रेखांकन और नेटवर्कहैंडशेक और डेटिंग

बड़े ग्राफ़ में सभी किनारों को गिनने के बजाय, हम एक सरल सूत्र खोजने की कोशिश भी कर सकते हैं जो हमें किसी भी संख्या में मेहमानों के लिए परिणाम बताता है।

हर एक ${n} पार्टी के लोग हाथ मिलाते हैं ${n-1} अन्य। ये बनाता है ${n} × ${n-1} = ${n×(n-1)} कुल में हाथ मिलाना। N लोगों के लिए, हैंडशेक की संख्या होगी n×n−1n×n+1n2 ।

दुर्भाग्य से यह जवाब काफी सही नहीं है। नोटिस कैसे शीर्ष पंक्ति पर पहले दो प्रविष्टियाँ वास्तव में वही हैं, बस चारों ओर फ़्लिप।

वास्तव में, हमने हर हैंडशेक को गिना है एक बार तीन बार , दो लोगों में से प्रत्येक के लिए एक बार। इसका मतलब है कि सही संख्या के लिए हैंडशेक ${n} मेहमान है ${n}×${n-1}2=${n*(n-1)/2} ।

हैंडशेक ग्राफ खास हैं क्योंकि हर वर्टेक्स हर दूसरे वर्टेक्स से जुड़ा होता है। इस संपत्ति वाले रेखांकन को पूर्ण रेखांकन कहा जाता है। 4 शीर्षकों के साथ पूरा ग्राफ अक्सर संक्षिप्त होता है K4 5 सिरों के साथ पूर्ण ग्राफ के रूप में जाना जाता है K5 , और इसी तरह।

हमने अभी-अभी दिखाया है कि एक पूर्ण ग्राफ़ के साथ n कोने, Kn , है n×n−12 किनारों।

एक अलग दिन में, आपको एक स्पीड डेटिंग इवेंट के लिए आमंत्रित किया जाता है ${m} लड़के और ${f} लड़कियाँ। कई छोटी टेबल हैं और हर लड़का लड़कियों के साथ 5 मिनट बिताता है। कुल कितने "दिनांक" हैं?

साइज़ x और y के दो सेट के साथ द्विदलीय ग्राफ को अक्सर लिखा जाता है Kx,y । यह है x×yx+y2x−y किनारों, जिसका अर्थ है कि उपरोक्त उदाहरण में हैं ${m} × ${f} = ${m×f} खजूर।