فيديو قصير: صيغة أويلر وازدواجية المخططات

نسخة الفيديو النصية

في الفيديو الذي تناولت فيه مسألة تقسيم الدائرة، أشرت إلى صيغة مميزة أويلر. وهنا، أريد أن أعرض لكم برهانًا جيدًا جدًا لهذه الصيغة. وهو مختلف تمامًا عن البرهان الاستقرائي المعطى عادة، لكن لن أحاول أن أبرهن على أنه أفضل أو أسهل بطريقة أو بأخرى عن البراهين الأخرى. بدلًا من ذلك، اخترت هذا الموضوع لأوضح مثالًا على المفهوم الرائع للازدواجية وكيف يمكنها أن تنتج صيغًا رياضية بارعة وبسيطة.

أولًا، لنراجع ما تنص عليه النظرية. إذا رسمت بعض النقاط وبعض الخطوط التي تصل بينها، فسيكون هذا مخططًا، وإذا لم يتقاطع أي من هذه الخطوط، وهو ما يمكن أن نقول عنه مخططًا مستويًا، شريطة أن يكون الرسم مترابطًا، فإن صيغة أويلر تخبرنا بأن عدد النقاط ناقص عدد الخطوط زائد عدد الأجزاء التي تنتج عن تقسيم هذه الخطوط للمستوى، بما فيها ذلك الجزء الخارجي، سيساوي دائمًا اثنين.

ونظرًا لأن أويلر كان يتحدث في الأساس عن متعدد السطوح الثلاثي الأبعاد عندما توصل إلى هذه الصيغة، والتي لم تعد صياغتها إلا فيما بعد مع المخططات المستوية، فبدلًا من أن نقول نقاطًا، سنقول رءوسًا ‪(vertices)‬‏؛ وبدلًا من الخطوط، سنقول أحرفًا ‪(edges)‬‏؛ وبدلًا من أجزاء سنقول أوجهًا ‪(faces)‬‏. ومن ثم، نكتب الصيغة التي اكتشفها أويلر هكذا: ‪𝑉‬‏ ناقص ‪𝐸‬‏ زائد ‪𝐹‬‏ يساوي اثنين.

قبل شرح البرهان، أريد أن أستعرض ثلاثة مفاهيم تستخدم في مصطلحات نظرية المخططات، هي: الدورات، والشجرات الممتدة، والمخططات المزدوجة. إذا كنت على دراية بالفعل ببعض هذه الموضوعات ولا يعنيك أن تعرف كيف سأشرحها، فيمكنك النقر فوق المصطلح الذي تريده وتخطي المصطلحات الأخرى.

تخيل وجود كائن صغير يقف عند أحد الرءوس. لنطلق عليه اسم راندولف. إذا فكرنا في الأحرف على أنها شيء يمكن لراندولف أن يتحرك على امتداده، من رأس إلى آخر، فمن المنطقي أن نتحدث عن «المسار» بوصفه أحرفًا متتابعة يمكن لراندولف التحرك على امتدادها، حيث لا نسمح له بالعودة على أعقابه إلى الحرف نفسه.

الدورة ببساطة هي مسار ينتهي عند الرأس نفسه الذي بدأ منه. لعلك تستطيع تخمين أهمية الدورات لأغراضنا، بما أنها دائمًا ما تحيط بمجموعة من الأوجه.

الآن، تخيل أن راندولف يريد الوصول إلى الرءوس الأخرى جميعها، لكن الأحرف مكلفة، ومن ثم لن يشتري صلاحية وصول إلى أحد الأحرف إلا إذا كان يعطيه مسارًا إلى رأس لم يصل إليه من قبل. سينتج عن هذا التوفير مجموعة من الأحرف بلا أي دورات، بما أن الحرف الذي يكمل دورة سيكون دائمًا غير ضروري.

بشكل عام، المخطط المترابط دون دورات يسمى «شجرة»، والسبب وراء هذه التسمية أننا يمكننا تحريك الأشياء وجعلها تبدو كمجموعة من الأفرع، وأي شجرة داخل المخطط تمس جميع الرءوس تسمى بالشجرة الممتدة.

قبل تعريف المخطط المزدوج، الذي قد يكون مربكًا، من المهم أن نتذكر سبب اهتمام الناس بالمخططات في الأساس.

لقد كنت أكذب سابقًا عندما قلت إن المخطط هو مجموعة من النقاط والخطوط؛ إذ إنه في الحقيقة مجموعة من أشياء مترابطة، لكننا عادة نمثل هذه الأشياء بالنقاط ونمثل العلاقات بينها بالخطوط.

على سبيل المثال، يخزن فيسبوك مخططًا ضخمًا، تمثل فيه الرءوس الحسابات وتمثل فيه الأحرف الصداقات. على الرغم من أننا يمكننا استخدام الرسومات لتمثيل هذا المخطط، فإن المخطط نفسه هو المجموعة المجردة من الحسابات والصداقات، ويختلف تمامًا عن الرسم الممثل له.

الأشياء بجميع أنواعها هي مخططات غير مرسومة: مجموعة كلمات اللغة الإنجليزية تعد مرتبطة عندما تختلف فيما بينها في حرف واحد، وعلماء الرياضيات يعدون مرتبطين إذا كتبوا ورقة بحثية معًا، والخلايا العصبية مرتبطة بواسطة الوصلات العصبية، أو ربما بالنسبة لمن يفكرون في الرسم الفعلي لأحد المخططات على المستوى، يمكننا أن نأخذ مجموعة الأوجه الذي تنتج عن تقسيم هذا المخطط للمستوى ونعتبر أن وجهين منها متصلان إذا كانا يتشاركان في حرف.

