-
منتظم
-
تام
مختبر نظرية الرسوم البيانية
الرسم البياني مجموعة من النقاط تُسمّى الرؤوس، تصل بينها خطوط تُسمّى الحواف. ارسم واحدًا هنا ببضع نقرات، وسيخبرك المختبر بنوعه: كم جزءًا فيه، وهل هو شجرة، وما أقل عدد من الألوان يحتاج إليه، وهل يمكنك رسمه دون رفع القلم، وغير ذلك. انقر على خاصية لتراها على رسمك، وغيّر حافة، وراقب الإجابات وهي تتغير. انقر على مكان فارغ لإضافة رأس. انقر على رأس ثم على آخر لتصل بينهما بحافة؛ وكرّر ذلك لإزالة الحافة. اسحب رأسًا لتحريكه. حوّل النقر إلى «يمحو» ثم انقر على رأس أو حافة لحذفه. عند تحديد رأس، يحذفه مفتاح Delete ويلغي Escape تحديده. انقر على خاصية لعرضها على الرسم البياني. «مثال» يحمّل رسمًا بيانيًا معروفًا، و«رسم بياني عشوائي» ينشئ رسمًا جديدًا، و«ترتيب» يباعد بين الرؤوس، و«المتمِّم» يصل تمامًا بين الأزواج التي لم تكن موصولة. ويتراجع Ctrl+Z خطوة واحدة.
كيف يعمل
- انقر على مكان فارغ لإضافة رأس. انقر على رأس ثم على آخر لتصل بينهما؛ وكرّر ذلك لإزالة الحافة. اسحب رأسًا لتحريكه.
- اقرأ الخصائص أسفل الرسم البياني، وانقر على إحداها لعرضها: تلوينًا، أو الجانبين، أو درب أويلر، أو شجرة ممتدة، أو أقصر دورة، أو القطر.
- حمّل مثالاً مثل رسم بيترسن البياني، أو أنشئ رسمًا بيانيًا عشوائيًا، أو خذ المتمِّم، أو حوّل النقر إلى «يمحو» لحذف الرؤوس والحواف.
ماذا تعني الخصائص
درجة الرأس هي عدد الحواف المتصلة به. يكون الرسم البياني متصلاً حين يستطيع كل رأس الوصول إلى كل رأس آخر عبر الحواف، ويكون شجرة حين يكون متصلاً وبلا دورات. ويكون ثنائي التجزئة حين تنقسم رؤوسه إلى جانبين وكل حافة تعبر من جانب إلى الآخر، وهذا يحدث تمامًا حين لا تكون فيه دورة طولها فردي. والعدد اللوني هو أقل عدد من الألوان يعطي الرؤوس المتجاورة ألوانًا مختلفة. ويُسمّى طول أقصر دورة الخصر، والقطر هو أكبر مسافة بين رأسين، محسوبة بعدد الحواف.
الرسم دون رفع القلم
يمر درب أويلر بكل حافة مرة واحدة بالضبط. أدرك ليونهارد أويلر عام 1736، مع جسور كونيغسبرغ السبعة، ما الذي يقف في الطريق: في كل مرة يمر فيها الدرب برأس يستخدم حافتين من حوافه. لذا إما أن تكون كل الدرجات زوجية، فيمكن أن ينتهي الدرب حيث بدأ، وإما أن تكون درجتان فقط فرديتين، فيجب أن يسير الدرب من أحد هذين الرأسين إلى الآخر. وأثبت كارل هيرهولتسر لاحقًا أن هذا الشرط، مع وجود كل الحواف في جزء واحد، كافٍ أيضًا. حمّل مثال البيت واكتشف من أين يجب أن يبدأ الخط.
الأسئلة المتداولة
ما الرسم البياني في نظرية الرسوم البيانية؟
مجموعة من النقاط تُسمّى الرؤوس أو العقد، وخطوط بين بعض أزواجها تُسمّى الحواف. وهو ليس منحنى دالة: إنه يصف فقط ما الموصول بماذا. خرائط الطرق والشبكات الاجتماعية والجزيئات وشبكات الحاسوب كلها رسوم بيانية.
كيف يُحسب العدد اللوني؟
يحاول المختبر تلوين الرسم البياني بلون واحد، ثم بلونين، ثم بثلاثة، وهكذا، ولكل عدد يبحث في كل الطرق المهمة، ويلوّن دائمًا بعد ذلك الرأس الذي تستخدم جيرانه أكبر عدد من الألوان. وأول عدد ينجح هو العدد اللوني. في الرسوم التي يمكنك رسمها هنا لا يستغرق ذلك أكثر من لحظة؛ أما في رسم بياني صعب جدًا فيتوقف البحث مبكرًا وتُعرض القيمة على أنها حد أعلى.
متى يكون للرسم البياني مسار أويلر؟
حين تكون كل حوافه في جزء واحد ولا يزيد عدد الرؤوس ذات الدرجة الفردية على اثنين. إذا لم يكن فيه رأس فردي فثمة دارة أويلر تنتهي حيث تبدأ؛ وإذا كان فيه رأسان فرديان، فكل مسار أويلر يبدأ عند أحدهما وينتهي عند الآخر. وعدد الرؤوس الفردية زوجي دائمًا، فلا يكون واحدًا أبدًا.
ما متمِّم الرسم البياني؟
هو الرسم البياني على الرؤوس نفسها، وحوافه هي بالضبط الأزواج التي لم تكن موصولة من قبل. ومتمِّم المتمِّم هو الرسم الذي بدأت به. فمتمِّم رسم بيترسن البياني مثلاً منتظم من الدرجة 6، لأن كل رأس كان موصولاً بـ 3 من الرؤوس الأخرى البالغ عددها 9.
لماذا اشتهر رسم بيترسن البياني؟
إنه رسم بياني صغير فيه 10 رؤوس و15 حافة، وهو مثال مضاد لكثير من التخمينات المتفائلة. درجة كل رأس 3، وطول أقصر دورة فيه 5، وأي رأسين تفصل بينهما حافتان على الأكثر، ولا يمكن رسمه دون تقاطع الحواف. ويبدأ المختبر به.
هل أنت مستعد لتجربتها؟
افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.
الانتقال إلى المحرر