व्याख्यान 4. रेखांकन

4.1.ग्राफ़. परिभाषा, ग्राफ़ के प्रकार

4.2. ग्राफ़ के गुण

कार्यक्रम प्रावधान

ग्राफ सिद्धांत में बढ़ती रुचि के कई कारण हैं। यह एक निर्विवाद तथ्य है कि ग्राफ सिद्धांत का उपयोग भौतिकी, रसायन विज्ञान, संचार सिद्धांत, कंप्यूटर डिजाइन, इलेक्ट्रिकल इंजीनियरिंग, मैकेनिकल इंजीनियरिंग, वास्तुकला, संचालन अनुसंधान, आनुवंशिकी, मनोविज्ञान, समाजशास्त्र, अर्थशास्त्र, मानव विज्ञान और भाषा विज्ञान जैसे क्षेत्रों में किया जाता है। यह सिद्धांत गणित की कई शाखाओं से भी निकटता से संबंधित है, जिसमें समूह सिद्धांत, मैट्रिक्स सिद्धांत, संख्यात्मक विश्लेषण, संभाव्यता सिद्धांत, टोपोलॉजी और कॉम्बिनेटरियल विश्लेषण शामिल हैं। यह भी निश्चित है कि ग्राफ़ सिद्धांत द्विआधारी संबंध वाले किसी भी सिस्टम के लिए गणितीय मॉडल के रूप में कार्य करता है। रेखाचित्रों के रूप में प्रस्तुत किए जाने के कारण ग्राफ़ आकर्षक और सौंदर्य की दृष्टि से मनभावन होते हैं। यद्यपि ग्राफ़ सिद्धांत में ऐसे कई परिणाम शामिल हैं जो प्रकृति में प्राथमिक हैं, इसमें सबसे परिष्कृत गणितज्ञों के ध्यान के योग्य बहुत ही सूक्ष्म संयोजक समस्याओं की एक विशाल बहुतायत भी शामिल है। (एफ. हरारी "ग्राफ थ्योरी")

लागू समस्याओं में ग्राफ़ के व्यापक उपयोग की सुविधा और संभावना पर ध्यान दें

साहित्य

सुरक्षा प्रश्न

1. ग्राफ क्या है?
2. ग्राफ़ का शीर्ष और किनारा किसे कहते हैं?

3. क्या पेंसिल को उठाए बिना और किसी भी किनारे से दो बार गुजरे बिना इस आरेख का पता लगाना संभव है?

1. क्या ग्राफ़ के शीर्षों की डिग्री का योग एक विषम संख्या हो सकता है?
2. क्या 11 टीमों के बीच एक टूर्नामेंट आयोजित करना संभव है, ताकि प्रत्येक टीम ठीक 5 मैच खेले?

6. पैराग्राफ 4.1.(6) से परिभाषाओं की समानता दिखाएं (कि वे एक ही वस्तु का वर्णन करते हैं)

7.दिखाएँ कि ग्राफ समरूपी हैं

8. दिखाएँ कि समरूपता ग्राफ़ पर एक तुल्यता संबंध है।

9. तार के एक टुकड़े को न्यूनतम कितने भागों में विभाजित करने की आवश्यकता है ताकि इसका उपयोग क्यूब फ्रेम बनाने के लिए किया जा सके?

10. दिखाएँ कि ग्राफ समतलीय है

रेखांकन. परिभाषा, ग्राफ़ के प्रकार

ग्राफ़ सिद्धांत के जनक एल. यूलर ए707-1782) हैं, जिन्होंने 1736 में एक समस्या हल की थी जो उस समय व्यापक रूप से ज्ञात थी, जिसे कोनिग्सबर्ग पुलों की समस्या कहा जाता था।

कोएनिग्सबर्ग शहर में दो द्वीप थे जो सात पुलों द्वारा प्रागोलिया नदी के किनारे और एक दूसरे से जुड़े हुए थे जैसा कि चित्र में दिखाया गया है। 4.1.(1) (ए,डी - द्वीप, बी,सी - नदी तट)। कार्य इस प्रकार था: भूमि के सभी चार हिस्सों के माध्यम से एक मार्ग खोजना, जो उनमें से किसी एक से शुरू हो, उसी हिस्से पर समाप्त हो और प्रत्येक पुल के ऊपर से ठीक एक बार गुजरे। बेशक, इस समस्या को सभी मार्गों से खोजकर, अनुभवजन्य रूप से हल करने का प्रयास करना आसान है, लेकिन सभी प्रयास विफलता में समाप्त होंगे। एल. यूलर ऐसे मार्ग की असंभवता को साबित करके इस समस्या का समाधान खोजने में कामयाब रहे।

यह साबित करने के लिए कि समस्या का कोई समाधान नहीं है, यूलर ने भूमि के प्रत्येक भाग को एक बिंदु (शीर्ष) के साथ नामित किया, और प्रत्येक पुल को संबंधित बिंदुओं को जोड़ने वाली एक रेखा (किनारे) के साथ नामित किया। परिणाम एक "ग्राफ़" है. यह ग्राफ़ चित्र में दिखाया गया है। 4.1.(2), जहां अंक

चित्र में सुशी के चार टुकड़ों के समान अक्षरों से चिह्नित किया गया है। 4.1(1). इस समस्या के "सकारात्मक" समाधान की गैर-मौजूदगी के बारे में बयान चित्र 1 में प्रस्तुत ग्राफ़ को एक विशेष तरीके से पार करने की असंभवता के बारे में बयान के बराबर है। 4.1(2).

इस मामले में, समस्या निम्नलिखित सूत्रीकरण पर आधारित है: किसी भी शीर्ष से शुरू करके, प्रत्येक किनारे से केवल एक बार गुजरते हुए, मूल शीर्ष पर वापस लौटें।

एक अन्य समस्या का उदाहरण जिसे ग्राफ़ सिद्धांत का उपयोग करके तैयार किया जा सकता है वह तीन घरों को तीन प्रकार की उपयोगिताओं की आपूर्ति करने की समस्या है। समस्या के अनुसार, तीनों घरों में से प्रत्येक को भूमिगत पाइप लाइनों और केबलों के माध्यम से तीन प्रकार की उपयोगिताओं, उदाहरण के लिए, पानी, गैस और बिजली से जोड़ा जाना चाहिए। सवाल यह है कि क्या आपूर्ति लाइनों को पार किए बिना इन तीन घरों को उपयोगिताएँ प्रदान करना संभव है। इस समस्या का मॉडलिंग करने वाला ग्राफ़ चित्र में दिखाया गया है। 4.1(3) (यह सुप्रसिद्ध मॉडल समस्या कभी-कभी घरों और कुओं की समस्या के रूप में तैयार की जाती है)

अधिक व्यावहारिक प्रकृति की एक समान समस्या माइक्रो-सर्किट बनाते समय उत्पन्न होती है। उनमें प्रत्येक स्तर पर तारों को पार करना अवांछनीय है।

परिभाषा 4.1(1)

एक ग्राफ़ एक परिमित समुच्चय V है, जिसे शीर्षों का समुच्चय कहा जाता है, और समुच्चय V के दो-तत्व उपसमुच्चय का समुच्चय E होता है। समुच्चय E को किनारों का समुच्चय कहा जाता है। समुच्चय E के एक तत्व को किनारा कहा जाता है। ग्राफ को G(V, E) द्वारा निरूपित किया जाता है। समुच्चय V के तत्व a और b को कनेक्टेड कहा जाता है, या एक किनारे (a, b) द्वारा कनेक्टेड कहा जाता है, यदि।

दूसरे शब्दों में, एक ग्राफ एक आरेख है जिसमें बिंदु होते हैं, जिनमें से कुछ खंडों से जुड़े होते हैं।

ग्राफ़ के उदाहरण मेट्रो मानचित्र, पारिवारिक वृक्ष, रोड मैप आदि हैं।

परिभाषाएँ 4.1(2)

यदि (a, b) एक किनारा है, तो शीर्ष a और b किनारे (a, b) के सिरे कहलाते हैं। एज (ए, बी) भी कहा जाता है आकस्मिकशीर्ष a और b तक. इसके विपरीत, हम कहते हैं कि शीर्ष a और b किनारे (a, b) पर आपतित हैं। दो शिखर कहलाते हैं निकटवर्ती (पड़ोसी)), यदि वे एक किनारे के सिरे हैं, या, वही है, यदि वे एक ही किनारे पर आपतित हैं। दो किनारों को आसन्न कहा जाता है यदि वे एक उभयनिष्ठ शीर्ष पर आपतित हों।

यदि दो बिंदुओं के बीच एकाधिक किनारों की अनुमति है, तो ग्राफ़ कहा जाता है मल्टीग्राफ.

यदि किसी ग्राफ़ में सभी शीर्ष आसन्न हैं, तो ग्राफ़ कहलाता है पूरा.

एक शीर्ष और बिना किनारों वाला एक ग्राफ़ (जिसमें 1 बिंदु - एक शीर्ष होता है) कहलाता है मामूली।

परिभाषा 4.1(3)

एक शीर्ष v की डिग्री को deg(v) द्वारा दर्शाया जाता है, जो इस शीर्ष पर पड़ने वाले (इससे निकलने वाले) किनारों की संख्या है।

डिग्री 0 का एक शीर्ष (अर्थात, शीर्ष से कोई किनारा नहीं निकलता है, यह एक "अकेला" बिंदु है) को पृथक कहा जाता है।

डिग्री 1 के शीर्ष को लटकता हुआ शीर्ष कहा जाता है।

शीर्ष सम या विषम हो सकते हैं।

परिभाषाएँ 4.1.(4)

