قائمة المصطلحات

حدد واحدة من الكلمات الرئيسية على اليسار ...

الرسوم البيانية والشبكاتالمصافحة والتعارف

وقت القراءة: ~15 min

لقد تمت دعوتك لحفلة عيد ميلاد رائعة مع أصدقائك. بما في ذلك أنت والمضيف ، هناك ${hnd} شخصًا موجودًا. في المساء ، عندما يستعد الضيوف للمغادرة ، يصافح الجميع بعضهم البعض. كم عدد المصافحات في المجموع؟ يمكننا تمثيل المصافحات باستخدام رسم بياني: كل شخص هو ، وكل مصافحة .

أصبح من السهل الآن حساب عدد الحواف في الرسم البياني. نجد أنه مع ${hnd} شخص ، هناك ${hnd*(hnd-1)/2} مصافحة.

بدلاً من حساب جميع الحواف في الرسوم البيانية الكبيرة ، يمكننا أيضًا محاولة العثور على صيغة بسيطة تخبرنا بنتيجة أي عدد من الضيوف . كل من ${n} شخص في الحفلة يصافحون ${n-1} آخرين. وهذا يجعل ${n} × ${n-1} = ${n×(n-1)} مصافحة إجمالاً. بالنسبة إلى n شخصًا ، سيكون عدد المصافحات .

للأسف ، هذه الإجابة ليست صحيحة تمامًا. لاحظ كيف ] أول إدخالين في الصف العلوي ](->.handshakes_trfirst-child_tdfirst-child,.handshakes_trfirst-child_tdnth-child(2)) في الواقع هي نفسها ، فقط انقلبت. في الواقع ، لقد حسبنا كل مصافحة ، _{span.reveal(data-when="blank-0")} مرة واحدة لكل من الأشخاص المعنيين. وهذا يعني أن العدد الصحيح للمصافحة لـ ${n} ضيفًا هو ${n}×${n-1}2=${n*(n-1)/2}.

الرسوم البيانية للمصافحة خاصة لأن كل رؤوس متصلة بكل رؤوس أخرى. تسمى الرسوم البيانية بهذه الخاصية الرسوم البيانية الكاملة. غالبًا ما يتم اختصار الرسم البياني الكامل ذو 4 رؤوس كـ K4 ، ويعرف الرسم البياني الكامل الذي يحتوي على 5 رؤوس باسم K5 ، وهكذا. لقد أظهرنا للتو أن رسمًا بيانيًا كاملاً يحتوي على n رؤوس ، Kn ، له n×n12 حواف.

في يوم مختلف ، تتم دعوتك إلى حدث مواعدة سريع لـ ${m} فتيان و ${f} فتيات. هناك العديد من الطاولات الصغيرة وكل طفل يقضي 5 دقائق مع كل من الفتيات. كم عدد "التواريخ" الفردية الموجودة في المجموع؟

في هذه الحالة ، يتكون الرسم البياني المقابل من مجموعتين منفصلتين من الرؤوس. كل قمة متصلة بجميع الرؤوس في مجموعة ، ولكن لا توجد أي قمة في مجموعة . تسمى الرسوم البيانية التي تحتوي على هذا التنسيق الرسوم البيانية الثنائية.

غالبًا ما تتم كتابة الرسم البياني الثنائي مع مجموعتين من الحجم × و ص بالشكل Kx,y. يحتوي على حواف ، مما يعني أنه في المثال أعلاه هناك ${m} × ${f} = ${m×f} التواريخ.