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

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

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

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

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

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