पथ (शीर्षों के बीच) - किनारों और उन्हें जोड़ने वाले मध्यवर्ती शीर्षों का एक क्रम

पथ की लंबाई - पथ में शामिल किनारों की संख्या

सरल पथ वह पथ है जिसके सभी किनारे और शीर्ष अलग-अलग होते हैं

एक चक्र (लूप) गैर-शून्य लंबाई का एक बंद पथ है जिसमें शुरुआत को छोड़कर सभी शीर्ष अलग-अलग होते हैं, जो अंत के साथ मेल खाता है

उदाहरण 4.1(1).

1. शीर्षों के सेट V = (a,b,c) और किनारों के सेट E ((a, b), (b, c)) के साथ एक ग्राफ को चित्र 4.1(4) में दिखाए अनुसार चित्रित किया जा सकता है (सरल) ) शीर्ष a और c के बीच के पथ में किनारे (a,b), (b,c) और शीर्ष c शामिल हैं

नोट: दोनों तस्वीरें एक ही स्थिति को दर्शाती हैं। ग्राफ़ के दृष्टिकोण से, जो सबसे पहले मायने रखता है वह है बिंदुओं के बीच संबंध का अस्तित्व, न कि उसकी ज्यामिति।

2. वी = (ए, बी, सी, डी, ई) और ई = ((ए, बी), (ए, ई), (बी, ई), (बी, डी), (बी, सी) के साथ एक ग्राफ ), (सी, डी)),

चित्र में दिखाए गए चित्र द्वारा दर्शाया जा सकता है। 4.1.(5). ग्राफ़ में दो चक्र हैं (बी, ई, ए), (बी, सी, डी)।

3. चित्र में। 4.1.(6) शीर्ष a और c आसन्न हैं और e 1, e 2 और e 3 आसन्न किनारे हैं, शीर्ष a और f आसन्न नहीं हैं, और e 2 और e 5 आसन्न किनारे नहीं हैं। शीर्ष b, c और d की घात 2 है, जबकि शीर्ष a और f की घात 3 है।

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

पहले मामले में, सभी शीर्षों की डिग्री सम होनी चाहिए, दूसरे में, प्रवेश और निकास को छोड़कर, सभी शीर्षों की डिग्री सम होनी चाहिए।

उदाहरण 4.1.(2)

क्या चित्र में दिए गए ग्राफ़ को देखना संभव है? 4.1(4), दो बार बिना छोड़े या किसी भी किनारे से गुजरे बिना?

डिग्री 3 वाले शीर्ष c और j को छोड़कर, सभी शीर्षों की अंश सम हैं। तदनुसार, एकमात्र ट्रैवर्सल पथ वह है जिसके आरंभ और अंत में शीर्ष c और j हैं (या इसके विपरीत)

कई मामलों में, आपको ऐसे ग्राफ़ की आवश्यकता होती है जिनके किनारे अनिवार्य रूप से एक-तरफ़ा सड़क हों। इसका मतलब यह है कि यदि किसी किनारे को शीर्ष a से शीर्ष b तक जाता हुआ माना जाता है, तो इसे शीर्ष b से शीर्ष a तक जाता हुआ नहीं माना जा सकता है। उदाहरण के लिए, यदि ग्राफ एक पाइपलाइन में तेल के प्रवाह को दर्शाता है, और यदि तेल बिंदु ए से बिंदु बी तक बहता है, तो हम नहीं चाहेंगे कि यह विपरीत दिशा में, बिंदु बी से बिंदु ए तक बहे।

परिभाषा 4.1(5)

निर्देशित ग्राफ या डिग्राफ जी, जिसे जी(वी, ई) द्वारा निरूपित किया जाता है, इसमें शीर्षों का एक सेट वी और वाई से तत्वों के क्रमित जोड़े का एक सेट ई होता है, जिसे उन्मुख किनारों या बस किनारों का सेट कहा जाता है, अगर यह स्पष्ट है कि ग्राफ उन्मुख है। सेट E के एक तत्व को ओरिएंटेड एज कहा जाता है। यदि, तो a को किनारे (a, b) का प्रारंभिक शीर्ष कहा जाता है, b को अंतिम शीर्ष कहा जाता है।

उदाहरण 4.1(3)

एक डिग्राफ जिसके लिए V = (a, b, c, d] और E = ((a, b), (b, c), (c, c), (c, d), (d,b),( c,d),(d,a)) चित्र में दिखाया गया है।

परिभाषा 4.1.(6)

आइए ट्री ग्राफ़ की कई समकक्ष परिभाषाओं पर विचार करें।

1) यह एक कनेक्टेड ग्राफ़ है जिसमें कोई चक्र नहीं है (कनेक्टिविटी प्रॉपर्टी के बारे में, 4.2 देखें।)

2) एक ग्राफ जिसमें कोई भी 2 शीर्ष एक सरल पथ से जुड़े हुए हैं

3) एक कनेक्टेड ग्राफ़ जो किसी भी किनारे को हटा दिए जाने पर कनेक्टिविटी खो देता है

4) एक ग्राफ जिसमें शीर्षों की तुलना में 1 किनारे कम हैं

पेड़ों के उदाहरण:

एक पर्याप्त रूप से विकसित वंश वृक्ष एक वृक्ष बनता है। यदि आप एक विशिष्ट (प्रसिद्ध) व्यक्ति से शुरुआत करते हैं और प्रत्येक माता-पिता और प्रत्येक बेटे या बेटी के बीच किनारा बनाते हैं, तो यह एक पेड़ बन जाएगा। हालाँकि, पारिवारिक वृक्ष का निर्माण करते समय, यह सुनिश्चित करने के लिए बहुत सावधानी बरतनी चाहिए कि दूर के रिश्तेदारों के बीच विवाह चक्र न बनें।

ग्राफ़ के गुण

प्रमेय 4.2(1).

ग्राफ़ के शीर्षों की डिग्री का योग सदैव सम होता है।

सबूत

चूँकि ग्राफ़ के प्रत्येक किनारे के दो सिरे होते हैं, एक किनारे की कीमत पर प्रत्येक सिरे की डिग्री 1 बढ़ जाती है। इस प्रकार, प्रत्येक किनारा सभी शीर्षों की डिग्री के योग में 2 इकाइयों का योगदान देता है, इसलिए योग किनारों की संख्या से दोगुना होना चाहिए। इसलिए, योग एक सम संख्या है।

प्रमेय 4.2.(2)

किसी भी ग्राफ़ में विषम डिग्री के शीर्षों की संख्या सम होती है।

सबूत

हम विरोधाभास द्वारा प्रमाण को आगे बढ़ाएंगे: यह मानते हुए कि प्रमेय सत्य नहीं है, हम एक विरोधाभास पाएंगे जिससे यह पता चलेगा कि प्रमेय सत्य है। यदि प्रमेय सत्य नहीं है, तो विषम संख्या में शीर्ष हैं जिनकी डिग्री विषम हैं। लेकिन सम अंशों वाले शीर्षों की अंशों का योग भी सम होता है। सभी शीर्षों की डिग्री का योग विषम डिग्री वाले शीर्षों की डिग्री और सम डिग्री वाले शीर्षों की डिग्री का योग है। चूँकि एक विषम संख्या और एक सम संख्या का योग एक विषम संख्या है, इसलिए सभी शीर्षों की डिग्री का योग विषम है। लेकिन यह प्रमेय 4.1(1) का खंडन करता है, इसलिए हम एक विरोधाभास पर पहुंच गए हैं। इसलिए, हम यह निष्कर्ष निकालते हैं कि प्रमेय सत्य है।

उदाहरण 4.2.(1)

क्या 7 टीमों के बीच एक फुटबॉल टूर्नामेंट आयोजित करना संभव है ताकि प्रत्येक टीम ठीक 3 मैच खेले?

नहीं, क्योंकि यदि हम 7 शीर्षों के साथ एक ग्राफ़ बनाते हैं, और प्रत्येक शीर्ष से 3 किनारे प्राप्त करने का प्रयास करते हैं। प्रमेय 4.2(2) के अनुसार ऐसा ग्राफ बनाना असंभव है।

परिभाषा 4.2(1).

समान संरचना वाले ग्राफ़ को आइसोमोर्फिक कहा जाता है। दो ग्राफ़ G और H समरूपी (या कभी-कभी G=H लिखे जाते हैं) हैं यदि उनके शीर्षों के सेट के बीच एक-से-एक पत्राचार है जो आसन्नता को संरक्षित करता है। उदाहरण के लिए, चित्र में G और H। 4. 2(2) अनुरूपता के अंतर्गत समरूपी हैं।

दूसरे शब्दों में, ऐसे प्रत्येक ग्राफ़ के शीर्षों को इस प्रकार क्रमांकित किया जा सकता है कि शीर्षों को इस प्रकार क्रमांकित किया जा सकता है कि इसके शीर्ष पड़ोसी हों यदि और केवल यदि वे दूसरे में पड़ोसी हों।

ध्यान दें कि समरूपता ग्राफ़ पर एक तुल्यता संबंध है।

परिभाषाएँ 4.2(2)

ग्राफ कहा जाता है सुसंगत, यदि किन्हीं दो शीर्षों के बीच कोई पथ है।

कनेक्टिविटी घटक- ग्राफ़ का एक भाग जो स्वयं जुड़ा हुआ है, लेकिन इसे बढ़ाया नहीं जा सकता ताकि यह जुड़ा रहे

