# 1: ग्राफ थ्योरी का संक्षिप्त परिचय

एक ग्राफ की परिभाषा

एक ग्राफ एक गणितीय संरचना है जिसमें वर्टिकल का एक सेट (जिसे नोड्स भी कहा जाता है) और किनारों का एक सेट (जिसे लिंक या कनेक्शन भी कहा जाता है) होता है जो वर्टिकल के जोड़े को जोड़ता है। एक ग्राफ़ में, कोने वस्तुओं या संस्थाओं का प्रतिनिधित्व करते हैं, और किनारे उनके बीच संबंधों या बातचीत का प्रतिनिधित्व करते हैं।

एक ग्राफ को गणितीय रूप से दर्शाया जा सकता है G = (V,E), जहाँ V शीर्षों का समुच्चय है और E किनारों का समुच्चय है।

ग्राफ़ के आकार को ग्राफ़ में शीर्षों की संख्या के रूप में परिभाषित किया जाता है, जिसे द्वारा निरूपित किया जाता है |V|, और किनारों की संख्या, द्वारा निरूपित की जाती है |E|।

एक ग्राफ के घटक

एक ग्राफ को निम्नलिखित सहित कई घटकों में विभाजित किया जा सकता है:

• वर्टेक्स : एक वर्टेक्स एक ग्राफ में एक बिंदु या वस्तु है। इसे एक वृत्त या बिंदु के रूप में दर्शाया जाता है।
• किनारा (Edge) : एक किनारा एक ग्राफ में दो शीर्षों के बीच एक रेखा या संबंध है। इसे दो वृत्तों को जोड़ने वाली रेखा या तीर के रूप में दर्शाया जाता है।

• डिग्री : किसी शीर्ष की डिग्री उस पर आपतित किनारों की संख्या होती है । दूसरे शब्दों में, यह शीर्ष से जुड़े किनारों की संख्या है।
• पथ : ग्राफ़ में पथ शीर्षों और किनारों का एक क्रम होता है जो दो शीर्षों को जोड़ता है। इसे कोने और किनारों के अनुक्रम के रूप में दर्शाया जा सकता है, जैसे (v1, e1, v2, e2, …, vn-1, en-1, vn) ।
• चक्र: एक चक्र एक ग्राफ में एक पथ है जो एक ही शीर्ष पर शुरू और समाप्त होता है। इसे कोने और किनारों के अनुक्रम के रूप में दर्शाया जा सकता है, जैसे (v1, e1, v2, e2, …, vn-1, en-1, vn, en, v1) ।

निम्नलिखित सहित कई प्रकार के रेखांकन हैं:

• अप्रत्यक्ष ग्राफ़ : एक अप्रत्यक्ष ग्राफ़ में, किनारों की कोई दिशा नहीं होती है, जिसका अर्थ है कि उन्हें दोनों दिशाओं में पार किया जा सकता है। इसका अर्थ है कि यदि शीर्ष v1 और शीर्ष v2 के बीच कोई किनारा है, तो शीर्ष v2 और शीर्ष v1 के बीच भी एक किनारा है।
• निर्देशित ग्राफ़ : एक निर्देशित ग्राफ़ में, किनारों की एक दिशा होती है, जिसका अर्थ है कि उन्हें केवल एक दिशा में ही पार किया जा सकता है। इसका अर्थ है कि यदि शीर्ष v1 से शीर्ष v2 तक कोई किनारा है, तो शीर्ष v2 से शीर्ष v1 तक कोई किनारा नहीं है।

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

• पूर्ण ग्राफ़ : एक पूर्ण ग्राफ़ में, प्रत्येक शीर्ष ग्राफ़ में प्रत्येक अन्य शीर्ष से जुड़ा होता है।
• सबग्राफ : एक ग्राफ का एक सबग्राफ Gएक ग्राफ होता है जो के शीर्षों और किनारों के एक उपसमुच्चय द्वारा बनाया जाता है G।

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