Graph Theory: Introduction, Terminology, Types of Graphs, Paths, and Graph Coloring | ग्राफ सिद्धांत: परिचय, पारिभाषिक शब्दावली, ग्राफ के प्रकार, पथ और रंगन


Graph Theory: Introduction, Terminology, Types of Graphs, Paths, and Graph Coloring | ग्राफ सिद्धांत: परिचय, पारिभाषिक शब्दावली, ग्राफ के प्रकार, पथ और रंगन

ग्राफ सिद्धांत (Graph Theory) गणित की वह शाखा है जो वस्तुओं (Objects) और उनके संबंधों (Relationships) का अध्ययन करती है। यह Computer Science, Networking, Artificial Intelligence, और Optimization में अत्यंत महत्वपूर्ण भूमिका निभाती है। Graph का उपयोग वास्तविक जीवन की समस्याओं जैसे नेटवर्क कनेक्टिविटी, मार्ग खोज (Path Finding), और संसाधन आवंटन (Resource Allocation) में किया जाता है।

1️⃣ ग्राफ का परिचय (Introduction to Graph)

एक ग्राफ G को इस प्रकार परिभाषित किया जाता है:

G = (V, E)

जहाँ V = Vertex (बिंदुओं का सेट) और E = Edge (रेखाओं का सेट जो दो बिंदुओं को जोड़ते हैं)।

उदाहरण: V = {A, B, C, D}, E = {(A, B), (B, C), (C, D), (D, A)}

यह एक वर्गाकार (square) ग्राफ को दर्शाता है।

2️⃣ ग्राफ की पारिभाषिक शब्दावली (Terminology of Graph Theory)

  • Vertex (शिखर): ग्राफ के बिंदु, जैसे V = {A, B, C, D}
  • Edge (रेखा): दो बिंदुओं को जोड़ने वाली रेखा, जैसे (A, B)
  • Degree: किसी vertex से जुड़ी edges की संख्या
  • Adjacent Vertices: दो बिंदु जो एक edge से जुड़े हों
  • Isolated Vertex: जो किसी edge से जुड़ा न हो
  • Loop: कोई vertex स्वयं से जुड़ा हो (A, A)
  • Parallel Edges: दो vertices को जोड़ने वाली एक से अधिक edges
  • Path: विभिन्न vertices का ऐसा अनुक्रम जो edges से जुड़ा हो

3️⃣ ग्राफ के प्रकार (Types of Graphs)

  • 1. Simple Graph: कोई loop या parallel edge नहीं होती।
  • 2. Multigraph: दो vertices के बीच एक से अधिक edges होती हैं।
  • 3. Pseudograph: जिसमें loop मौजूद हो।
  • 4. Directed Graph (Digraph): जिसमें edges दिशा (Direction) के साथ होती हैं।
  • 5. Weighted Graph: जिसमें edges के साथ भार (Weight) जुड़ा हो।
  • 6. Complete Graph: प्रत्येक vertex हर अन्य vertex से जुड़ा हो।
  • 7. Bipartite Graph: Vertices को दो समूहों में बाँटा जा सके ताकि edges केवल अलग-अलग समूहों के बीच हों।
  • 8. Connected Graph: किसी भी दो vertices के बीच कम से कम एक path हो।
  • 9. Null Graph: कोई edge न हो।

4️⃣ पथ, साइकिल और दूरी (Path, Cycle, and Distance)

  • Path: Vertices का ऐसा अनुक्रम जिसमें edges लगातार जुड़े हों। उदाहरण: A → B → C → D
  • Cycle: ऐसा Path जो एक ही vertex से शुरू होकर उसी पर समाप्त हो। उदाहरण: A → B → C → A
  • Length of Path: Path में edges की संख्या।
  • Distance: दो vertices के बीच का सबसे छोटा Path।

5️⃣ वेटेड ग्राफ और शॉर्टेस्ट पाथ (Weighted Graph and Shortest Path)

Weighted Graph में प्रत्येक edge को एक मान (Weight) दिया जाता है जो दूरी, समय या लागत को दर्शाता है। Shortest Path वह होता है जिसका कुल Weight न्यूनतम हो।

उदाहरण:

Vertices: A, B, C, D  
Edges:  
A–B (4), A–C (2), B–C (1), B–D (5), C–D (8)

Shortest Path (A → B → D) = 4 + 5 = 9

प्रसिद्ध एल्गोरिद्म:

  • Dijkstra’s Algorithm — Single Source Shortest Path
  • Floyd–Warshall Algorithm — All Pairs Shortest Path

6️⃣ ग्राफ कलरिंग (Graph Coloring)

Graph Coloring का अर्थ है — vertices या edges को रंग देना ताकि कोई दो adjacent vertices एक ही रंग के न हों।

  • Vertex Coloring: दो जुड़े हुए vertices एक ही रंग के नहीं होंगे।
  • Edge Coloring: दो समान vertices से जुड़ी edges अलग रंग की होंगी।
  • Region Coloring: Graph के क्षेत्रों को रंगना (जैसे मानचित्र)।

Chromatic Number (χ(G)):

किसी Graph को रंगने के लिए आवश्यक न्यूनतम रंगों की संख्या। उदाहरण: Triangle Graph के लिए χ(G) = 3

7️⃣ ग्राफ के अनुप्रयोग (Applications of Graph Theory)

  • Computer Networks (Routing and Connectivity)
  • Social Network Analysis
  • Compiler Optimization (Register Allocation)
  • Map Coloring and Scheduling
  • Artificial Intelligence Path Planning

🔟 निष्कर्ष (Conclusion)

Graph Theory वास्तविक जीवन के संबंधों का गणितीय प्रतिनिधित्व है। यह संरचनाओं, नेटवर्कों और तर्क-आधारित समस्याओं के समाधान में आधारशिला का काम करती है। “Graphs connect logic, structure, and reality.”

Related Post