ग्राफ़ G की कनेक्टिविटी x=x(G) शीर्षों की सबसे छोटी संख्या है जिसके हटाने से एक डिस्कनेक्टेड या तुच्छ ग्राफ़ बनता है। परिभाषा से यह पता चलता है कि एक डिस्कनेक्ट किए गए ग्राफ़ की कनेक्टिविटी 0 के बराबर है, और एक जंक्शन बिंदु वाले कनेक्टेड ग्राफ़ की कनेक्टिविटी 1 के बराबर है। एक पूर्ण ग्राफ़ को डिस्कनेक्ट नहीं किया जा सकता है, चाहे कितने भी कोने हटा दिए जाएं यह।

रेखांकन

ग्राफ़ की उत्पत्ति अठारहवीं शताब्दी में हुई जब प्रसिद्ध गणितज्ञ लियोनहार्ड यूलर ने कोनिग्सबर्ग पुलों की अब क्लासिक समस्या को हल करने का प्रयास किया। उस समय कोनिग्सबर्ग शहर में जैसा कि चित्र में दिखाया गया है, दो द्वीप प्रागोल नदी के तट और एक दूसरे से सात पुलों द्वारा जुड़े हुए थे। 7.1. कार्य निम्नलिखित है: शहर के चारों ओर इस तरह से घूमना कि, प्रत्येक पुल पर ठीक एक बार चलने के बाद, आप उसी स्थान पर लौट आएं जहां से चलना शुरू हुआ था। इस समस्या को हल करते हुए, यूलर ने कोएनिग्सबर्ग को एक ग्राफ के रूप में चित्रित किया, जिसमें शहर के कुछ हिस्सों के साथ इसके शिखर और इन हिस्सों को जोड़ने वाले पुलों के साथ इसके किनारों की पहचान की गई। जैसा कि हम § 7.1 में दिखाएंगे, यूलर यह साबित करने में सक्षम था कि शहर के चारों ओर वांछित मार्ग मौजूद नहीं है।

चित्र 7.1. पुराने कोएनिग्सबर्ग की योजना

इस अध्याय में, हम ग्राफ सिद्धांत में प्रयुक्त मानक शब्दावली का परिचय देते हैं और कई विशिष्ट समस्याओं की जांच करते हैं जिन्हें ग्राफ़ का उपयोग करके हल किया जा सकता है। विशेष रूप से, हमें ग्राफ़ के एक वर्ग से परिचित कराया जाएगा जिसे पेड़ कहा जाता है। पेड़ एक प्राकृतिक मॉडल हैं जो एक पदानुक्रमित प्रणाली में व्यवस्थित डेटा का प्रतिनिधित्व करते हैं। अलग-अलग वस्तुओं को अलग करने के लिए पेड़ की खोज करना और एक पेड़ में डेटा को सॉर्ट करना कंप्यूटर विज्ञान में प्रयास के महत्वपूर्ण बिंदु हैं। इस अध्याय के परिशिष्ट में, हम पेड़ों में व्यवस्थित डेटा को क्रमबद्ध और खोजेंगे।

रेखांकन और शब्दावली

चित्र में. 7.1 कोनिग्सबर्ग के सात पुलों को इस प्रकार दिखाता है। वे अठारहवीं शताब्दी में कैसे स्थित थे। यूलर ने जिस समस्या का समाधान किया, वह पूछती है: क्या ऐसा पैदल मार्ग खोजना संभव है जो प्रत्येक पुल के ठीक ऊपर से एक बार गुजरता हो और शहर में एक ही स्थान पर शुरू और समाप्त होता हो?

कार्य मॉडल है ग्राफ,अनेकों से मिलकर बना हुआ चोटियोंऔर कई पसलियाँशीर्षों को जोड़ना. शीर्ष A, B, C और डी नदी के किनारों और द्वीपों और पसलियों का प्रतीक है ए,सी, सी,डी,एफ और जीसात पुलों को निरूपित करें (चित्र 7.2 देखें)। आवश्यक मार्ग (यदि यह मौजूद है) ग्राफ़ के किनारों को इस तरह से पार करने से मेल खाता है कि उनमें से प्रत्येक को केवल एक बार पार किया जाए। पसली का मार्ग स्पष्ट रूप से पुल द्वारा नदी को पार करने से मेल खाता है।

चित्र 7.2. कोनिग्सबर्ग ब्रिज समस्या का मॉडल

एक ग्राफ जिसमें एक मार्ग होता है, एक मार्ग होता है जो एक ही शीर्ष पर शुरू और समाप्त होता है, और ग्राफ के सभी किनारों से ठीक एक बार गुजरता है, कहलाता है सीलर ग्राफ.शीर्षों का क्रम (शायद दोहराव के साथ) जिसके माध्यम से वांछित मार्ग गुजरता है, मार्ग की तरह, कहा जाता है यूलेरियन चक्र. यूलर ने देखा कि यदि किसी ग्राफ़ में एक यूलेरियन चक्र है, तो किसी शीर्ष तक जाने वाले प्रत्येक किनारे के लिए इस शीर्ष 1 को छोड़कर एक और किनारा होना चाहिए, और इस सरल अवलोकन से उन्होंने निम्नलिखित निष्कर्ष निकाला: यदि ग्राफ़ में एक यूलेरियन चक्र है यदि ग्राफ दिया गया है, तो प्रत्येक शीर्ष पर किनारों की संख्या सम होनी चाहिए।

इसके अलावा, यूलर विपरीत कथन को सिद्ध करने में सक्षम था, ताकि एक ग्राफ जिसमें शीर्षों का कोई भी जोड़ा किनारों के किसी अनुक्रम से जुड़ा हो, यूलेरियन है यदि और केवल तभी जब इसके सभी शीर्षों की डिग्री सम हो। डिग्रीशिखर वी संख्या δ(v) कहलाती है पसलियाँ, उसकी घटना 2 .

अब यह बिल्कुल स्पष्ट है कि कोनिग्सबर्ग ब्रिज समस्या के ग्राफ़ मॉडलिंग में, यूलर चक्र नहीं पाया जा सकता है। दरअसल, इसके सभी शीर्षों की डिग्री विषम हैं: δ(बी) = δ(सी)= δ(डी) = 3 और δ(ए) = 5. यूलर की मदद से, पुलों की समस्या को हल करते समय हमने जो अध्ययन किया था, उसके समान ग्राफ़ का उपयोग कई व्यावहारिक समस्याओं को हल करने में किया जाने लगा और उनका अध्ययन गणित के एक महत्वपूर्ण क्षेत्र में विकसित हुआ।

सरल ग्राफजोड़ी G = (V) के रूप में परिभाषित किया गया है ई),जहाँ V शीर्षों का एक सीमित समुच्चय है, और ई- किनारों का एक सीमित सेट, और शामिल नहीं हो सकता छोरों(किनारे एक ही शीर्ष पर शुरू और समाप्त होते हैं) और अनेक किनारे(एकाधिक किनारे शीर्षों के एक ही जोड़े को जोड़ने वाले अनेक किनारे हैं)। चित्र में दिखाया गया ग्राफ। 7.2. सरल नहीं है, क्योंकि, उदाहरण के लिए, शीर्ष एऔर मेंदो किनारों से जुड़े हुए हैं (इन किनारों को एकाधिक कहा जाता है)।

दो शिखर यू और वीएक साधारण ग्राफ़ में कहा जाता है नज़दीक, यदि वे किसी किनारे से जुड़े हों ई, जिसके बारे में वे कहते हैं कि यह है आकस्मिकवर्टेक्स यू (और वी ). इस प्रकार हम अनेकों की कल्पना कर सकते हैं ईकिनारों को आसन्न शीर्षों के जोड़े के एक सेट के रूप में, जिससे सेट पर एक गैर-प्रतिवर्ती, सममित संबंध परिभाषित होता है वीरिफ्लेक्सिविटी की कमी इस तथ्य के कारण है कि एक साधारण ग्राफ में लूप नहीं होते हैं, यानी किनारे, जिसके दोनों सिरे एक ही शीर्ष पर होते हैं। रिश्ते की समरूपता इस तथ्य से उत्पन्न होती है कि किनारा ई, शीर्ष को जोड़ना औरसाथ वी,जोड़ता है और वीसाथ और(दूसरे शब्दों में, किनारे उन्मुख नहीं हैं, यानी उनकी कोई दिशा नहीं है)। एक साधारण ग्राफ़ में शीर्षों की एक जोड़ी को जोड़ने वाला एक किनारा यू और वी,हम इसे इस रूप में निरूपित करेंगे औरवी(या vi).

किसी ग्राफ़ के शीर्षों के समुच्चय पर किसी संबंध का तार्किक मैट्रिक्स, जो उसके किनारों द्वारा परिभाषित होता है, कहलाता है ,सहखंडज मैट्रिक्स।आसन्न मैट्रिक्स M के संदर्भ में किसी संबंध की समरूपता का अर्थ है कि M मुख्य विकर्ण के बारे में सममित. और मैट्रिक्स एम के मुख्य विकर्ण पर इस संबंध की गैर-प्रतिवर्तीता के कारण वहाँ एक प्रतीक है "L"।

उदाहरण 7.1. एक ग्राफ़ G(V, E) बनाएं शीर्षों के समुच्चय V = के साथ (ए, बी, सी, डी, ई) और किनारों का एक सेट ई = (एबी, एई, बीसी, बीडी, सीई, डी)। इसकी आसन्नता मैट्रिक्स लिखिए।

समाधान। ग्राफ़ G चित्र में दिखाया गया है। 7.3.

चित्र 7.3.

इसके आसन्न मैट्रिक्स का रूप है:

ग्राफ़ को पुनर्स्थापित करने के लिए, हमें केवल आसन्न मैट्रिक्स के उन तत्वों की आवश्यकता है जो मुख्य विकर्ण से ऊपर हैं।

