Planar Graphs, Multigraphs, and Weighted Graphs in Hindi – Definition, Examples, and Applications


Planar Graphs, Multigraphs, and Weighted Graphs क्या हैं?

Discrete Mathematics में Planar Graphs, Multigraphs, और Weighted Graphs महत्वपूर्ण प्रकार के ग्राफ हैं। इनका उपयोग विभिन्न समस्याओं के समाधान में किया जाता है। इस ब्लॉग में हम इन ग्राफ्स की परिभाषा, उदाहरण और उनके उपयोग को विस्तार से समझेंगे।

Planar Graphs की परिभाषा (Definition of Planar Graph)

Planar Graph वह Graph है, जिसे Plane पर इस प्रकार ड्रॉ किया जा सकता है कि उसकी कोई भी Edge एक-दूसरे को क्रॉस (Cross) न करे।

Example of Planar Graph:

K4 (Complete Graph on 4 Vertices) एक Planar Graph का उदाहरण है।

Properties of Planar Graphs (Planar Graphs की विशेषताएं)

  • Euler's Formula: V - E + F = 2 (जहाँ V = Vertices, E = Edges, और F = Faces)
  • Planar Graphs को Plane पर बिना Edges के Intersection के ड्रॉ किया जा सकता है।
  • K5 और K3,3 Non-Planar Graphs के उदाहरण हैं।

Multigraphs की परिभाषा (Definition of Multigraph)

Multigraph वह Graph है, जिसमें एक ही Pair of Vertices के बीच Multiple Edges हो सकती हैं। यह Self-loops को भी अनुमति दे सकता है।

Example of Multigraph:

दो Cities को जोड़ने वाली कई Roads को Multigraph के रूप में दर्शाया जा सकता है।

Properties of Multigraphs (Multigraphs की विशेषताएं)

  • Multigraph में एक ही Vertex Pair के बीच एक से अधिक Edges हो सकती हैं।
  • Self-loops की अनुमति होती है।
  • Multigraphs को Weighted या Unweighted रूप में दर्शाया जा सकता है।

Weighted Graphs की परिभाषा (Definition of Weighted Graph)

Weighted Graph वह Graph है, जिसमें प्रत्येक Edge के साथ एक Weight (मूल्य) जुड़ा होता है। Weight किसी Distance, Cost, या Capacity को दर्शा सकता है।

Example of Weighted Graph:

Google Maps में Cities को Nodes और उनकी बीच की Distance को Edges के Weight के रूप में दर्शाया जा सकता है।

Applications of Weighted Graphs

Weighted Graphs का उपयोग विभिन्न क्षेत्रों में किया जाता है:

  1. Shortest Path Algorithms (जैसे Dijkstra's Algorithm)
  2. Network Flow Optimization
  3. Scheduling Problems
  4. Transportation Networks
  5. Electrical Circuit Analysis

Difference between Planar Graphs, Multigraphs, and Weighted Graphs

Planar Graph Multigraph Weighted Graph
Plane पर ड्रॉ किया जा सकता है बिना Edges के Crossing के। Multiple Edges और Self-loops की अनुमति देता है। Edges के साथ एक Weight जुड़ा होता है।
Euler's Formula लागू होती है। Euler's Formula लागू नहीं होती। Cost, Distance, या Capacity को दर्शाने में उपयोगी।

Conclusion

Planar Graphs, Multigraphs, और Weighted Graphs Discrete Mathematics के महत्वपूर्ण हिस्से हैं। इनका उपयोग विभिन्न समस्याओं को हल करने और वास्तविक दुनिया की समस्याओं को मॉडल करने में किया जाता है। Graph Theory के इन प्रकारों को समझकर हम जटिल समस्याओं को सरल बना सकते हैं।

Related Post