वर्टेक्स
एज
टुकड़े

क्लिक
  • रेगुलर
  • पूर्ण

ग्राफ़ थ्योरी के बारे में और

ग्राफ़ थ्योरी प्लेग्राउंड

ग्राफ़ बिंदुओं का एक समूह है, जिन्हें वर्टेक्स कहते हैं, और ये बिंदु रेखाओं से जुड़े होते हैं, जिन्हें एज कहते हैं। यहाँ कुछ क्लिक में एक ग्राफ़ बनाएँ, और प्लेग्राउंड बताएगा कि यह किस तरह का ग्राफ़ है: इसमें कितने टुकड़े हैं, क्या यह ट्री है, इसे कम से कम कितने रंग चाहिए, क्या इसे बिना पेन उठाए बनाया जा सकता है, और भी बहुत कुछ। किसी गुण पर क्लिक करके उसे अपने ग्राफ़ पर देखें, कोई एज बदलें, और जवाबों को बदलते देखें। वर्टेक्स जोड़ने के लिए किसी खाली जगह पर क्लिक करें। दो वर्टेक्स को एज से जोड़ने के लिए एक वर्टेक्स पर, फिर दूसरे पर क्लिक करें; एज हटाने के लिए यही दोबारा करें। किसी वर्टेक्स को खिसकाने के लिए उसे खींचें। क्लिक को “मिटाए” पर बदलें और किसी वर्टेक्स या एज को हटाने के लिए उस पर क्लिक करें। वर्टेक्स चुना होने पर Delete उसे हटाता है और Escape उसे छोड़ देता है। किसी गुण को ग्राफ़ पर देखने के लिए उस पर क्लिक करें। “उदाहरण” कोई जाना-माना ग्राफ़ लोड करता है, “रैंडम ग्राफ़” एक नया ग्राफ़ बनाता है, “व्यवस्थित करें” वर्टेक्स को फैला देता है, और “पूरक” ठीक उन्हीं जोड़ों को जोड़ता है जो पहले जुड़े नहीं थे। Ctrl+Z एक चरण पूर्ववत करता है।

यह कैसे काम करता है

  1. वर्टेक्स जोड़ने के लिए किसी खाली जगह पर क्लिक करें। दो वर्टेक्स को जोड़ने के लिए एक वर्टेक्स पर, फिर दूसरे पर क्लिक करें; एज हटाने के लिए यही दोबारा करें। किसी वर्टेक्स को खिसकाने के लिए उसे खींचें।
  2. ग्राफ़ के नीचे गुण पढ़ें, और किसी गुण पर क्लिक करके उसे दिखाएँ: कलरिंग, दोनों पक्ष, यूलर ट्रेल, स्पैनिंग ट्री, सबसे छोटा साइकिल या व्यास।
  3. पीटरसन ग्राफ़ जैसा कोई उदाहरण लोड करें, रैंडम ग्राफ़ बनाएँ, पूरक लें, या वर्टेक्स और एज हटाने के लिए क्लिक को “मिटाए” पर बदलें।

गुणों का मतलब

किसी वर्टेक्स की डिग्री उससे जुड़े एजों की संख्या है। ग्राफ़ कनेक्टेड तब होता है जब हर वर्टेक्स एजों के सहारे हर दूसरे वर्टेक्स तक पहुँच सके, और ट्री तब, जब वह कनेक्टेड हो और उसमें कोई साइकिल न हो। वह बाइपार्टाइट तब होता है जब उसके वर्टेक्स दो पक्षों में बँट जाएँ और हर एज एक पक्ष से दूसरे पक्ष तक जाए, और ऐसा ठीक तब होता है जब उसमें विषम लंबाई का कोई साइकिल न हो। क्रोमैटिक संख्या रंगों की वह न्यूनतम संख्या है जिससे पड़ोसी वर्टेक्स को अलग-अलग रंग मिलें। सबसे छोटे साइकिल की लंबाई को गर्थ कहते हैं, और व्यास दो वर्टेक्स के बीच की सबसे बड़ी दूरी है, जो एजों में गिनी जाती है।

बिना पेन उठाए बनाना