सबग्राफग्राफ G = (V, E) को ग्राफ G' = (V', E') कहा जाता है, जिसमें E' C E और V' C V होता है।

उदाहरण 7.2चित्र में दिखाए गए ग्राफ़ H, K और L में से खोजें। 7.4, ग्राफ़ जी के उपग्राफ़।

समाधान।आइए हम ग्राफ G, H और K के शीर्षों को निरूपित करें जैसा कि चित्र में दिखाया गया है। 7.5. ग्राफ़ H और K, G के उपग्राफ़ हैं, जैसा कि हमारे नोटेशन से देखा जा सकता है। ग्राफ़ L, G का उपग्राफ़ नहीं है क्योंकि इसमें सूचकांक 4 के साथ एक शीर्ष है, जबकि G नहीं है।

मार्गलंबाई के ग्राफ G में शीर्षों का ऐसा क्रम कहलाता है वी 0 , वी 1 , …, वी के , प्रत्येक i = 1, …, k जोड़ी के लिए वी मैं – 1 वी मैं ग्राफ़ का एक किनारा बनाता है। हम ऐसे मार्ग को निरूपित करेंगे वी 0 वी 1 … वी के . उदाहरण के लिए, 1 4 3 2 5 उदाहरण 7.2 से ग्राफ जी में लंबाई 4 का एक मार्ग है।

जी एच

के एल

चित्र 7.4.

चक्रग्राफ़ में शीर्षों के अनुक्रम को कॉल करने की प्रथा है वी 0 , वी 1 , … , वी के , जिनमें से प्रत्येक जोड़ी एक किनारे का सिरा है, और वी 0 = वी 1 , और शेष शीर्ष (और किनारे) दोहराए नहीं जाते हैं। दूसरे शब्दों में, एक चक्र एक बंद मार्ग है जो इसके प्रत्येक शीर्ष और किनारे से केवल एक बार गुजरता है

1 2 1 2 3

चित्र 7.5

उदाहरण 7.3.उदाहरण 7.2 से ग्राफ G में चक्र खोजें।

समाधान।इस ग्राफ़ में लंबाई 5 के दो अलग-अलग चक्र हैं:

1 3 2 5 4 1 और 1 2 5 4 3 1

हम चक्र के एक मनमाने शीर्ष से शुरू करके, इन चक्रों से एक या दूसरे दिशा में गुजर सकते हैं। इसके अलावा, ग्राफ़ में लंबाई 4 के तीन अलग-अलग चक्र हैं:

1 2 5 4 1, 1 2 3 4 1 और 2 5 4 3 2,

और लंबाई 3 के दो लूप:

1 2 3 1 और 1 3 4 1.

वह ग्राफ़ जिसमें कोई चक्र नहीं है, कहलाता है चक्रीय.गणना में उत्पन्न होने वाली वृक्ष संरचनाएं एसाइक्लिक ग्राफ़ का एक विशेष मामला है। हम इस अध्याय में बाद में उनसे निपटेंगे।

गिनती, बुलाया सुसंगत,यदि इसके शीर्षों का कोई जोड़ा किसी मार्ग से जुड़ा हो। किसी भी सामान्य ग्राफ को उपग्राफ में विभाजित किया जा सकता है, जिनमें से प्रत्येक जुड़ा हुआ हो जाता है। ऐसे जुड़े हुए घटकों की न्यूनतम संख्या कहलाती है कनेक्शन संख्याग्राफ और द्वारा निरूपित किया जाता है सी(जी) . कंप्यूटर नेटवर्क पर ग्राफ़ सिद्धांत के अनुप्रयोगों में कनेक्टिविटी मुद्दे महत्वपूर्ण हैं। ग्राफ़ की कनेक्टिविटी संख्या निर्धारित करने के लिए निम्नलिखित एल्गोरिदम का उपयोग किया जाता है।

कनेक्टिविटी एल्गोरिदम.

मान लीजिए G = (V, E) एक ग्राफ है। एल्गोरिथम को मूल्य की गणना करने के लिए डिज़ाइन किया गया है सी = सी(जी), वे। किसी दिए गए ग्राफ़ G से जुड़े घटकों की संख्या।

वी' :=वी;

जबकिवी'≠ øकरना

y Є का चयन करें वी’

मार्ग को y से जोड़ने वाले शीर्ष खोजें;

से शीर्ष हटाएँवी' और

ई से संगत किनारे;

सी:= सी+1;

उदाहरण 7.4.चित्र में दिखाए गए ग्राफ़ पर कनेक्टिविटी एल्गोरिदम के संचालन का निरीक्षण करें। 7.6.

चित्र 7.6.

समाधान।तालिका देखें. 7.1.

तालिका 7.1.

प्रारंभिक मान	{1,2,3,4,5,6,7,8}
विकल्प y = 1
विकल्प y = 2
विकल्प y = 7

इसलिए, सी(जी) = 3. संबंधित जुड़े हुए घटकों को चित्र में दिखाया गया है। 7.7.

5

मुख्य प्रश्न:

ग्राफ़ के इतिहास से जानकारी. गिनें और
इसके तत्व.
ग्राफ़ में पथ और मार्ग
जुड़े हुए ग्राफ़. पेड़
ग्राफ़ पर संचालन.

ग्राफ सिद्धांत है
गणित की वह शाखा जिसमें
व्यापक व्यावहारिक अनुप्रयोग।
ग्राफ सिद्धांत - क्षेत्र
गणित पृथक करें,
कौन सी विशेषता है
अध्ययन के लिए ज्यामितीय दृष्टिकोण
वस्तुएं.

ग्राफ़ का इतिहास

पहली बार ग्राफ सिद्धांत की मूल बातें
लियोनार्ड के कार्यों में दिखाई दिया
यूलर (1707-1783;
स्विस, जर्मन और
रूसी गणितज्ञ)
जिसका उन्होंने समाधान बताया
पहेलियाँ और गणित
मनोरंजन कार्य.
ग्राफ सिद्धांत की शुरुआत हुई
यूलर की समस्या का समाधान
सात पुल
कोएनिग्सबर्ग.

निम्नलिखित पहेली लंबे समय से कोनिग्सबर्ग के निवासियों के बीच आम रही है:
किसी भी पुल को पार किए बिना (प्रीगोलिया नदी के पार) सभी पुलों को कैसे पार किया जाए
उनमें से दो बार? कई लोगों ने इस समस्या को सैद्धांतिक और सैद्धांतिक दोनों तरह से हल करने का प्रयास किया है
व्यावहारिक रूप से, चलते समय। लेकिन कोई सफल नहीं हुआ, लेकिन नहीं
यह साबित करना संभव था कि यह सैद्धांतिक रूप से भी असंभव है।
भागों के सरलीकृत आरेख में
शहर (काउंटी) पुल
रेखाओं के अनुरूप (आर्क)
गिनती), और शहर के कुछ हिस्से -
लाइन कनेक्शन बिंदु
(ग्राफ़ के शीर्ष)।
अपने तर्क के क्रम में, यूलर आया
निम्नलिखित निष्कर्ष: उत्तीर्ण होने में असमर्थ
किसी भी पुल से गुजरे बिना सभी पुलों को पार करें
उन्हें दो बार.

ग्राफ़ का इतिहास

शब्द "ग्राफ़" पहली बार पुस्तक में दिखाई दिया
हालाँकि, 1936 में हंगेरियन गणितज्ञ डी. कोएनिग
ग्राफ़ के बारे में प्रारंभिक सबसे महत्वपूर्ण प्रमेय
एल. यूलर पर वापस जाएँ।

यह सिद्धांत एक ग्राफ की अवधारणा पर आधारित है।

- परिमित संख्याओं का एक सेट
बिंदुओं को ग्राफ़ का शीर्ष कहा जाता है, और
इनमें से कुछ को जोड़ीवार जोड़ना
रेखाओं के शीर्षों को किनारा या कहा जाता है
ग्राफ़ के चाप. कभी-कभी ग्राफ़ समग्र रूप से
एक बड़े अक्षर से दर्शाया जा सकता है
पत्र।
G V ,X दो का जोड़ा कहलाता है
परिमित समुच्चय: बिंदुओं V और का समुच्चय
रेखाओं का सेट X (किनारे, चाप),
बिंदुओं के कुछ जोड़े को जोड़ना।

ग्राफ़ की संरचना

ग्राफ़ में रेखाओं से जुड़े शीर्ष होते हैं। चोटियों
कॉलम को लैटिन अक्षरों ए, बी, सी, डी या द्वारा निर्दिष्ट किया गया है
संख्या में.
एक निर्देशित रेखा (एक तीर के साथ) को चाप कहा जाता है।
एक गैर-दिशात्मक रेखा (बिना तीर के) को किनारा कहा जाता है।
एक रेखा जो एक निश्चित शीर्ष को छोड़कर a में प्रवेश करती है
इसे लूप कहा जाता है.
आर्क
ए
किनारा
में
कुंडली
साथ

निर्देशित ग्राफ -

एक ग्राफ़ जिसके शीर्ष चापों द्वारा जुड़े हुए हैं। साथ
ऐसे ग्राफ़ का उपयोग करके दर्शाया जा सकता है
एकतरफ़ा संबंध योजनाएँ.
यूरा
आन्या
माशा
कोल्या
वाइटा

भारित ग्राफ

