वर्टेक्स (ग्राफ़ सिद्धांत): Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Fundamental unit of which graphs are formed}}[[Image:6n-graf.svg|thumb|6 शीर्षों और 7 किनारों वाला एक ग्राफ़ जहां सबसे बाईं ओर शीर्ष संख्या 6 एक पत्ती शीर्ष या एक लटकता हुआ शीर्ष है]]असतत गणित में | {{Short description|Fundamental unit of which graphs are formed}}[[Image:6n-graf.svg|thumb|6 शीर्षों और 7 किनारों वाला एक ग्राफ़ जहां सबसे बाईं ओर शीर्ष संख्या 6 एक पत्ती शीर्ष या एक लटकता हुआ शीर्ष है]]असतत गणित में और अधिक विशेष रूप से ग्राफ़ सिद्धांत में, एक '''शीर्ष''' (बहुवचन '''शीर्ष''') या '''नोड''' वह मूलभूत इकाई है जिससे ग्राफ़ बनते हैं: एक अप्रत्यक्ष ग्राफ़ में शीर्षों का एक सेट और किनारों का एक सेट (शीर्षों के अव्यवस्थित जोड़े) होते है जबकि एक [[निर्देशित ग्राफ]] में शीर्षों का एक सेट और चापों का एक सेट (शीर्षों के क्रमबद्ध जोड़े) होते हैं। ग्राफ़ के आरेख में, एक शीर्ष को सामान्यतः एक लेबल के साथ एक वृत्त द्वारा दर्शाया जाता है और एक किनारे को एक शीर्ष से दूसरे तक फैली हुई रेखा या तीर द्वारा दर्शाया जाता है। | ||
ग्राफ़ सिद्धांत के दृष्टिकोण से, शीर्षों को सुविधाहीन और अविभाज्य [[गणितीय वस्तु]] के रूप में माना जाता है, | ग्राफ़ सिद्धांत के दृष्टिकोण से, शीर्षों को सुविधाहीन और अविभाज्य [[गणितीय वस्तु|गणितीय वस्तुओं]] के रूप में माना जाता है, चूँकि ग्राफ़ जिस अनुप्रयोग से उत्पन्न होता है, उसके आधार पर उनकी अतिरिक्त संरचना हो सकती है; उदाहरण के लिए, [[सिमेंटिक नेटवर्क]] एक ग्राफ़ है जिसमें शीर्ष वस्तुओं की अवधारणाओं या वर्गों का प्रतिनिधित्व करते हैं। | ||
एक किनारे को बनाने वाले दो शीर्षों को इस किनारे का अंतिम बिंदु कहा जाता है | एक किनारे को बनाने वाले दो शीर्षों को इस किनारे का अंतिम बिंदु कहा जाता है और किनारे को शीर्षों पर आपतित कहा जाता है। यदि ग्राफ़ में एक किनारा (''v'',''w'') है तो एक शीर्ष ''w'' को दूसरे शीर्ष ''v'' के निकट कहा जाता है। शीर्ष ''v'' का निकटतम (ग्राफ़ सिद्धांत) ग्राफ़ का एक प्रेरित उपसमूह है, जो ''v'' के निकटवर्ती सभी शीर्षों द्वारा बनता है। | ||
==शीर्षों के प्रकार== | ==शीर्षों के प्रकार== | ||
[[File:Small Network.png|alt=A small example network with 8 vertices and 10 edges.|अंगूठा|8 शीर्षों (जिनमें से एक अलग है) और 10 किनारों वाला उदाहरण नेटवर्क।]]किसी शीर्ष की डिग्री (ग्राफ़ सिद्धांत), जिसे ग्राफ़ में 𝛿( | [[File:Small Network.png|alt=A small example network with 8 vertices and 10 edges.|अंगूठा|8 शीर्षों (जिनमें से एक अलग है) और 10 किनारों वाला उदाहरण नेटवर्क।]]किसी शीर्ष की डिग्री (ग्राफ़ सिद्धांत), जिसे ग्राफ़ में 𝛿(वी) दर्शाया जाता है, उस पर पड़ने वाले किनारों की संख्या है। एक '''पृथक शीर्ष''' शून्य डिग्री वाला एक शीर्ष है; अर्थात्, एक शीर्ष जो किसी किनारे का समापन बिंदु नहीं है (उदाहरण छवि एक अलग शीर्ष को दर्शाती है)।<ref>[[:File:Small Network.png]]; example image of a network with 8 vertices and 10 edges</ref> एक '''पत्ती शीर्ष''' ('''पेंडेंट शीर्ष''' भी) एक डिग्री वाला शीर्ष है। एक निर्देशित ग्राफ़ में, कोई आउटडिग्री (आउटगोइंग किनारों की संख्या)‚ जिसे 𝛿 +(v) के रूप में दर्शाया जाता है, को इंडिग्री (आने वाले किनारों की संख्या) से, जिसे 𝛿−(v) के रूप में दर्शाया जाता है, में अंतर कर सकता है; एक '''स्रोत शीर्ष''' इंडिग्री शून्य वाला एक शीर्ष है, जबकि एक '''सिंक शीर्ष''' आउटडिग्री शून्य वाला एक शीर्ष है। एक '''सरल शीर्ष''' वह है जिसके निकटतम एक समूह बनाते हैं (ग्राफ़ सिद्धांत): प्रत्येक दो निकटतम आसन्न होते हैं। एक [[सार्वभौमिक शीर्ष]] वह शीर्ष है जो ग्राफ़ में हर दूसरे शीर्ष के निकट होता है। | ||
एक कट शीर्ष एक शीर्ष है जिसे हटाने से शेष ग्राफ़ डिस्कनेक्ट हो जाएगा; एक [[शीर्ष विभाजक]] शीर्षों का एक संग्रह है जिसे हटाने से शेष ग्राफ़ छोटे टुकड़ों में अलग हो जाएगा। [[के-वर्टेक्स-कनेक्टेड ग्राफ़]] एक ऐसा ग्राफ़ है जिसमें ''k'' से कम कोने हटाने पर शेष ग्राफ़ हमेशा जुड़ा रहता है। एक [[स्वतंत्र सेट (ग्राफ़ सिद्धांत)]] शीर्षों का एक सेट है, जिनमें से कोई भी दो आसन्न नहीं हैं | एक कट शीर्ष एक शीर्ष है जिसे हटाने से शेष ग्राफ़ डिस्कनेक्ट हो जाएगा; एक [[शीर्ष विभाजक]] शीर्षों का एक संग्रह है जिसे हटाने से शेष ग्राफ़ छोटे टुकड़ों में अलग हो जाएगा। [[के-वर्टेक्स-कनेक्टेड ग्राफ़]] एक ऐसा ग्राफ़ है जिसमें ''k'' से कम कोने हटाने पर शेष ग्राफ़ हमेशा जुड़ा रहता है। एक [[स्वतंत्र सेट (ग्राफ़ सिद्धांत)]] शीर्षों का एक सेट है, जिनमें से कोई भी दो आसन्न नहीं हैं और एक [[शीर्ष आवरण]] शीर्षों का एक सेट है जिसमें ग्राफ़ में प्रत्येक किनारे का कम से कम एक समापन बिंदु सम्मिलित होता है। ग्राफ़ का [[शीर्ष स्थान]] एक सदिश स्थान है जिसमें ग्राफ़ के शीर्षों के अनुरूप आधार वैक्टर का एक सेट होता है। | ||
एक ग्राफ़ [[शीर्ष-संक्रमणीय ग्राफ | एक ग्राफ़ [[शीर्ष-संक्रमणीय ग्राफ|शीर्ष-संक्रमणीय]] होता है यदि इसमें समरूपताएं होती हैं जो किसी भी शीर्ष को किसी अन्य शीर्ष पर मैप करती हैं। [[ग्राफ गणना]] और [[ग्राफ समरूपता]] के संदर्भ में लेबल वाले शीर्षों और बिना '''लेबल वाले शीर्षों''' और '''बिना लेबल वाले शीर्षों''' के बीच अंतर करना महत्वपूर्ण है। एक लेबल वाला शीर्ष एक ऐसा शीर्ष है जो अतिरिक्त जानकारी से जुड़ा होता है जो इसे अन्य लेबल वाले शीर्षों से अलग करने में सक्षम बनाता है; दो ग्राफ़ों को समरूपी तभी माना जा सकता है जब उनके शीर्षों के बीच का पत्राचार समान लेबल वाले शीर्षों को जोड़ता है। एक बिना लेबल वाला शीर्ष वह है जिसे किसी अन्य शीर्ष के लिए केवल ग्राफ़ में उसकी [[आसन्नता (ग्राफ़ सिद्धांत)]] के आधार पर प्रतिस्थापित किया जा सकता है, न कि किसी अतिरिक्त जानकारी के आधार पर प्रतिस्थापित होता हैं। | ||
ग्राफ़ में शीर्ष, [[शीर्ष (ज्यामिति)]] के अनुरूप होते हैं, | ग्राफ़ में शीर्ष, [[शीर्ष (ज्यामिति)]] के अनुरूप होते हैं, किन्तु समान नहीं होते हैं: एक पॉलीहेड्रॉन का [[कंकाल (टोपोलॉजी)]] एक ग्राफ बनाता है, जिसके शीर्ष पॉलीहेड्रॉन के शीर्ष होते हैं, किन्तु पॉलीहेड्रॉन के शीर्षों में अतिरिक्त संरचना (उनकी ज्यामितीय स्थिति) होती है जिसे ग्राफ़ सिद्धांत में उपस्तिथ नहीं माना जाता है। एक बहुफलक में एक शीर्ष का शीर्ष आंकड़ा एक ग्राफ में एक शीर्ष के पड़ोस के अनुरूप होता है। | ||
==यह भी देखें== | ==यह भी देखें== | ||
Revision as of 08:44, 4 July 2023
असतत गणित में और अधिक विशेष रूप से ग्राफ़ सिद्धांत में, एक शीर्ष (बहुवचन शीर्ष) या नोड वह मूलभूत इकाई है जिससे ग्राफ़ बनते हैं: एक अप्रत्यक्ष ग्राफ़ में शीर्षों का एक सेट और किनारों का एक सेट (शीर्षों के अव्यवस्थित जोड़े) होते है जबकि एक निर्देशित ग्राफ में शीर्षों का एक सेट और चापों का एक सेट (शीर्षों के क्रमबद्ध जोड़े) होते हैं। ग्राफ़ के आरेख में, एक शीर्ष को सामान्यतः एक लेबल के साथ एक वृत्त द्वारा दर्शाया जाता है और एक किनारे को एक शीर्ष से दूसरे तक फैली हुई रेखा या तीर द्वारा दर्शाया जाता है।
ग्राफ़ सिद्धांत के दृष्टिकोण से, शीर्षों को सुविधाहीन और अविभाज्य गणितीय वस्तुओं के रूप में माना जाता है, चूँकि ग्राफ़ जिस अनुप्रयोग से उत्पन्न होता है, उसके आधार पर उनकी अतिरिक्त संरचना हो सकती है; उदाहरण के लिए, सिमेंटिक नेटवर्क एक ग्राफ़ है जिसमें शीर्ष वस्तुओं की अवधारणाओं या वर्गों का प्रतिनिधित्व करते हैं।
एक किनारे को बनाने वाले दो शीर्षों को इस किनारे का अंतिम बिंदु कहा जाता है और किनारे को शीर्षों पर आपतित कहा जाता है। यदि ग्राफ़ में एक किनारा (v,w) है तो एक शीर्ष 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.
