نظرية الرسوم البيانية
نقاط وخطوط بينها: هذا كل ما في الرسم البياني. ومع ذلك تصف الصورة نفسها خريطة طرق، وشبكة أصدقاء، وجزيئًا، والإنترنت، والأسئلة التي يمكن طرحها عنها، من عدد الألوان التي يحتاج إليها إلى إمكانية رسمه دون رفع القلم، تشغل علماء الرياضيات منذ عام 1736.
الرؤوس والحواف
للرسم البياني رؤوس، تُسمّى أيضًا عقدًا، وحواف تصل كل منها بين رأسين. لا يهم أين تُرسم الرؤوس، بل المهم أي الأزواج موصولة، لذا قد يبدو الرسم البياني نفسه مختلفًا جدًا على الورق. الرسوم البيانية في المختبر بسيطة: لا حافة من رأس إلى نفسه، وحافة واحدة على الأكثر بين رأسين. ومع n من الرؤوس يمكن أن يكون عدد الحواف n(n − 1) / 2 على الأكثر؛ والرسم الذي يحتوي عليها جميعًا يُسمّى تامًا، وK5 هو الرسم البياني التام على خمسة رؤوس.
الدرجات ومبرهنة المصافحة
درجة الرأس هي عدد الحواف المتصلة به. اجمع كل الدرجات تحصل بالضبط على ضعف عدد الحواف، لأن لكل حافة طرفين وتُعدّ مرة عند كل منهما. هذه هي مبرهنة المصافحة: في أي مجموعة من الناس، مجموع المصافحات المعدودة شخصًا شخصًا يساوي ضعف عدد المصافحات. وهذا يعني أيضًا أن عدد الرؤوس ذات الدرجة الفردية زوجي دائمًا. والرسم البياني الذي درجة كل رأس فيه هي k نفسها يُسمّى منتظمًا من الدرجة k.
الرسوم المتصلة والأشجار والدورات
يكون الرسم البياني متصلاً حين يمكنك الانتقال من كل رأس إلى كل رأس آخر عبر الحواف؛ وإلا فإنه ينقسم إلى أجزاء تُسمّى المكونات. الدورة جولة تعود إلى بدايتها دون أن تمر برأس مرتين، وطول أقصر دورة هو الخصر. والرسم المتصل الخالي من الدورات شجرة، والشجرة ذات n من الرؤوس فيها دائمًا n − 1 حافة بالضبط: إن نقصت حافة انقسمت، وإن زادت حافة ظهرت فيها دورة. ويحتوي كل رسم بياني متصل على شجرة ممتدة، وهي شجرة تبلغ كل رأس باستخدام بعض الحواف فقط.
الرسوم ثنائية التجزئة والتلوين
لوّن الرؤوس بحيث لا تصل أي حافة بين رأسين من اللون نفسه. أقل عدد من الألوان يحقق ذلك هو العدد اللوني. لا يكفي لون واحد إلا إذا لم تكن هناك حواف. ويكفي لونان تمامًا حين يكون الرسم البياني ثنائي التجزئة: تنقسم رؤوسه إلى جانبين وكل حافة تعبر بينهما. وقد بيّن دينيش كونيغ عام 1936 أن هذا يكافئ خلوّه من أي دورة طولها فردي، لأن الدورة الفردية لا يمكن أن يتناوب عليها لونان. أما لثلاثة ألوان أو أكثر فلا يُعرف اختبار بسيط كهذا: تحديد ما إذا كانت ثلاثة ألوان تكفي مسألة NP-كاملة، لذا تلجأ البرامج إلى البحث، كما يفعل المختبر.
مثال: رسم بيترسن البياني
خذ خماسيًا A–B–C–D–E ونجمة خماسية F–H–J–G–I داخله، وصِل كل رأس من رؤوس الخماسي برأس من رؤوس النجمة: A–F وB–G وC–H وD–I وE–J. هذا هو رسم بيترسن البياني، وفيه 10 رؤوس و15 حافة. درجة كل رأس 3، فمجموع الدرجات 30، أي ضعف 15. وطول أقصر دورة فيه 5، فلا مثلث فيه، لكن الخماسي دورة فردية، فهو ليس ثنائي التجزئة ويحتاج إلى 3 ألوان. وأي رأسين تفصل بينهما حافتان على الأكثر، فقطره 2. ودرجاته العشر كلها فردية، فلا يوجد فيه درب أويلر، ولا يمكن رسمه دون تقاطعات.
مسارات أويلر وجسور كونيغسبرغ
كان في مدينة كونيغسبرغ سبعة جسور تصل بين أربع قطع من اليابسة، وتساءل الناس هل يمكن عبور كل جسر مرة واحدة بالضبط في نزهة واحدة. وفي عام 1736 أثبت ليونهارد أويلر أن ذلك مستحيل، فوُلدت نظرية الرسوم البيانية. في كل مرة تمر فيها النزهة بقطعة من اليابسة تستخدم جسرين، لذا لا يجوز أن يكون عدد الجسور فرديًا إلا عند البداية والنهاية، بينما كان عدد الجسور عند كل قطعة من قطع كونيغسبرغ الأربع فرديًا. ويُسمّى الدرب الذي يمر بكل حافة مرة واحدة اليوم مسار أويلر، أو دارة أويلر إذا انتهى حيث بدأ. وأثبت كارل هيرهولتسر عام 1873 أن الشرط كافٍ أيضًا: إذا كانت كل الحواف في جزء واحد ولم يزد عدد الدرجات الفردية على اثنتين، فالدرب موجود، وطريقته في ربط الجولات المغلقة بعضها ببعض ما زالت تجده حتى اليوم.
المسافة والقطر والمتمِّم
المسافة بين رأسين هي أقل عدد من الحواف على مسار بينهما، والقطر هو أكبر مسافة في الرسم البياني؛ وفي رسم غير متصل يكون لا نهائيًا. للشبكات الاجتماعية أقطار صغيرة، وهذه هي الفكرة وراء «درجات الانفصال الست». ومتمِّم الرسم البياني له الرؤوس نفسها ويصل تمامًا بين الأزواج التي لم تكن موصولة. ومن بين الرسم البياني ومتمِّمه، يكون أحدهما على الأقل متصلاً دائمًا.
استكشفه بنفسك
يُفتح المختبر على رسم بيترسن البياني ملونًا بثلاثة ألوان. انقر على «الدرجات» وتحقق من مبرهنة المصافحة، وانقر على «ثنائي التجزئة» لترى دورة فردية، ثم حمّل المكعب وشاهد الجانبين يظهران. حمّل البيت وانقر على «درب أويلر» لترى من أين يجب أن يبدأ الرسم دون رفع القلم. ارسم رسمك البياني وأضف حافة في كل مرة: راقب أقصر دورة وهي تقصر، والقطر وهو ينخفض، والعدد اللوني وهو يرتفع عند إضافة آخر حافة في K4.
الأسئلة المتداولة
ما الفرق بين المسار والدرب والجولة؟
الجولة أي متتالية من الرؤوس تصل بينها حواف، ويجوز أن تتكرر فيها الرؤوس والحواف كلتاهما. والدرب يجوز أن تتكرر فيه الرؤوس لا الحواف، ولهذا يمكن لدرب أويلر أن يمر برأس عدة مرات. أما المسار فلا يتكرر فيه أي منهما.
ما مبرهنة الألوان الأربعة؟
تنص على أن كل رسم بياني يمكن رسمه على الورق دون تقاطع الحواف يمكن تلوينه بأربعة ألوان على الأكثر، لذا لا تحتاج أي خريطة إلى أكثر من أربعة ألوان. أثبتها كينيث أبيل وفولفغانغ هاكن عام 1976 بمساعدة الحاسوب، وكانت أول مبرهنة كبرى تُثبت بهذه الطريقة.
ما الدورة الهاملتونية؟
دورة تمر بكل رأس مرة واحدة بالضبط، بدلاً من كل حافة. تبدو شبيهة بسؤال أويلر، لكن لا يُعرف لها اختبار بسيط: تحديد ما إذا كان للرسم البياني دورة كهذه مسألة NP-كاملة. لرسم بيترسن البياني مسار هاملتوني لكن ليست له دورة هاملتونية.
أين تُستخدم نظرية الرسوم البيانية؟
تبحث برامج تخطيط المسارات في رسوم الطرق البيانية، وترتّب محركات البحث صفحات الويب بحسب روابطها، وتلوّن المصرّفات رسومًا بيانية لتقاسم سجلات المعالج، وتتجنب الجداول الزمنية التعارضات بتلوين رسم بياني للتعارضات، ويعدّ الكيميائيون الجزيئات بوصفها رسومًا بيانية، وتُدرس شبكات الحواسيب وخطوط الكهرباء والأصدقاء بوصفها رسومًا بيانية.
هل أنت مستعد لتجربتها؟
افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.
افتح مختبر نظرية الرسوم البيانية