यह एक ग्राफ़ है जिसके किनारे या चाप निर्दिष्ट हैं
संख्यात्मक मानों के अनुरूप (वे कर सकते हैं
उदाहरण के लिए, शहरों के बीच की दूरी इंगित करें
या परिवहन लागत)।
ग्राफ़ का भार उसके किनारों के भार के योग के बराबर होता है।
4
बी
सी
2
3
2
ए
1
ई
डी
ए
बी
सी
डी
ई
ए बी सी डी ई
3 1
4
2
3 4
2
1
2 2
तालिका (इसे वजन तालिका कहा जाता है)
मैट्रिक्स) ग्राफ़ से मेल खाता है।

अगर
ग्राफ G का एक किनारा इसके दोनों किनारों को जोड़ता है
शीर्ष V और W, (अर्थात V ,WX), तो वे कहते हैं
कि यह किनारा उनके लिए आकस्मिक है।
ग्राफ़ के दो शीर्षों को आसन्न कहा जाता है,
यदि इसमें कोई बढ़त की घटना है: चालू
चित्र में, शीर्ष A और B आसन्न हैं,
ए और एस.
ए
साथ
में

यदि ग्राफ़ G में एक किनारा है जिसका मूल है
और अंत संपाती हो, तो इस किनारे को कहा जाता है
कुंडली। चित्र में, किनारा q(C, C) एक लूप है।
क्यू
ई
साथ
ए
डी
बी

दो किनारों को आसन्न कहा जाता है यदि वे
एक उभयनिष्ठ शीर्ष है.
चित्र में, आसन्न हैं, उदाहरण के लिए,
एक उभयनिष्ठ शीर्ष C के साथ किनारे X1 और x2।
डी
x5
x1
एफ
साथ
x4
x2
जी
x7
x3
ई
x6
बी
एच
ए

पसलियां जो एक और से शुरू होती हैं
वही शिखर, वही अंत
एक ही शीर्ष पर कहा जाता है
एकाधिक या समानांतर.
प्रकार के समान युग्मों की संख्या
(V , W) को किनारे की बहुलता कहा जाता है (V , W)
शीर्ष A पर आपतित किनारों की संख्या है
इस शीर्ष की डिग्री कहलाती है और
डिग्री (ए) द्वारा दर्शाया जाता है (अंग्रेजी डिग्री से -
डिग्री)।

चित्र में, गुणज हैं, उदाहरण के लिए,
किनारे x1(A, B), x2(A, B). शीर्ष A और C
किनारे x3, x4, x5 आपतित हैं। इस तरह,
एज एसी में 3 की बहुलता है, और एज है
एबी - बहुलता 2 के बराबर।
ए
x4
x1
x3
साथ
x2
x5
में

चित्र में, शीर्ष A की डिग्री है
1 के बराबर, शीर्ष C – 4, शीर्ष D – 2.
इसे इस रूप में लिखा गया है: deg(A)=1, deg(C)=4,
डिग्री(डी)=2.
डी
x5
x1
एफ
साथ
x4
x2
जी
x7
x3
ई
x6
बी
एच
ए

ग्राफ़ का एक शीर्ष जिसकी डिग्री शून्य है, वह है
पृथक कहा जाता है।
पृथक शीर्षों से युक्त एक ग्राफ़
शून्य ग्राफ कहा जाता है।
ग्राफ़ का एक शीर्ष जिसकी डिग्री 1 है
फांसी कहा जाता है.
वह ग्राफ़ जिसमें कोई किनारा (चाप) न हो, कहलाता है
खाली।
ई
सी
ए
डी
बी
तस्वीर में सबसे ऊपर
ई - पृथक:
डिग्री(ई)=0.

आकृति में, शीर्ष A, B, E, G, H लटकन हैं।
डी
x5
x1
एफ
साथ
x4
x2
जी
x7
x3
ई
x6
बी
एच
ए

प्रमेय 1. ग्राफ़ जी वी, एक्स में योग
इसके सभी शीर्षों की डिग्री एक सम संख्या है,
ग्राफ़ के किनारों की संख्या के दोगुने के बराबर:
एन
डिग्री(V) 2मी
मैं 1
मैं
किसी भी ग्राफ़ में किनारों की संख्या बराबर होती है
इसके शीर्षों की घातों के योग का आधा।
जहां एन वी
- शीर्षों की संख्या;
एमएक्स ग्राफ के किनारों की संख्या है।

शीर्ष को सम (विषम) कहा जाता है,
यदि इसकी डिग्री सम (विषम) संख्या है।
चित्र में deg(D)=2, deg(F)=3, जिसका अर्थ है
ग्राफ शीर्ष D सम है और F सम है
विषम।
x5
डी
x1
एफ
साथ
x4
x2
जी
x7
x3
ई
x6
बी
एच
ए

काम। मालेंकी शहर में 15 टेलीफोन हैं। क्या उन्हें तारों से जोड़ना संभव है ताकि प्रत्येक फोन बिल्कुल पांच से जुड़ा हो

अन्य?

प्रमेय 2. कोई भी (गैर-उन्मुख)
ग्राफ़ में विषम की सम संख्या है
चोटियों
परिणाम। इसका ग्राफ बनाना असंभव है
विषम शीर्षों की एक विषम संख्या.
ग्राफ़ G को पूर्ण कहा जाता है,
यदि इनमें से कोई भी दो भिन्न हैं
शीर्ष एक और से जुड़े हुए हैं
केवल एक किनारा.

काम। कक्षा में 30 लोग हैं। क्या ऐसा हो सकता है कि 9 लोगों के 3 मित्र हों, 11 के 4 मित्र हों, और 10 के 5 मित्र हों?

ग्राफ़ का पूरक G V, X कहलाता है
समान शीर्षों V के साथ ग्राफ़ G V, X
ग्राफ़ G, और उन और केवल उन किनारों वाले X,
जिसे ग्राफ G में जोड़ा जाना चाहिए ताकि यह हो सके
भर गया. चित्र में, ग्राफ़ G1 को जोड़कर
ग्राफ़ G एक ग्राफ़ है
जी1
जी
जी1
जी1

पैटर्न 1.
पैटर्न 2.
वर्टेक्स डिग्री
डिग्रियों का योग
पूरा ग्राफ
वही हैं, और
उनमें से प्रत्येक 1 है
कम संख्या
इसके शीर्ष
ग्राफ
ग्राफ शीर्ष संख्या
सम, समान
संख्या दोगुनी करें
ग्राफ़ के किनारे. यह
नमूना
निष्पक्ष नहीं
केवल पूर्ण के लिए
लेकिन किसी के लिए भी
ग्राफ.

पैटर्न 3.
पैटर्न 4.
विषम संख्या
असंभव
किसी का शीर्ष
स्तंभ सम है.
के साथ एक ग्राफ बनाएं
विषम संख्या
विषम शीर्ष.

पैटर्न 5.
पैटर्न 6.
यदि सभी शीर्ष
हर चीज़ के साथ ग्राफ़
तो, स्तंभ सम है
इसे तोड़े बिना संभव है
कागज पेंसिल
("एक झटके से"),
प्रत्येक के माध्यम से स्वाइप करना
पसली केवल एक बार,
यह ग्राफ़ बनाएं.
आंदोलन संभव है
किसी से भी शुरुआत करें
शीर्ष और समापन
वह उसी शिखर पर है.
दो विषम
चोटियाँ, आप कर सकते हैं
ड्रा, नहीं
एक पेंसिल फाड़ना
कागज से, जबकि
आंदोलन की जरूरत है
किसी एक से शुरू करें
ये अजीब
शीर्ष और समापन
उनमें से दूसरे में.

पैटर्न 7.
एक ग्राफ़ जिसमें अधिक है
दो विषम
शिखर, असंभव
ड्रा "एक
उत्कर्ष के साथ।" आकृति
(ग्राफ), जो हो सकता है
बिना उठाये ड्रा करें
कागज पेंसिल,
बुलाया
यूनिकर्सल.

ग्राफ़ में पथ और मार्ग

निर्देशित ग्राफ़ में पथ को कहा जाता है
चापों का क्रम जिसमें अंतिम है
पिछले चाप के अलावा किसी भी चाप का शीर्ष,
अगले चाप का प्रारंभिक शीर्ष है।
जिस शिखर से मार्ग तय होता है,
पथ की शुरुआत कहा जाता है, शीर्ष अंत में है
मार्ग - पथ का अंत.
वह पथ जिसमें प्रत्येक शीर्ष का उपयोग किया जाता है
एक बार से अधिक नहीं, सरल कहा जाता है
रास्ता।
ग्राफ़ में पथ की लंबाई चापों की संख्या है
(किनारे) जो इस पथ को बनाते हैं।

उदाहरण के तौर पर, डिग्राफ पर विचार करें
चित्र में प्रस्तुत किया गया है। मौजूदा में से एक
शीर्ष 1 और 3 को जोड़ने वाला पथ है
शीर्षों का क्रम 1, 2, 1, 4, 3. एकमात्र
शीर्षों के समान जोड़े के लिए एक सरल पथ है
अनुक्रम 1, 4, 3. शीर्ष 1 से पथ
उसी ग्राफ़ के लिए वर्टेक्स 5 मौजूद नहीं है।

अप्रत्यक्ष ग्राफ कहलाता है
यदि कम से कम एक पथ है तो जुड़ा हुआ है
शीर्षों के प्रत्येक जोड़े के बीच.
यदि कोई डायग्राफ़ जुड़ा हुआ है तो उसे कनेक्टेड कहा जाता है
एक अप्रत्यक्ष ग्राफ़
मूल उन्मुख से प्राप्त किया जाता है
सभी चापों को किनारों से बदलना।

