लूप (ग्राफ सिद्धांत): Difference between revisions
From Vigyanwiki
(→डिग्री) |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Edge that connects a node to itself}} | {{Short description|Edge that connects a node to itself}} | ||
[[Image:6n-graph2.svg|thumb|शीर्ष 1 पर एक लूप वाला ग्राफ़]]ग्राफ़ सिद्धांत में, | [[Image:6n-graph2.svg|thumb|शीर्ष 1 पर एक लूप वाला ग्राफ़]]ग्राफ़ सिद्धांत में, '''लूप''' (जिसे '''सेल्फ-लूप''' या ''बकल'' भी कहा जाता है) एक किनारा है जो एक शीर्ष को अपने आप से जोड़ता है। साधारण [[ग्राफ़ (अलग गणित)|ग्राफ़]] में कोई लूप नहीं है। | ||
संदर्भ के आधार पर, | संदर्भ के आधार पर, ग्राफ या [[मल्टीग्राफ]] को परिभाषित किया जा सकता है ताकि या तो लूप की उपस्थिति की अनुमति दें या अनुमति न दें (प्रायः एक ही शीर्ष के बीच एकाधिक किनारों को अनुमति देने या अस्वीकार करने के साथ मिलकर): | ||
* जहां ग्राफ़ को इस तरह से परिभाषित किया जाता है कि लूप और एकाधिक किनारों की ''अनुमति'' दी जा सके, लूप या एकाधिक किनारों के बिना ग्राफ़ को | * जहां ग्राफ़ को इस तरह से परिभाषित किया जाता है कि लूप और एकाधिक किनारों की ''अनुमति'' दी जा सके, लूप या एकाधिक किनारों के बिना ग्राफ़ को प्रायः ''साधारण ग्राफ़'' कहकर अन्य ग्राफ़ से अलग किया जाता है। | ||
*जहां ग्राफ़ को इस प्रकार परिभाषित किया जाता है कि लूप और एकाधिक किनारों की ''अनुमति नहीं'' दी जाती है, | *जहां ग्राफ़ को इस प्रकार परिभाषित किया जाता है कि लूप और एकाधिक किनारों की ''अनुमति नहीं'' दी जाती है, ग्राफ़ जिसमें लूप या एकाधिक किनारे होते हैं, उसे प्रायः उन ग्राफ़ से अलग किया जाता है जो इन बाधाओं को ''मल्टीग्राफ'' या ''स्यूडोग्राफ'' कहकर संतुष्ट करते हैं। | ||
एक शीर्ष वाले ग्राफ में, सभी किनारों को लूप होना चाहिए। इस तरह के ग्राफ को बुके कहा जाता है। | एक शीर्ष वाले ग्राफ में, सभी किनारों को लूप होना चाहिए। इस तरह के ग्राफ को बुके कहा जाता है। | ||
==डिग्री (अंश)== | ==डिग्री (अंश)== | ||
[[अप्रत्यक्ष ग्राफ|अप्रत्यक्ष]] ग्राफ के लिए, शीर्ष की डिग्री [[आसन्न शीर्ष|आसन्न]] शीर्षों की संख्या के बराबर होती है। | |||
एक विशेष | एक विशेष स्तिथि एक लूप है, जो डिग्री में दो जोड़ता है। इसे लूप एज के प्रत्येक कनेक्शन को उसके स्वयं के आसन्न शीर्ष के रूप में गिनने देकर समझा जा सकता है। दूसरे शब्दों में, लूप वाला शीर्ष खुद को किनारे के ''दोनों'' सिरों से आसन्न शीर्ष के रूप में "देखता" है और इस प्रकार डिग्री में एक नहीं बल्कि दो जुड़ जाते हैं। | ||
[[निर्देशित ग्राफ|निर्देशित]] ग्राफ के लिए, लूप को इन डिग्री और एक को आउट डिग्री में जोड़ता है। | |||
==यह भी देखें== | ==यह भी देखें== | ||
Revision as of 23:45, 19 July 2023
ग्राफ़ सिद्धांत में, लूप (जिसे सेल्फ-लूप या बकल भी कहा जाता है) एक किनारा है जो एक शीर्ष को अपने आप से जोड़ता है। साधारण ग्राफ़ में कोई लूप नहीं है।
संदर्भ के आधार पर, ग्राफ या मल्टीग्राफ को परिभाषित किया जा सकता है ताकि या तो लूप की उपस्थिति की अनुमति दें या अनुमति न दें (प्रायः एक ही शीर्ष के बीच एकाधिक किनारों को अनुमति देने या अस्वीकार करने के साथ मिलकर):
- जहां ग्राफ़ को इस तरह से परिभाषित किया जाता है कि लूप और एकाधिक किनारों की अनुमति दी जा सके, लूप या एकाधिक किनारों के बिना ग्राफ़ को प्रायः साधारण ग्राफ़ कहकर अन्य ग्राफ़ से अलग किया जाता है।
- जहां ग्राफ़ को इस प्रकार परिभाषित किया जाता है कि लूप और एकाधिक किनारों की अनुमति नहीं दी जाती है, ग्राफ़ जिसमें लूप या एकाधिक किनारे होते हैं, उसे प्रायः उन ग्राफ़ से अलग किया जाता है जो इन बाधाओं को मल्टीग्राफ या स्यूडोग्राफ कहकर संतुष्ट करते हैं।
एक शीर्ष वाले ग्राफ में, सभी किनारों को लूप होना चाहिए। इस तरह के ग्राफ को बुके कहा जाता है।
डिग्री (अंश)
अप्रत्यक्ष ग्राफ के लिए, शीर्ष की डिग्री आसन्न शीर्षों की संख्या के बराबर होती है।
एक विशेष स्तिथि एक लूप है, जो डिग्री में दो जोड़ता है। इसे लूप एज के प्रत्येक कनेक्शन को उसके स्वयं के आसन्न शीर्ष के रूप में गिनने देकर समझा जा सकता है। दूसरे शब्दों में, लूप वाला शीर्ष खुद को किनारे के दोनों सिरों से आसन्न शीर्ष के रूप में "देखता" है और इस प्रकार डिग्री में एक नहीं बल्कि दो जुड़ जाते हैं।
निर्देशित ग्राफ के लिए, लूप को इन डिग्री और एक को आउट डिग्री में जोड़ता है।
यह भी देखें
ग्राफ़ सिद्धांत में
- चक्र (ग्राफ सिद्धांत)
- ग्राफ सिद्धांत
- ग्राफ सिद्धांत की शब्दावली
टोपोलॉजी में
- मोबियस लैडर
- मोबियस स्ट्रिप
- वियर्ड लूप
- क्लेन बॉटल
संदर्भ
- Balakrishnan, V. K.; Graph Theory, McGraw-Hill; 1 edition (February 1, 1997). ISBN 0-07-005489-4.
- Bollobás, Béla; Modern Graph Theory, Springer; 1st edition (August 12, 2002). ISBN 0-387-98488-7.
- Diestel, Reinhard; Graph Theory, Springer; 2nd edition (February 18, 2000). ISBN 0-387-98976-5.
- Gross, Jonathon L, and Yellen, Jay; Graph Theory and Its Applications, CRC Press (December 30, 1998). ISBN 0-8493-3982-0.
- Gross, Jonathon L, and Yellen, Jay; (eds); Handbook of Graph Theory. CRC (December 29, 2003). ISBN 1-58488-090-2.
- Zwillinger, Daniel; CRC Standard Mathematical Tables and Formulae, Chapman & Hall/CRC; 31st edition (November 27, 2002). ISBN 1-58488-291-3.
बाहरी संबंध
This article incorporates public domain material from Black, Paul E. "Self loop". Dictionary of Algorithms and Data Structures.
