शीर्ष (ग्राफ सिद्धांत)
 | This article includes a list of general references, but it lacks sufficient corresponding inline citations. (February 2014) (Learn how and when to remove this template message) |
असतत गणित में, और अधिक विशेष रूप से ग्राफ सिद्धांत में, एक वर्टेक्स (बहुवचन कोने) या नोड मौलिक इकाई है, जिसमें ग्राफ बनते हैं: एक ग्राफ (असतत गणित)#ग्राफ में वर्टिकल का एक सेट और एज (ग्राफ) का एक सेट होता है सिद्धांत) (कोने के अक्रमित जोड़े), जबकि एक निर्देशित ग्राफ में वर्टिकल का एक सेट और आर्क का एक सेट होता है (कोने के जोड़े का आदेश दिया जाता है)। एक ग्राफ के आरेख में, एक शीर्ष को आमतौर पर एक लेबल के साथ एक वृत्त द्वारा दर्शाया जाता है, और एक किनारे को एक रेखा या तीर द्वारा एक शीर्ष से दूसरे तक विस्तारित किया जाता है।
ग्राफ सिद्धांत के दृष्टिकोण से, शीर्षों को सुविधाहीन और अविभाज्य गणितीय वस्तु के रूप में माना जाता है, हालांकि उनके पास अतिरिक्त संरचना हो सकती है जो उस अनुप्रयोग के आधार पर होती है जिससे ग्राफ उत्पन्न होता है; उदाहरण के लिए, सिमेंटिक नेटवर्क एक ग्राफ़ है जिसमें कोने अवधारणाओं या वस्तुओं की कक्षाओं का प्रतिनिधित्व करते हैं।
किनारे बनाने वाले दो शीर्ष इस किनारे के अंत बिंदु कहलाते हैं, और किनारे को शीर्षों पर घटना कहा जाता है। एक शीर्ष w को दूसरे शीर्ष v के सन्निकट कहा जाता है यदि ग्राफ़ में एक किनारा है (v,w)। वर्टेक्स v का नेबरहुड (ग्राफ़ थ्योरी) ग्राफ़ का प्रेरित सबग्राफ़ है, जो v के आस-पास के सभी वर्टिकल से बनता है।
कोने के प्रकार
किसी वर्टेक्स की डिग्री (ग्राफ़ थ्योरी), जिसे ग्राफ़ में 𝛿(v) के रूप में दर्शाया जाता है, उसके किनारों की संख्या होती है। एक विलगित शीर्ष शून्य डिग्री वाला शीर्ष है; यानी, एक ऐसा शीर्ष जो किसी किनारे का समापन बिंदु नहीं है (उदाहरण छवि एक पृथक शीर्ष को दर्शाती है)।[1] एक लीफ वर्टेक्स (पेंडेंट वर्टेक्स भी) डिग्री वन के साथ एक वर्टेक्स है। निर्देशित ग्राफ़ में, आउटडिग्री (आउटगोइंग किनारों की संख्या) को अलग किया जा सकता है, जिसे 𝛿 दर्शाया गया है+(v), डिग्री से (आने वाले किनारों की संख्या), 𝛿 को दर्शाता है−(v); एक स्रोत शीर्ष शून्य के साथ एक शीर्ष है, जबकि एक सिंक शीर्ष शून्य के साथ एक शीर्ष है। एक साधारण शीर्ष वह है जिसके पड़ोसी एक समूह (ग्राफ सिद्धांत) बनाते हैं: प्रत्येक दो पड़ोसी आसन्न होते हैं। एक सार्वभौमिक शीर्ष एक ऐसा शीर्ष है जो ग्राफ में हर दूसरे शीर्ष के निकट है।
एक कटा हुआ शीर्ष एक वर्टेक्स है जिसे हटाने से शेष ग्राफ डिस्कनेक्ट हो जाएगा; एक शीर्ष विभाजक शीर्षों का एक संग्रह है जिसे हटाने से शेष ग्राफ छोटे टुकड़ों में टूट जाएगा। एक के-वर्टेक्स-कनेक्टेड ग्राफ एक ग्राफ़ है जिसमें k से कम वर्टिकल को हटाने से हमेशा शेष ग्राफ़ जुड़ा रहता है। एक स्वतंत्र सेट (ग्राफ़ थ्योरी) वर्टिकल का एक सेट है, जिनमें से कोई दो आसन्न नहीं हैं, और एक वर्टेक्स कवर वर्टिकल का एक सेट है जिसमें ग्राफ़ में प्रत्येक किनारे का कम से कम एक समापन बिंदु शामिल है। ग्राफ़ का वर्टेक्स स्पेस एक वेक्टर स्पेस है जिसमें ग्राफ़ के वर्टिकल के अनुरूप आधार वैक्टर का एक सेट होता है।
एक ग्राफ़ शीर्ष-सकर्मक ग्राफ है | वर्टेक्स-ट्रांसिटिव अगर इसमें समरूपता है जो किसी भी वर्टेक्स को किसी अन्य शीर्ष आकृति मैप करता है। ग्राफ गणना और ग्राफ़ समरूपता के संदर्भ में लेबल किए गए शीर्षों और लेबल रहित शीर्षों के बीच अंतर करना महत्वपूर्ण है। एक लेबल किया हुआ शीर्ष एक शीर्ष है जो अतिरिक्त जानकारी से जुड़ा होता है जो इसे अन्य लेबल वाले शीर्षों से अलग करने में सक्षम बनाता है; दो ग्राफ़ों को समरूपी तभी माना जा सकता है जब उनके शीर्षों के बीच पत्राचार समान लेबल वाले शीर्षों को जोड़ता है। एक बिना लेबल वाला शीर्ष वह होता है जिसे किसी अन्य शीर्ष के लिए केवल उसके आसन्नता (ग्राफ़ सिद्धांत) के आधार पर प्रतिस्थापित किया जा सकता है और किसी अतिरिक्त जानकारी पर आधारित नहीं होता है।
ग्राफ़ में वर्टिकल समरूप होते हैं, लेकिन वर्टेक्स (ज्यामिति) के समान नहीं होते हैं: पॉलीहेड्रॉन का कंकाल (टोपोलॉजी) एक ग्राफ़ बनाता है, जिसके कोने पॉलीहेड्रॉन के कोने होते हैं, लेकिन पॉलीहेड्रॉन के कोने में अतिरिक्त संरचना होती है (उनकी ज्यामितीय) स्थान) जिसे ग्राफ सिद्धांत में मौजूद नहीं माना जाता है। एक पॉलीहेड्रॉन में शीर्ष का शीर्ष आंकड़ा एक ग्राफ में शीर्ष के पड़ोस के अनुरूप होता है।
यह भी देखें
- नोड (कंप्यूटर विज्ञान)
- ग्राफ सिद्धांत
- ग्राफ सिद्धांत की शब्दावली
संदर्भ
- ↑ File:Small Network.png; example image of a network with 8 vertices and 10 edges
- Gallo, Giorgio; Pallotino, Stefano (1988). "Shortest path algorithms". Annals of Operations Research. 13 (1): 1–79. doi:10.1007/BF02288320. S2CID 62752810.
- Berge, Claude, Théorie des graphes et ses applications. Collection Universitaire de Mathématiques, II Dunod, Paris 1958, viii+277 pp. (English edition, Wiley 1961; Methuen & Co, New York 1962; Russian, Moscow 1961; Spanish, Mexico 1962; Roumanian, Bucharest 1969; Chinese, Shanghai 1963; Second printing of the 1962 first English edition. Dover, New York 2001)
- Chartrand, Gary (1985). Introductory graph theory. New York: Dover. ISBN 0-486-24775-9.
- Biggs, Norman; Lloyd, E. H.; Wilson, Robin J. (1986). Graph theory, 1736-1936. Oxford [Oxfordshire]: Clarendon Press. ISBN 0-19-853916-9.
- Harary, Frank (1969). Graph theory. Reading, Mass.: Addison-Wesley Publishing. ISBN 0-201-41033-8.
- Harary, Frank; Palmer, Edgar M. (1973). Graphical enumeration. New York, Academic Press. ISBN 0-12-324245-2.