किसी पथ को बंद कहा जाता है यदि
आरंभ और अंत शीर्ष समान हैं।
एक बंद रास्ते को एक चक्र कहा जाता है यदि सभी
इसके शीर्ष (प्रारंभिक और अंतिम को छोड़कर)
कुछ अलग हैं।
ग्राफ़ पर विचार करें. उसके लिए रास्ता है 2, 1, 6, 5, 4, 1,
2 बंद है; और पथ 1, 6, 5, 4, 1 है
एक चक्र है.

जोड़ीवार आसन्न का क्रम
एक अप्रत्यक्ष ग्राफ़ के शीर्ष, यानी
किनारों का क्रम
अप्रत्यक्ष ग्राफ़ जिसमें दूसरा
पिछले किनारे का शीर्ष मेल खाता है
अगले के पहले शीर्ष को कहा जाता है
मार्ग।
किसी मार्ग में किनारों की संख्या को लंबाई कहा जाता है
मार्ग।
यदि मार्ग का आरंभिक शीर्ष मेल खाता है
अंतिम एक के साथ, फिर ऐसे मार्ग को कहा जाता है
बंद या लूप.

चित्र में, HCDFD लंबाई 4 का एक मार्ग है।
पदनाम: |एचसीडीएफडी|=4. मार्ग स्वीकृत
पूछना
कैसे
परिणाम को
पसलियाँ,
चूँकि गुणज होने पर यह सुविधाजनक होता है
पसलियाँ
एक्स
डी
x1
5
एफ
साथ
x4
x2
जी
x7
x3
ई
x6
बी
एच
ए

चित्र में ग्राफ़ में (t, s, p, r), (u, s, t, r) चक्र हैं
लंबाई 4, (आर, टी, क्यू, एस, यू) - चक्र लंबाई 5, (टी, एस, यू, आर, टी, एस, पी, आर)
- 8-चक्र, (पी, यू) - 2-चक्र, लूप (क्यू) - 1-चक्र।
ई
क्यू
सी
एस
ए
पी
टी
डी
आर
बी
यू

ग्राफ़ पर संचालन

एकल संचालन
1. ग्राफ़ के एक किनारे को हटाना - इस मामले में, ग्राफ़ के सभी शीर्ष
सहेजे गए हैं
2. दो के बीच एक ग्राफ़ किनारा जोड़ना
मौजूदा चोटियाँ.
3. एक शीर्ष को हटाना (घटना के साथ)।
पसलियाँ)।
4. एक शीर्ष जोड़ना (जिससे जोड़ा जा सके
ग्राफ़ के कुछ शीर्ष)।
5. एक किनारे का संकुचन - शीर्षों की एक जोड़ी की पहचान, यानी।
आसन्न शीर्षों की एक जोड़ी को हटाना और एक नया जोड़ना
उन शीर्षों के निकटवर्ती शीर्ष जो थे
दूरस्थ शीर्षों में से कम से कम एक के निकट)
6. एक किनारे को उपविभाजित करना - एक किनारे को हटाकर जोड़ना
एक नया शीर्ष जो प्रत्येक से एक किनारे से जुड़ा हुआ है
सुदूर किनारे के शिखर.

ग्राफ़ पर संचालन

दोहरा ऑपरेशन
ग्राफ़ G1 (V1, X 1) और G2 (V2, X 2) को मिलाकर
ग्राफ को G G1 G2 कहा जाता है, शीर्षों का समुच्चय
जो V V1 V2 है, और किनारों का सेट X X 1 X 2 है।
ग्राफ़ G1 और G2 के प्रतिच्छेदन को कहा जाता है
ग्राफ G G1 G2 जिसके लिए X X 1 X 2 किनारों का समुच्चय है, और V V1 V2 शीर्षों का समुच्चय है।
दो ग्राफ़ के रिंग योग को ग्राफ़ कहा जाता है
G G1 G2 शीर्षों के एक सेट द्वारा उत्पन्न होता है
वे।
V V1 V2 और किनारों का एक सेट (X1 X 2) \ (X1 X 2) ,
किनारों का सेट या तो G1 या अंदर समाहित है
G2, लेकिन G1 G2 में नहीं.

V4
वी 2
x3
x2
वी 3
x4
V1
x1
वी 5
x2
x7
x3
x4
x4
V1
x7
V1
जी=जी1यूजी2
वी 3
x4
वी 5
x2
V1
x3
G=G1∩G2
वी 2
x1
जी2
V4
वी 2
x5 x6
x6
वी 3
V1
V4
वी 3
V4
x5
x3
x1
जी1
वी 2
वी 5
वी 2
V4
x5 x6V
3
x7
जी=जी1 जी2

ग्राफ़ का अनुप्रयोग

साथ
मदद से
रेखांकन
सरलीकृत
गणित की समस्याएँ, पहेलियाँ,
सरलता.
समाधान
के लिए कार्य
आगे

ग्राफ़ का अनुप्रयोग

भूलभुलैया एक ग्राफ है. और इसका अन्वेषण करना इसे खोजना है
इस ग्राफ़ में पथ.
आगे

ग्राफ़ का उपयोग करता है और
बड़प्पन.
चित्र दिखाता है
वंशावली का हिस्सा
पेड़
प्रसिद्ध
कुलीन परिवार एल.एन.
टॉल्स्टॉय. यह रहा
शीर्ष इसके सदस्य हैं
दयालु, और उन्हें जोड़ने वाले
खंड - रिश्ते
रिश्तेदारी,
माता-पिता से अग्रणी
बच्चे।
आगे

ग्राफ़ का अनुप्रयोग

ग्राफ़ कार्यक्रमों के ब्लॉक आरेख हैं
कंप्यूटर।
आगे

ग्राफ़ का अनुप्रयोग

विशिष्ट ग्राफ़ पर
भौगोलिक मानचित्र हैं
रेलमार्ग छवियां.
आगे

ग्राफ़ का अनुप्रयोग

शहर के मानचित्रों पर विशिष्ट ग्राफ़
शहरी यातायात पैटर्न हैं
परिवहन।
आगे

निष्कर्ष

ग्राफ़ अद्भुत गणितीय हैं
जिन वस्तुओं से आप हल कर सकते हैं
गणितीय, आर्थिक और तार्किक
कार्य. आप विभिन्न समाधान भी कर सकते हैं
पहेलियाँ और उनके अनुसार कार्यों की शर्तों को सरल बनाएं
भौतिकी, रसायन विज्ञान, इलेक्ट्रॉनिक्स, स्वचालन। रेखांकन
उपयोग किया जाता है
पर
बनाना
कार्ट
और
वंशावली वृक्ष.
गणित में भी एक विशेष अनुभाग है
जिसे कहा जाता है: "ग्राफ़ सिद्धांत"।
सामग्री

पूरी तरह से डिस्कनेक्ट किए गए ग्राफ़ . वह ग्राफ जिसके कई किनारे खाली हों, कहलाता है काफी असंगत(या खाली) ग्राफ़.हम n शीर्षों वाले पूर्णतया असंबद्ध ग्राफ को N n से निरूपित करेंगे; एन 4 चित्र में दिखाया गया है। 1. ध्यान दें परपूरी तरह से असंबद्ध ग्राफ़ के, सभी शीर्ष अलग-थलग हैं। पूरी तरह से असंबद्ध ग्राफ़ विशेष रुचि के नहीं हैं।

पूर्ण ग्राफ़ . एक सरल ग्राफ जिसमें कोई भी दो शीर्ष आसन्न हों, कहलाता है पूरा ग्राफ. n शीर्षों वाला एक पूर्ण ग्राफ आमतौर पर द्वारा दर्शाया जाता है। ग्राफ़ और चित्र में दिखाए गए हैं। 2 और 3. में बिल्कुल n (n - 1)/2 किनारे हैं।

नियमित रेखांकन . वह ग्राफ़ कहलाता है जिसमें सभी शीर्षों की डिग्री समान होती है नियमित ग्राफ.यदि प्रत्येक शीर्ष की डिग्री r है, तो ग्राफ़ कहा जाता है नियमित डिग्री आर.डिग्री 3 का नियमित ग्राफ़ भी कहा जाता है घन(या त्रिसंयोजक)ग्राफ़ (उदाहरण के लिए, चित्र 2 और 4 देखें)। घन ग्राफ़ का एक अन्य प्रसिद्ध उदाहरण तथाकथित है काउंट पीटरसन,अंजीर में दिखाया गया है। 5. ध्यान दें कि प्रत्येक पूरी तरह से डिस्कनेक्ट किया गया ग्राफ़ डिग्री 0 का नियमित है, और प्रत्येक पूर्ण ग्राफ़ K n डिग्री n - 1 का नियमित है।

प्लेटोनिक रेखांकन . नियमित ग्राफ़ के बीच, तथाकथित प्लेटोनिक ग्राफ़ विशेष रूप से दिलचस्प हैं - पाँच नियमित पॉलीहेड्रा के शीर्षों और किनारों द्वारा निर्मित ग्राफ़ - प्लेटोनिक ठोस: टेट्राहेड्रोन, क्यूब, ऑक्टाहेड्रोन, डोडेकाहेड्रोन और इकोसाहेड्रोन। ग्राफ़ एक चतुष्फलक से मेल खाता है (चित्र 2); घन और अष्टफलक के संगत ग्राफ़ चित्र में दिखाए गए हैं। 5 और 6;

द्विदलीय रेखांकन . आइए मान लें कि ग्राफ़ के शीर्षों के सेट को दो असंयुक्त उपसमुच्चय वी 1 और वी 2 में विभाजित किया जा सकता है ताकि जी में प्रत्येक किनारा वी 1 से कुछ शीर्ष को वी 2 से कुछ शीर्ष से जोड़ सके (चित्र 7);

