वर्टेक्स (ग्राफ़ सिद्धांत)
असतत गणित में, और विशेष रूप से ग्राफ़ सिद्धांत में, एक शीर्ष (बहुवचन शीर्ष) या नोड वह मूलभूत इकाई है जिससे ग्राफ़ बनते हैं: एक ग्राफ़ (असतत गणित)#ग्राफ़ में शीर्षों का एक सेट और किनारे का एक सेट होता है (ग्राफ़) सिद्धांत) (शीर्षों के अव्यवस्थित जोड़े), जबकि एक निर्देशित ग्राफ में शीर्षों का एक सेट और चापों का एक सेट (शीर्षों के क्रमबद्ध जोड़े) होते हैं। ग्राफ़ के आरेख में, एक शीर्ष को आमतौर पर एक लेबल के साथ एक वृत्त द्वारा दर्शाया जाता है, और एक किनारे को एक शीर्ष से दूसरे तक फैली हुई रेखा या तीर द्वारा दर्शाया जाता है।
ग्राफ़ सिद्धांत के दृष्टिकोण से, शीर्षों को सुविधाहीन और अविभाज्य गणितीय वस्तु के रूप में माना जाता है, हालाँकि ग्राफ़ जिस अनुप्रयोग से उत्पन्न होता है, उसके आधार पर उनकी अतिरिक्त संरचना हो सकती है; उदाहरण के लिए, सिमेंटिक नेटवर्क एक ग्राफ़ है जिसमें शीर्ष वस्तुओं की अवधारणाओं या वर्गों का प्रतिनिधित्व करते हैं।
एक किनारे को बनाने वाले दो शीर्षों को इस किनारे का अंतिम बिंदु कहा जाता है, और किनारे को शीर्षों पर आपतित कहा जाता है। यदि ग्राफ़ में एक किनारा (v,w) है तो एक शीर्ष w को दूसरे शीर्ष v के निकट कहा जाता है। शीर्ष 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.