यूलर ट्रेल हर एज का ठीक एक बार इस्तेमाल करता है। लियोनहार्ड यूलर ने 1736 में कोनिग्सबर्ग के सात पुलों के सवाल में देखा कि रुकावट क्या है: ट्रेल जब भी किसी वर्टेक्स से होकर गुज़रता है, उसके दो एज इस्तेमाल करता है। इसलिए या तो हर डिग्री सम हो, और तब ट्रेल वहीं खत्म हो सकता है जहाँ से शुरू हुआ था, या ठीक दो डिग्री विषम हों, और तब ट्रेल को उनमें से एक वर्टेक्स से दूसरे तक जाना होगा। बाद में कार्ल हीरहोल्ज़र ने साबित किया कि यह शर्त, सारे एज एक ही टुकड़े में होने के साथ, काफ़ी भी है। घर वाला उदाहरण लोड करें और पता लगाएँ कि रेखा कहाँ से शुरू करनी होगी।

अक्सर पूछे जाने वाले प्रश्न

ग्राफ़ थ्योरी में ग्राफ़ क्या होता है?

बिंदुओं का एक समूह, जिन्हें वर्टेक्स या नोड कहते हैं, और उनमें से कुछ जोड़ों के बीच की रेखाएँ, जिन्हें एज कहते हैं। यह किसी फ़ंक्शन का ग्राफ़ नहीं है: यह सिर्फ़ बताता है कि कौन किससे जुड़ा है। सड़कों के नक्शे, सोशल नेटवर्क, अणु और कंप्यूटर नेटवर्क, सभी ग्राफ़ हैं।

क्रोमैटिक संख्या कैसे निकाली जाती है?

प्लेग्राउंड ग्राफ़ को पहले एक रंग से रंगने की कोशिश करता है, फिर दो से, फिर तीन से, और इसी तरह आगे। हर संख्या के लिए वह सभी मायने रखने वाले तरीके खोजता है, और हमेशा अगला उस वर्टेक्स को रंगता है जिसके पड़ोसियों में पहले से सबसे ज़्यादा रंग इस्तेमाल हो चुके हों। जो पहली संख्या काम कर जाए, वही क्रोमैटिक संख्या है। यहाँ बनाए जा सकने वाले ग्राफ़ के लिए इसमें ज़्यादा से ज़्यादा एक पल लगता है; बहुत कठिन ग्राफ़ पर सर्च जल्दी रुक जाती है और मान ऊपरी सीमा के रूप में दिखाया जाता है।

किसी ग्राफ़ में यूलर पाथ कब होता है?

जब उसके सारे एज एक ही टुकड़े में हों और दो से ज़्यादा वर्टेक्स की डिग्री विषम न हो। कोई विषम वर्टेक्स न हो, तो एक यूलर सर्किट होता है जो वहीं खत्म होता है जहाँ से शुरू होता है; दो हों, तो हर यूलर पाथ उनमें से एक पर शुरू होकर दूसरे पर खत्म होता है। विषम वर्टेक्स की संख्या हमेशा सम होती है, इसलिए यह कभी ठीक एक नहीं होती।

किसी ग्राफ़ का पूरक क्या होता है?

उन्हीं वर्टेक्स पर बना वह ग्राफ़ जिसके एज ठीक वे जोड़े हैं जो पहले जुड़े नहीं थे। पूरक का पूरक वही ग्राफ़ है जिससे आपने शुरुआत की थी। उदाहरण के लिए, पीटरसन ग्राफ़ का पूरक 6-रेगुलर है, क्योंकि हर वर्टेक्स बाकी 9 में से 3 से जुड़ा था।

पीटरसन ग्राफ़ इतना मशहूर क्यों है?

यह 10 वर्टेक्स और 15 एज वाला एक छोटा-सा ग्राफ़ है, जो कई उम्मीद भरे अनुमानों को गलत साबित करने वाला प्रति-उदाहरण है। हर वर्टेक्स की डिग्री 3 है, इसके सबसे छोटे साइकिल की लंबाई 5 है, कोई भी दो वर्टेक्स ज़्यादा से ज़्यादा 2 एज दूर हैं, और इसे एजों के एक-दूसरे को काटे बिना नहीं बनाया जा सकता। प्लेग्राउंड इसी से शुरू होता है।

आज़माने के लिए तैयार?

अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।

एडिटर पर जाएँ