तब G को द्विदलीय ग्राफ कहा जाता है। यदि कोई दो निर्दिष्ट उपसमुच्चय में अंतर करना चाहता है तो ऐसे ग्राफ़ को कभी-कभी G(V 1, V 2) से दर्शाया जाता है। एक द्विदलीय ग्राफ को दूसरे तरीके से भी परिभाषित किया जा सकता है - इसके शीर्षों को दो रंगों, जैसे लाल और नीले, से रंगने के संदर्भ में। एक ग्राफ़ को द्विदलीय कहा जाता है यदि इसके प्रत्येक शीर्ष को लाल या नीले रंग में रंगा जा सकता है ताकि किसी भी किनारे का एक छोर लाल और दूसरा नीला हो। इस बात पर जोर दिया जाना चाहिए कि द्विदलीय ग्राफ में यह आवश्यक नहीं है कि V 1 से प्रत्येक शीर्ष V 2 से प्रत्येक शीर्ष से जुड़ा हो; यदि ऐसा है और यदि ग्राफ़ G सरल है, तो इसे कहा जाता है पूर्ण द्विदलीय ग्राफऔर आमतौर पर इसे इससे दर्शाया जाता है जहां m, n क्रमशः V 1 और V 2 में शीर्षों की संख्या है। उदाहरण के लिए, चित्र में. 8 ग्राफ K 4, 3 दिखाता है। ध्यान दें कि ग्राफ़ में बिल्कुल m + n शीर्ष और mn किनारे हैं। प्रपत्र के पूर्ण द्विदलीय ग्राफ़ को स्टार ग्राफ़ कहा जाता है; चित्र में 9 एक स्टार ग्राफ दिखाता है।

जुड़े हुए ग्राफ़ . ग्राफ़ जुड़े हुए,यदि इसे दो ग्राफ़ों के संघ के रूप में प्रस्तुत नहीं किया जा सकता है, और बेतुकाअन्यथा। जाहिर है, प्रत्येक असंबद्ध ग्राफ़ G को सीमित संख्या में जुड़े हुए ग्राफ़ों के संघ के रूप में दर्शाया जा सकता है - ऐसे प्रत्येक जुड़े हुए ग्राफ़ को कहा जाता है घटक (कनेक्टिविटी)ग्राफ़ जी. (चित्रा 10 तीन घटकों के साथ एक ग्राफ़ दिखाता है।) पहले जुड़े हुए ग्राफ़ के लिए मनमाने ग्राफ़ के लिए कुछ कथनों को सिद्ध करना और फिर उन्हें प्रत्येक घटक पर अलग से लागू करना अक्सर सुविधाजनक होता है।

"पृथक" शीर्षों से युक्त ग्राफ़ आरेख को कहा जाता है शून्य ग्राफ. (अंक 2)

ऐसे ग्राफ़ कहलाते हैं जिनमें सभी संभावित किनारों का निर्माण नहीं किया जाता है अपूर्ण रेखांकन. (चित्र 3)

वे ग्राफ़ कहलाते हैं जिनमें सभी संभावित किनारों का निर्माण किया जाता है पूर्ण रेखांकन. (चित्र.4)


यदि किसी ग्राफ़ के किनारों पर किनारों की दिशा बताने वाले तीर हों तो ऐसा ग्राफ़ कहा जाता है निर्देशित.

चित्र में दिखाए गए ग्राफ़ में एक कार्य से दूसरे कार्य तक जाने वाले तीर का अर्थ कार्यों का क्रम है।

आप नींव का निर्माण पूरा किए बिना दीवारें स्थापित करना शुरू नहीं कर सकते हैं; परिष्करण शुरू करने के लिए, आपको फर्श आदि पर पानी रखना होगा।

शीर्षों की डिग्री और किनारों की संख्या की गिनती।

ग्राफ़ के एक शीर्ष को छोड़ने वाले किनारों की संख्या को शीर्ष की डिग्री कहा जाता है। ग्राफ़ के जिस शीर्ष पर विषम डिग्री होती है उसे विषम कहा जाता है, और जिस शीर्ष पर सम डिग्री होती है उसे सम कहा जाता है।

यदि किसी ग्राफ़ के सभी शीर्षों की डिग्री बराबर हो, तो ग्राफ़ कहलाता है सजातीय. इस प्रकार, कोई भी पूर्ण ग्राफ सजातीय होता है।

चित्र 5 पाँच शीर्षों वाला एक ग्राफ़ दिखाता है।

हम शीर्ष A की डिग्री को St.A के रूप में दर्शाते हैं।

चित्र में:
एसटी.ए = 1, एसटी.बी = 2, एसटी.बी = 3, एसटी.जी = 2, एसटी.डी = 0।

आइए हम कुछ ग्राफ़ में निहित कुछ नियमितताएं तैयार करें।

पैटर्न 1.एक पूर्ण ग्राफ़ के शीर्षों की डिग्री समान होती है, और उनमें से प्रत्येक इस ग्राफ़ के शीर्षों की संख्या से 1 कम है।

पैटर्न 2.ग्राफ़ के शीर्षों की डिग्री का योग एक सम संख्या है जो ग्राफ़ के किनारों की संख्या के दोगुने के बराबर है।

यह पैटर्न न केवल संपूर्ण ग्राफ़ के लिए, बल्कि किसी भी ग्राफ़ के लिए भी सत्य है।

किसी भी ग्राफ़ में विषम शीर्षों की संख्या सम होती है.

ध्यान दें कि यदि पूर्ण ग्राफ़ में n शीर्ष हैं, तो किनारों की संख्या n(n-1)/2 के बराबर होगी।

एक ग्राफ़ जो पूर्ण नहीं है, उसे लुप्त किनारों को जोड़कर समान शीर्षों के साथ पूरा किया जा सकता है। उदाहरण के लिए, चित्र 3 पाँच शीर्षों वाला एक अधूरा ग्राफ़ दिखाता है। चित्र 4 में, ग्राफ़ को पूर्ण ग्राफ़ में बदलने वाले किनारों को एक अलग रंग में दर्शाया गया है; इन किनारों के साथ ग्राफ़ के शीर्षों के संग्रह को ग्राफ़ का पूरक कहा जाता है।

यूलर रेखांकन.

वह ग्राफ जो कागज से पेंसिल उठाए बिना खींचा जा सकता है, कहलाता है यूलेरियन. (चित्र.6)

इन ग्राफ़ का नाम वैज्ञानिक के नाम पर रखा गया है लियोनहार्ड यूलर.


पैटर्न 3.(हमारे द्वारा विचार किए गए प्रमेय से अनुसरण करता है)।
विषम शीर्षों की विषम संख्या वाला ग्राफ बनाना असंभव है।

पैटर्न 4.यदि ग्राफ़ के सभी शीर्ष सम हैं, तो आप अपनी पेंसिल को कागज़ से उठाए बिना ("एक झटके से"), प्रत्येक किनारे पर केवल एक बार घुमाकर यह ग्राफ़ बना सकते हैं। आंदोलन किसी भी शीर्ष से शुरू हो सकता है और उसी शीर्ष पर समाप्त हो सकता है।

पैटर्न 5.कागज से पेंसिल उठाए बिना केवल दो विषम शीर्षों वाला एक ग्राफ खींचा जा सकता है, और यह गति इन विषम शीर्षों में से एक पर शुरू होनी चाहिए और उनमें से दूसरे पर समाप्त होनी चाहिए।

पैटर्न 6.दो से अधिक विषम शीर्षों वाला ग्राफ़ नहीं खींचा जा सकता" एक झटके से».

वह आकृति (ग्राफ) जो कागज पर से पेंसिल उठाए बिना खींची जा सके, कहलाती है यूनिकर्सल.

ग्राफ कहा जाता है सुसंगत, यदि इसके किन्हीं दो शीर्षों को एक पथ से जोड़ा जा सकता है, अर्थात, किनारों का एक क्रम, जिनमें से प्रत्येक पिछले एक के अंत से शुरू होता है।

चित्र 7 स्पष्ट रूप से एक असंबद्ध ग्राफ़ दिखाता है।

ग्राफ कहा जाता है बेतुका, यदि यह शर्त पूरी नहीं होती है।

यदि, उदाहरण के लिए, चित्र में आप शीर्ष D और E के बीच एक किनारा खींचते हैं, तो ग्राफ़ जुड़ जाएगा।( चित्र.8)

ग्राफ सिद्धांत में ऐसे किनारे को (जिसे हटाने के बाद ग्राफ कनेक्टेड से डिसकनेक्टेड में बदल जाता है) कहा जाता है पुल.

पुलों के उदाहरण चित्र 7किनारे DE, A3, VZh, आदि काम कर सकते हैं, जिनमें से प्रत्येक ग्राफ़ के "पृथक" भागों के शीर्षों को जोड़ देगा। ( चित्र.8)

एक डिस्कनेक्ट किए गए ग्राफ़ में कई " होते हैं टुकड़े" इन "टुकड़ों" को ग्राफ़ के जुड़े हुए घटक कहा जाता है। प्रत्येक जुड़ा हुआ घटक, निश्चित रूप से, एक जुड़ा हुआ ग्राफ़ है। ध्यान दें कि कनेक्टेड ग्राफ़ में एक कनेक्टेड घटक होता है।

एक ग्राफ यूलेरियन है यदि और केवल यदि यह जुड़ा हुआ है और इसमें अधिकतम दो विषम शीर्ष हैं।

पेड़.

पेड़कोई भी जुड़ा हुआ ग्राफ जिसमें कोई चक्र नहीं है, कहलाता है।