بعبارة أخرى، إذا كان في مقدورك رسم مخطط على المستوى بلا أحرف متقاطعة، فستحصل تلقائيًّا على مخطط آخر، غير مرسوم حتى الآن، تكون رءوسه هي الأوجه وأحرفه هي أحرف المخطط الأصلي. يمكننا أن نسمي ذلك «المخطط المزدوج» للمخطط الأصلي.

إذا كنت تريد تمثيل المخطط المزدوج بالنقاط والخطوط، فعليك أولًا وضع نقطة بداخل كل وجه من الأوجه. أنا شخصيًّا أفضل تصور النقطة الموجودة في المنطقة الخارجية كنقطة في ما لا نهاية، حيث يمكنك التحرك في أي اتجاه للوصول إلى هناك.

بعد ذلك، صل هذه النقاط الجديدة بالخطوط الجديدة التي تمر عبر مراكز الخطوط القديمة، حيث يمكن للخطوط المتصلة بالنقطة الموجودة في ما لا نهاية الخروج عن الشاشة في أي اتجاه، طالما مفهوم أنها تتقابل جميعها في النقطة نفسها.

لكن مع الأخذ في الاعتبار أن هذا مجرد رسم للمخطط المزدوج، تمامًا مثل أن تمثيل حسابات فيسبوك والصداقات بالنقاط والخطوط هو مجرد رسم لمخطط شبكة التواصل الاجتماعي؛ المخطط المزدوج نفسه هو مجموعة الأوجه والأحرف.

السبب في أنني أؤكد على هذه النقطة هو للتأكيد على أن أحرف المخطط الأصلي وأحرف المخطط المزدوج ليست مجرد أحرف مرتبطة؛ إنما هي الشيء نفسه.

كما ترى، فالسبب في روعة المخطط المزدوج هو الطرق العديدة التي يرتبط من خلالها بالمخطط الأصلي. على سبيل المثال، الدورات في المخطط الأصلي تناظر العناصر المرتبطة للمخطط المزدوج، وبالمثل فإن الدورات في المخطط المزدوج تناظر العناصر المرتبطة في المخطط الأصلي.

والآن نأتي إلى الجزء الشيق. لنفترض أن صديقنا راندولف لديه مثيل آخر، مورتيمر، وهو يعيش في المخطط المزدوج، وينتقل من وجه لآخر بدلًا من رأس لآخر، ويمر فوق الأحرف بينما يفعل ذلك.

لنقل إن راندولف اشترى جميع أحرف الشجرة الممتدة ومحظور على مورتيمر عبور هذه الأحرف. يتضح أن الأحرف المتاحة لمورتيمر وفرتها له شجرة ممتدة للمخطط المزدوج.

لمعرفة السبب، ما علينا إلا أن نتحقق من الخاصيتين اللتين تحددان الشجرات الممتدة: يجب أن توفرا لمورتيمر صلاحية الوصول إلى الأوجه جميعها وتكون هناك أي دورات.

السبب في أنه ما زالت لديه صلاحية الوصول إلى الأوجه جميعها هو أن الأمر سيستغرق دورة في الشجرة الممتدة لراندولف لمنعه عن أحد الأوجه، لكن الشجرات لا يمكن أن تكون لها دورات.

السبب في أن مورتيمر لا يمكنه اجتياز دورة في المخطط المزدوج يبدو متماثلًا تمامًا. إذا تمكن من اجتياز إحدى الدورات، فسيفصل مجموعة من رءوس راندولف عن البقية، ومن ثم لن تتمكن الشجرة الممتدة المحظور فيها من الامتداد لتشمل المخطط بالكامل.

إذن، ليست المخططات المستوية وحدها هي التي لها مخططات مزدوجة، فأي شجرة ممتدة في المخطط دائمًا لها شجرة ممتدة مزدوجة في المخطط المزدوج.

وإليكم المفاجأة: عدد الرءوس في أي شجرة يزيد دائمًا بمقدار واحد على عدد الأحرف. ولكي نرى ذلك، لاحظ أنه بعدما تبدأ بالرأس الأساسي، فإن كل حرف جديد يعطيك بالضبط رأسًا جديدًا.

بدلًا من ذلك، ووفقًا لروايتنا، يمكنك تصور راندولف وهو يبدأ برأس واحد ويحصل على رأس آخر لكل حرف يشتريه على هيئة ما سيصبح شجرة ممتدة. بما أن الشجرة تغطي الرءوس جميعها في المخطط، فإن عدد الرءوس يزيد بمقدار واحد على عدد الأحرف التي لدى راندولف.

علاوة على ذلك، بما أن الأحرف المتبقية تكون شجرة ممتدة للمخطط المزدوج الخاص بمورتيمر، فإن عدد الأحرف التي يحصل عليها يزيد بمقدار واحد على عدد الرءوس في المخطط المزدوج، وهي أوجه المخطط الأصلي.

بوضع هذا معًا، نجد أنه يعني أن العدد الكلي للأحرف يزيد بمقدار اثنين على عدد الرءوس زائد عدد الأوجه، وهو ما تنص عليه صيغة أويلر بالضبط.