चक्रएक ऐसा पथ है जिसमें आरंभ और अंत मेल खाते हैं।

यदि किसी चक्र के सभी शीर्ष अलग-अलग हों तो ऐसा चक्र कहलाता है प्राथमिक(या सरल) चक्र।

यदि किसी चक्र में ग्राफ़ के सभी किनारों को एक बार शामिल किया जाता है, तो ऐसे चक्र को कहा जाता है यूलर लाइन (चित्र.9ए).

पर कॉलम में चित्र.9बीदो चक्र: 1-2-3-4-1 और 5-6-7-5।

द्वाराएक ग्राफ़ में एक शीर्ष से दूसरे शीर्ष तक किनारों का एक क्रम होता है जिसके साथ इन शीर्षों के बीच एक मार्ग बिछाया जा सकता है।

इस स्थिति में, मार्ग का कोई भी किनारा एक से अधिक बार प्रकट नहीं होना चाहिए। जिस शिखर से मार्ग बिछाया जाता है उसे कहते हैं यात्रा की शुरुआत, मार्ग के अंत में शिखर - सड़क का अंत.

लटकता हुआ शीर्षएक शीर्ष है जहाँ से बिल्कुल एक किनारा निकलता है ( चित्र.10).
(लटकती चोटियाँ परिक्रमा करती हैं)।


प्रत्येक जोड़ी पेड़ के शिखर के लिए उन्हें जोड़ने वाला एक अनोखा मार्ग है.

इस संपत्ति का उपयोग तब किया जाता है जब किसी परिवार के पेड़ में सभी पूर्वजों को खोजा जाता है, उदाहरण के लिए, पुरुष वंश में, किसी भी व्यक्ति की वंशावली को परिवार के पेड़ के रूप में दर्शाया जाता है, जो कि " पेड़"और ग्राफ़ सिद्धांत के अर्थ में।

पेड़ का हर किनारा एक पुल है।

दरअसल, पेड़ के किसी भी किनारे को हटाने के बाद, यह " विखंडित"दो पेड़ों पर.

वह ग्राफ जिसमें किन्हीं दो शीर्ष बिल्कुल एक सरल पथ से जुड़े हों, वह है पेड़.

(लटके हुए शीर्ष के बारे में)। प्रत्येक पेड़ की एक लटकती हुई चोटी होती है।

. एक पेड़ में शीर्षों की संख्या किनारों की संख्या से एक अधिक होती है।

समरूपता। समतलीय रेखांकन और यूलर प्रमेय।

दो ग्राफ कहलाते हैं समरूपी, यदि उनके शीर्षों की संख्या समान है, और प्रत्येक ग्राफ़ के शीर्षों को 1 से n तक क्रमांकित किया जा सकता है, ताकि पहले ग्राफ़ के शीर्ष एक किनारे से जुड़े हों यदि और केवल यदि दूसरे ग्राफ़ के संगत शीर्ष इससे जुड़े हों एक किनारा।

आइए हम सिद्ध करें कि चित्र 11 में दिखाए गए ग्राफ समरूपी हैं।


आइए पहले और दूसरे ग्राफ़ के शीर्षों को 1 से 4 तक क्रमांकित करें ( चित्र.12).


पहला ग्राफ शीर्ष 1 और 2, 2 और 3, 3 और 4, 1 और 4, 1 और 3, 2 और 4 को जोड़ता है; ध्यान दें कि दूसरे ग्राफ में शीर्ष 1 और 2, 2 और 3, 3 और 4, 1 और 4, 1 और 3, 2 और 4 भी जुड़े हुए हैं, इसलिए, ये ग्राफ समरूपी हैं।

यह पता लगाने के लिए कि क्या दो ग्राफ समरूपी हैं, आपको यह सुनिश्चित करना होगा कि उनमें:

• शीर्षों की समान संख्या
• यदि एक ग्राफ़ के शीर्ष एक किनारे से जुड़े हुए हैं, तो दूसरे ग्राफ़ के संगत शीर्ष भी एक किनारे से जुड़े हुए हैं।

एक ग्राफ जिसे इस प्रकार खींचा जा सकता है कि इसके किनारे इसके शीर्षों को छोड़कर कहीं भी प्रतिच्छेद न करें, कहलाता है समतलया तलीय.

यूलर. सही ढंग से खींचे गए कनेक्टेड प्लेनर ग्राफ के लिए, इसमें समानता है: V-E+F=2, जहां V शीर्षों की संख्या है, E किनारों की संख्या है, F टुकड़ों की संख्या है F=2 को आमतौर पर यूलर का सूत्र कहा जाता है).

वह ग्राफ़ कहलाता है जिसमें प्रत्येक शीर्ष प्रत्येक दूसरे शीर्ष के एक किनारे से जुड़ा होता है पूरा.

पोंट्रीगिन - कुराटोव्स्की. एक ग्राफ़ सपाट होता है यदि और केवल तभी जब इसमें (टोपोलॉजिकल अर्थ में) "हाउस-वेल" प्रकार के छह शीर्षों वाला एक ग्राफ़ और पाँच शीर्षों वाला एक पूरा ग्राफ़ न हो।

(मुख्य रूप से घरों और कुओं के बारे में प्राचीन समस्याओं में उपयोग किया जाता है, जिसका सार प्रश्न को स्पष्ट करने के लिए कम हो जाता है - क्या प्रश्न में ग्राफ़ सपाट है या नहीं, चित्र.13)

निर्देशित रेखांकन.

व्यावहारिक समस्याओं के महत्वपूर्ण वर्ग हैं जिन्हें पहले चर्चा किए गए प्रकार के ग्राफ़ का उपयोग करके हल नहीं किया जा सकता है।

उदाहरण के लिए, किसी शहर की सड़कों और चौराहों का नक्शा एक समतल ग्राफ़ का उपयोग करके दर्शाया गया है। लेकिन क्या होगा यदि आपको कार से शहर के चारों ओर यात्रा करने के लिए इस योजना का उपयोग करने की आवश्यकता है, और कुछ (या सभी) सड़कों पर यातायात एकतरफा है?

फिर, उदाहरण के लिए, सीधे किनारों पर स्थित तीर - प्रश्न में शहर की सड़कें (ग्राफ), इस स्थिति को नेविगेट करने में मदद कर सकती हैं।

इसके किनारों पर तीरों वाला ग्राफ कहलाता है उन्मुखी.

आउटपुट डिग्रीएक निर्देशित ग्राफ़ का शीर्ष किनारों की संख्या है जिसके लिए यह शीर्ष शुरुआत है (किनारों की संख्या, " बाहर आ रहा है"ऊपर से)।

प्रवेश की डिग्रीनिर्देशित ग्राफ़ का शीर्ष किनारों की संख्या है जिसके लिए यह शीर्ष अंत है (किनारों की संख्या, " आने वाली"सबसे ऊपर)।

हाँ, चालू चित्र 15एक निर्देशित ग्राफ एबीसीडी दिखाता है। इसके कुछ शीर्षों की प्रवेश और निकास डिग्री इस प्रकार हैं:
St.in.A=2, St.out.A=1 St.in.B=2, St.out.B=0 St.in.D=1, St.out.D=3.

शीर्ष A1 से शीर्ष An तक निर्देशित ग्राफ़ में पथ उन्मुख किनारों A1A2, A2A3, ..., Аn-1Аn का एक क्रम है, जिसमें प्रत्येक पिछले किनारे का अंत अगले की शुरुआत के साथ मेल खाता है और प्रत्येक किनारा अंदर होता है यह क्रम केवल एक बार।

पर चित्र.15निर्देशित ग्राफ़ में पथों के उदाहरण दिखाए गए हैं। इसके अलावा, पहले दो पथ सरल हैं - इसमें कोई भी शीर्ष एक से अधिक बार समाहित नहीं है। तीसरा तरीका सरल नहीं है, यानी. शीर्ष जी के माध्यम से पथ " उत्तीर्ण"दो बार।

निर्देशित चक्रनिर्देशित ग्राफ़ में बंद पथ कहलाता है।

पर चित्र 15पिछले दो ग्राफ़ में उन्मुख चक्रों के उदाहरण दिए गए हैं। ग्राफ़ में किसी भी अन्य पथ की तरह, एक चक्र की लंबाई इस पथ में किनारों की संख्या से निर्धारित होती है।

तो, चित्र 16 में, A से D तक के रास्ते अलग-अलग हो सकते हैं और उनकी लंबाई भी अलग-अलग हो सकती है।
पहले पथ की लंबाई 2 है, दूसरे की - 3,
और तीसरा 4 है.

दो शीर्षों के बीच के "सबसे छोटे पथ" की लंबाई को उनके बीच की दूरी कहा जाता है। तो चित्र 16 के ग्राफ़ में शीर्ष A और D के बीच की दूरी 2 है; इस प्रकार लिखा गया है: S(BP)=2.

यदि निर्देशित ग्राफ़ में एक शीर्ष से दूसरे शीर्ष तक "पास" करना असंभव है, तो उनके बीच की दूरी को अनंत कहा जाता है (अनंत प्रतीक द्वारा दर्शाया गया है)। इस प्रकार, चित्र 17 में प्रस्तुत ग्राफ़ के शीर्ष B और D के बीच की दूरी अनंत है: S(DB) = ∞

अर्थशास्त्र में निर्देशित ग्राफ सक्रिय रूप से नेटवर्क प्लानिंग में, गणित में - गेम थ्योरी, सेट थ्योरी में उपयोग किए जाते हैं; कई समस्याओं को हल करते समय, विशेष रूप से संयोजक समस्याओं को हल करते समय।