चक्र (ग्राफ़ सिद्धांत): Difference between revisions

From Vigyanwiki
(Created page with "{{Short description|Trail in which only the first and last vertices are equal.}} File:Graph cycle.svg|thumb|एक पथ (ग्राफ़ सिद्धांत) क...")
 
No edit summary
Line 17: Line 17:


== तार रहित चक्र ==
== तार रहित चक्र ==
[[File:Graph with Chordless and Chorded Cycles.svg|thumb|right|इस ग्राफ़ में हरा चक्र A-B-C-D-E-F-A ताररहित है जबकि लाल चक्र G-H-I-J-K-L-G नहीं है। ऐसा इसलिए है क्योंकि किनारा {K, I} एक राग है।]]ग्राफ़ में एक [[ताररहित चक्र]], जिसे छेद या प्रेरित चक्र भी कहा जाता है, एक ऐसा चक्र है जिसमें चक्र के कोई भी दो शीर्ष किसी ऐसे किनारे से नहीं जुड़े होते हैं जो स्वयं चक्र से संबंधित नहीं होता है। एक एंटीहोल एक ग्राफ़ होल का [[पूरक ग्राफ]]़ है। कॉर्डलेस चक्रों का उपयोग सही ग्राफ़ को चिह्नित करने के लिए किया जा सकता है: मजबूत [[ उत्तम ग्राफ ]]़ प्रमेय के अनुसार, एक ग्राफ़ तभी सही होता है जब उसके किसी भी छेद या एंटीहोल में विषम संख्या में कोने न हों जो तीन से अधिक हो। [[कॉर्डल ग्राफ]]़, एक विशेष प्रकार का पूर्ण ग्राफ़, जिसमें तीन से अधिक आकार का कोई छेद नहीं होता है।
[[File:Graph with Chordless and Chorded Cycles.svg|thumb|right|इस ग्राफ़ में हरा चक्र A-B-C-D-E-F-A ताररहित है जबकि लाल चक्र G-H-I-J-K-L-G नहीं है। ऐसा इसलिए है क्योंकि किनारा {K, I} एक राग है।]]ग्राफ़ में एक [[ताररहित चक्र]], जिसे छेद या प्रेरित चक्र भी कहा जाता है, एक ऐसा चक्र है जिसमें चक्र के कोई भी दो शीर्ष किसी ऐसे किनारे से नहीं जुड़े होते हैं जो स्वयं चक्र से संबंधित नहीं होता है। एक एंटीहोल एक ग्राफ़ होल का [[पूरक ग्राफ]]़ है। कॉर्डलेस चक्रों का उपयोग सही ग्राफ़ को चिह्नित करने के लिए किया जा सकता है: मजबूत [[ उत्तम ग्राफ |उत्तम ग्राफ]] ़ प्रमेय के अनुसार, एक ग्राफ़ तभी सही होता है जब उसके किसी भी छेद या एंटीहोल में विषम संख्या में कोने न हों जो तीन से अधिक हो। [[कॉर्डल ग्राफ]]़, एक विशेष प्रकार का पूर्ण ग्राफ़, जिसमें तीन से अधिक आकार का कोई छेद नहीं होता है।


किसी ग्राफ का घेरा (ग्राफ़ सिद्धांत) उसके सबसे छोटे चक्र की लंबाई है; यह चक्र आवश्यक रूप से तार रहित है। केज (ग्राफ़ सिद्धांत) को डिग्री और परिधि के दिए गए संयोजनों के साथ सबसे छोटे नियमित ग्राफ़ के रूप में परिभाषित किया गया है।
किसी ग्राफ का घेरा (ग्राफ़ सिद्धांत) उसके सबसे छोटे चक्र की लंबाई है; यह चक्र आवश्यक रूप से तार रहित है। केज (ग्राफ़ सिद्धांत) को डिग्री और परिधि के दिए गए संयोजनों के साथ सबसे छोटे नियमित ग्राफ़ के रूप में परिभाषित किया गया है।
Line 31: Line 31:
निर्देशित और अप्रत्यक्ष ग्राफ़ में एक चक्र का अस्तित्व इस बात से निर्धारित किया जा सकता है कि क्या [[गहराई-पहली खोज]] (डीएफएस) को एक किनारा मिलता है जो वर्तमान शीर्ष के पूर्वज को इंगित करता है (इसमें गहराई-पहली खोज#गहराई-पहली खोज का आउटपुट शामिल है) ).<ref>{{cite book|last=Tucker|first=Alan|author-link=Alan Tucker|title=एप्लाइड कॉम्बिनेटरिक्स|year=2006|publisher=John Wiley & sons|location=Hoboken|isbn=978-0-471-73507-6|edition=5th|page=49|chapter=Chapter 2: Covering Circuits and Graph Colorings}}</ref> सभी पिछले किनारे जिन पर डीएफएस छूट जाता है वे चक्रों का हिस्सा हैं।<ref name="sedgewick">{{citation | first=Robert | last=Sedgewick | author-link=Robert Sedgewick (computer scientist) | title=Algorithms | chapter=Graph algorithms | year=1983 | publisher=Addison–Wesley | isbn=0-201-06672-6 | url-access=registration | url=https://archive.org/details/algorithms00sedg }}</ref> एक अप्रत्यक्ष ग्राफ़ में, किसी नोड के पैरेंट के किनारे को पिछले किनारे के रूप में नहीं गिना जाना चाहिए, लेकिन पहले से देखे गए किसी अन्य शीर्ष को ढूंढना पिछले किनारे का संकेत देगा। अप्रत्यक्ष ग्राफ़ के मामले में, एन-वर्टेक्स ग्राफ़ में एक चक्र खोजने के लिए केवल O(n) समय की आवश्यकता होती है, क्योंकि अधिकतम n − 1 किनारे पेड़ के किनारे हो सकते हैं।
निर्देशित और अप्रत्यक्ष ग्राफ़ में एक चक्र का अस्तित्व इस बात से निर्धारित किया जा सकता है कि क्या [[गहराई-पहली खोज]] (डीएफएस) को एक किनारा मिलता है जो वर्तमान शीर्ष के पूर्वज को इंगित करता है (इसमें गहराई-पहली खोज#गहराई-पहली खोज का आउटपुट शामिल है) ).<ref>{{cite book|last=Tucker|first=Alan|author-link=Alan Tucker|title=एप्लाइड कॉम्बिनेटरिक्स|year=2006|publisher=John Wiley & sons|location=Hoboken|isbn=978-0-471-73507-6|edition=5th|page=49|chapter=Chapter 2: Covering Circuits and Graph Colorings}}</ref> सभी पिछले किनारे जिन पर डीएफएस छूट जाता है वे चक्रों का हिस्सा हैं।<ref name="sedgewick">{{citation | first=Robert | last=Sedgewick | author-link=Robert Sedgewick (computer scientist) | title=Algorithms | chapter=Graph algorithms | year=1983 | publisher=Addison–Wesley | isbn=0-201-06672-6 | url-access=registration | url=https://archive.org/details/algorithms00sedg }}</ref> एक अप्रत्यक्ष ग्राफ़ में, किसी नोड के पैरेंट के किनारे को पिछले किनारे के रूप में नहीं गिना जाना चाहिए, लेकिन पहले से देखे गए किसी अन्य शीर्ष को ढूंढना पिछले किनारे का संकेत देगा। अप्रत्यक्ष ग्राफ़ के मामले में, एन-वर्टेक्स ग्राफ़ में एक चक्र खोजने के लिए केवल O(n) समय की आवश्यकता होती है, क्योंकि अधिकतम n − 1 किनारे पेड़ के किनारे हो सकते हैं।


कई [[ टोपोलॉजिकल छँटाई ]] एल्गोरिदम भी चक्रों का पता लगाएंगे, क्योंकि वे टोपोलॉजिकल ऑर्डर के अस्तित्व में बाधाएं हैं। इसके अलावा, यदि एक निर्देशित ग्राफ को दृढ़ता से जुड़े घटकों में विभाजित किया गया है, तो चक्र केवल घटकों के भीतर मौजूद होते हैं, उनके बीच नहीं, क्योंकि चक्र दृढ़ता से जुड़े होते हैं।<ref name="sedgewick" />
कई [[ टोपोलॉजिकल छँटाई |टोपोलॉजिकल छँटाई]] एल्गोरिदम भी चक्रों का पता लगाएंगे, क्योंकि वे टोपोलॉजिकल ऑर्डर के अस्तित्व में बाधाएं हैं। इसके अलावा, यदि एक निर्देशित ग्राफ को दृढ़ता से जुड़े घटकों में विभाजित किया गया है, तो चक्र केवल घटकों के भीतर मौजूद होते हैं, उनके बीच नहीं, क्योंकि चक्र दृढ़ता से जुड़े होते हैं।<ref name="sedgewick" />


निर्देशित ग्राफ़ के लिए, वितरित संदेश-आधारित एल्गोरिदम का उपयोग किया जा सकता है। ये एल्गोरिदम इस विचार पर भरोसा करते हैं कि एक चक्र में एक शीर्ष द्वारा भेजा गया संदेश स्वयं वापस आ जाएगा।
निर्देशित ग्राफ़ के लिए, वितरित संदेश-आधारित एल्गोरिदम का उपयोग किया जा सकता है। ये एल्गोरिदम इस विचार पर भरोसा करते हैं कि एक चक्र में एक शीर्ष द्वारा भेजा गया संदेश स्वयं वापस आ जाएगा।
Line 50: Line 50:


== एल्गोरिथम ==
== एल्गोरिथम ==
प्रत्येक शीर्ष v के लिए: विज़िट(v) = गलत, समाप्त(v) = गलत
<syntaxhighlight>
प्रत्येक शीर्ष v के लिए:
For every vertex v: visited(v) = false, finished(v) = false
  डीएफएस(वी)
For every vertex v:
 
  DFS(v)
डीएफएस(वी):
</syntaxhighlight><syntaxhighlight>
  यदि समाप्त हो गया(v)
DFS(v):
    वापस करना
  if finished(v)
  यदि दौरा किया गया(v)
    return
      साइकिल मिल गई और वापस आ गए
  if visited(v)
  विज़िट किया गया (v) = सत्य
    "Cycle found" and return
  प्रत्येक पड़ोसी के लिए w
  visited(v) = true
    डीएफएस(डब्ल्यू)
  for every neighbour w
  समाप्त (v) = सत्य
    DFS(w)
 
  finished(v) = true
नेबर का मतलब निर्देशित और अप्रत्यक्ष ग्राफ़ दोनों के लिए v से जुड़े सभी शीर्ष हैं, सिवाय उस शीर्ष को छोड़कर जिसे DFS(v) कहा जाता है। यह एल्गोरिथम को तुच्छ चक्रों को पकड़ने से भी बचाता है, जो कि कम से कम एक किनारे वाले प्रत्येक अप्रत्यक्ष ग्राफ़ में होता है।
</syntaxhighlight>नेबर का मतलब निर्देशित और अप्रत्यक्ष ग्राफ़ दोनों के लिए v से जुड़े सभी शीर्ष हैं, सिवाय उस शीर्ष को छोड़कर जिसे DFS(v) कहा जाता है। यह एल्गोरिथम को तुच्छ चक्रों को पकड़ने से भी बचाता है, जो कि कम से कम एक किनारे वाले प्रत्येक अप्रत्यक्ष ग्राफ़ में होता है।


== प्रोग्रामिंग ==
== प्रोग्रामिंग ==
[[प्रोग्रामिंग भाषा]] C_Sharp_(प्रोग्रामिंग_भाषा)|C# में निम्नलिखित उदाहरण एडजेंसी सूचियों का उपयोग करके एक अप्रत्यक्ष ग्राफ़ के एक कार्यान्वयन को दर्शाता है। अप्रत्यक्ष ग्राफ़ को Class_(computer_programming) UndirectedGraph के रूप में घोषित किया गया है। प्रोग्राम को निष्पादित करने में मुख्य विधि_(कंप्यूटर_प्रोग्रामिंग) का उपयोग किया जाता है, जो - यदि कोई मौजूद है - कंसोल पर सबसे छोटा, गैर-तुच्छ चक्र प्रिंट करता है।<ref>GeeksforGeeks: [https://www.geeksforgeeks.org/shortest-cycle-in-an-undirected-unweighted-graph/ Shortest cycle in an undirected unweighted graph] {{Webarchive|url=https://web.archive.org/web/20220111220148/https://www.geeksforgeeks.org/shortest-cycle-in-an-undirected-unweighted-graph/ |date=2022-01-11 }}</ref><सिंटैक्सहाइलाइट लैंग = सी# >
[[प्रोग्रामिंग भाषा]] C_Sharp_(प्रोग्रामिंग_भाषा)|C# में निम्नलिखित उदाहरण एडजेंसी सूचियों का उपयोग करके एक अप्रत्यक्ष ग्राफ़ के एक कार्यान्वयन को दर्शाता है। अप्रत्यक्ष ग्राफ़ को Class_(computer_programming) UndirectedGraph के रूप में घोषित किया गया है। प्रोग्राम को निष्पादित करने में मुख्य विधि_(कंप्यूटर_प्रोग्रामिंग) का उपयोग किया जाता है, जो - यदि कोई मौजूद है - कंसोल पर सबसे छोटा, गैर-तुच्छ चक्र प्रिंट करता है।<ref>GeeksforGeeks: [https://www.geeksforgeeks.org/shortest-cycle-in-an-undirected-unweighted-graph/ Shortest cycle in an undirected unweighted graph] {{Webarchive|url=https://web.archive.org/web/20220111220148/https://www.geeksforgeeks.org/shortest-cycle-in-an-undirected-unweighted-graph/ |date=2022-01-11 }}</ref><syntaxhighlight>
सिस्टम का उपयोग करना;
using System;                                                                                            
System.Collections.Generic का उपयोग करना;
using System.Collections.Generic;                                                                          
 
                                                                                                             
// ग्राफ़ के शीर्षों के लिए वर्ग की घोषणा करता है
// Declares the class for the vertices of the graph                                                         
क्लास नोड
class Node                                                                                               
{
{                                                                                              
सार्वजनिक पूर्णांक सूचकांक;
public int index;                                                                              
सार्वजनिक स्ट्रिंग मान;
public string value;                                                                              
सार्वजनिक हैशसेट<नोड> आसन्न नोड्स = नया हैशसेट<नोड>(); // पड़ोसी शीर्षों का सेट
public HashSet<Node> adjacentNodes = new HashSet<Node>(); // Set of neighbour vertices                 
}
}                                                                                                            
 
                                                                                                             
// अप्रत्यक्ष ग्राफ़ के लिए वर्ग घोषित करता है
// Declares the class for the undirected graph
कक्षा अप्रत्यक्ष ग्राफ़
class UndirectedGraph                                                                                         
{
{                                                                                                    
सार्वजनिक हैशसेट<नोड> नोड्स = नया हैशसेट<नोड>();
public HashSet<Node> nodes = new HashSet<Node>();                                                  
 
                                                                                                 
// यह विधि नोड1 और नोड2 को एक दूसरे से जोड़ती है
// This method connects node1 and node2 with each other                                       
सार्वजनिक शून्य कनेक्टनोड्स (नोड नोड 1, नोड नोड 2)
public void ConnectNodes(Node node1, Node node2)                                                    
{
{
node1.adjacentNodes.Add(node2);
node1.adjacentNodes.Add(node2);                                                  
node2.adjacentNodes.Add(node1);
node2.adjacentNodes.Add(node1);                                                            
}
}                                                                                            
}
}                                                                                                        
 
कक्षा कार्यक्रम
{
// यह विधि चक्र को ए, बी, सी, ... टेक्स्ट के रूप में लौटाती है।
सार्वजनिक स्थैतिक स्ट्रिंग ToString(सूची<नोड> चक्र)
{
स्ट्रिंग टेक्स्ट = ;
for (int i = 0; i <cycle.Count; i++) // फॉर-लूप, शीर्षों को पुनरावृत्त करते हुए
{
टेक्स्ट += चक्र[i].मूल्य + , ;
}
टेक्स्ट = टेक्स्ट.सबस्ट्रिंग(0, टेक्स्ट.लंबाई - 2);
वापसी पाठ;
}
 
// प्रोग्राम को निष्पादित करने वाली मुख्य विधि
सार्वजनिक स्थैतिक शून्य main (String [] args)
{
// 5 शीर्षों की घोषणा और आरंभ करता है
नोड नोड 1 = नया नोड {सूचकांक = 0, मान = ए };
नोड नोड2 = नया नोड{सूचकांक = 1, मान = बी };
नोड नोड 3 = नया नोड {सूचकांक = 2, मान = सी };
नोड नोड4 = नया नोड{सूचकांक = 3, मान = डी };
// शीर्षों को पकड़े हुए एक सरणी की घोषणा और आरंभ करता है
नोड[] नोड्स = {नोड1, नोड2, नोड3, नोड4};
// एक अप्रत्यक्ष ग्राफ़ बनाता है
अप्रत्यक्ष ग्राफ अप्रत्यक्ष ग्राफ = नया अप्रत्यक्ष ग्राफ();
int numberOfNodes = nodes.Length;
for (int i = 0; i < numberOfNodes; i++) // फॉर-लूप, सभी शीर्षों को पुनरावृत्त करते हुए
{
undirectedGraph.nodes.Add(nodes[i]); // ग्राफ़ में शीर्ष जोड़ता है
}
// ग्राफ़ के शीर्षों को एक दूसरे से जोड़ता है
undirectedGraph.ConnectNodes(node1, node1);
undirectedGraph.ConnectNodes(node1, node2);
undirectedGraph.ConnectNodes(node2, node3);
undirectedGraph.ConnectNodes(node3, node1);
undirectedGraph.ConnectNodes(node3, node4);
undirectedGraph.ConnectNodes(node4, node1);


HashSet<Node> newNodes = new HashSet<Node>(nodes); // पुनरावृत्त करने के लिए नए शीर्षों का सेट
class Program                                                                                   
हैशसेट<सूची<नोड>> पथ = नया हैशसेट<सूची<नोड>>(); // वर्तमान पथों का सेट
for (int i = 0; i < numberOfNodes; i++) // फॉर-लूप, ग्राफ़ के सभी शीर्षों को पुनरावृत्त करते हुए
{
नोड नोड = नोड्स[i];
newNodes.जोड़ें(नोड); // पुनरावृत्त करने के लिए नए शीर्षों के सेट में शीर्ष जोड़ें
सूची<नोड> पथ = नई सूची<नोड>();
पथ.जोड़ें(नोड);
पथ.जोड़ें(पथ); // प्रत्येक नोड के लिए प्रारंभिक शीर्ष के रूप में एक पथ जोड़ता है
}
हैशसेट<सूची<नोड>> सबसे छोटा चक्र = नया हैशसेट<सूची<नोड>>(); // सबसे छोटे चक्रों का सेट
int lengthOfCycles = 0; // सबसे छोटे चक्र की लंबाई
बूल साइकलअरेफाउंड = गलत; // साइकिलें मिलीं या नहीं
while (!cyclesAreFound && newNodes.Count > 0) // जब तक हमारे पास पुनरावृत्त करने के लिए शीर्ष शेष थे
{
newNodes.Clear(); // पुनरावृत्त करने के लिए नोड्स के सेट को खाली करें
HashSet<List<Node>> newPaths = new HashSet<List<Node>>(); // नए पाए गए पथों का सेट
foreach (पथों में सूची<नोड> पथ) // foreach-लूप, सभी मौजूदा पथों को पुनरावृत्त करता हुआ
{
नोड अंतिमनोड = पथ[पथ.गणना - 1];
newNodes.Add(lastNode); // पथ के अंतिम शीर्ष को पुनरावृत्त करने के लिए शीर्षों की सूची में जोड़ता है
foreach (lastNode.adjacentNodes में नोड अगला नोड) // foreach-लूप, पिछले नोड के सभी पड़ोसियों को पुनरावृत्त करता है
{
यदि (पथ.गणना >= 3 && पथ[0] == अगलानोड) // यदि 3 से अधिक या बराबर लंबाई वाला एक चक्र पाया गया
{
साइकलअरेफाउंड = सत्य;
सबसे छोटा चक्र। जोड़ें (पथ); // चक्रों के सेट में पथ जोड़ता है
lengthOfCycles = पथ.गिनती;
}
if (!path.Contains(nextNode)) // यदि पथ में पड़ोसी शामिल नहीं है
{
newNodes.Add(nextNode); // पुनरावृत्त करने के लिए शीर्षों के सेट में पड़ोसी को जोड़ता है
// एक नया पथ बनाता है
सूची<नोड> नयापथ = नई सूची<नोड>();
newPath.AddRange(पथ); // वर्तमान पथ के शीर्ष को सही क्रम में नए पथ में जोड़ता है
न्यूपावें.जोड़ें(अगलानोड); // पड़ोसी को नए पथ में जोड़ता है
newPaths.Add(newPath); // नए पाए गए पथों के सेट में पथ जोड़ता है
}
}
}
पथ = नए पथ; // वर्तमान पथों के सेट को अद्यतन करता है
}
यदि (shortestCycles.Count > 0) // यदि चक्र पाए गए
{
कंसोल.राइटलाइन (ग्राफ़ में + शॉर्टेस्टसाइकल्स.काउंट + लंबाई के चक्र + लेंथऑफसाइकल्स + शामिल हैं।); // कंसोल पर प्रिंट करें
foreach (सबसे छोटे चक्रों में सूची<नोड> चक्र) // foreach-लूप, सभी पाए गए चक्रों को पुनरावृत्त करता हुआ
{
कंसोल.राइटलाइन(टूस्ट्रिंग(चक्र)); // कंसोल पर प्रिंट करें
}
}
अन्य
{
{
कंसोल.राइटलाइन (ग्राफ़ में कोई चक्र नहीं है। ); // कंसोल पर प्रिंट करें
// This method returns the cycle in the form A, B, C, ... as text.                                 
}
public static string ToString(List<Node> cycle)                                                     
 
{                                                                                               
कंसोल.रीडलाइन();
string text = "";
}
for (int i = 0; i < cycle.Count; i++) // for-loop, iterating the vertices                     
{
text += cycle[i].value + ", ";                                                 
}
text = text.Substring(0, text.Length - 2);                                               
return text;                                                                             
}                                                                                                 
// Main method executing the program                                                             
public static void Main(string[] args)                                                           
{                                                                                             
// Declares and initialises 5 vertices                                             
Node node1 = new Node{index = 0, value = "A"};                                         
Node node2 = new Node{index = 1, value = "B"};                                             
Node node3 = new Node{index = 2, value = "C"};                                           
Node node4 = new Node{index = 3, value = "D"};                                             
// Declares and initialises an array holding the vertices                                   
Node[] nodes = {node1, node2, node3, node4};                                             
// Creates an undirected graph                           
UndirectedGraph undirectedGraph = new UndirectedGraph();
int numberOfNodes = nodes.Length;
for (int i = 0; i < numberOfNodes; i++) // for-loop, iterating all vertices
{                                                                                       
undirectedGraph.nodes.Add(nodes[i]); // Adds the vertices to the graph
}                                                                                         
// Connects the vertices of the graph with each other
undirectedGraph.ConnectNodes(node1, node1);                                               
undirectedGraph.ConnectNodes(node1, node2);
undirectedGraph.ConnectNodes(node2, node3);
undirectedGraph.ConnectNodes(node3, node1);
undirectedGraph.ConnectNodes(node3, node4);
undirectedGraph.ConnectNodes(node4, node1);
                                                                                       
HashSet<Node> newNodes = new HashSet<Node>(nodes); // Set of new vertices to iterate
HashSet<List<Node>> paths = new HashSet<List<Node>>(); // Set of current paths
for (int i = 0; i < numberOfNodes; i++) // for-loop, iterating all vertices of the graph
{                                                                                       
Node node = nodes[i];
newNodes.Add(node); // Add the vertex to the set of new vertices to iterate
List<Node> path = new List<Node>();
path.Add(node);                                                                   
paths.Add(path); // Adds a path for each node as a starting vertex
}                                                                                         
HashSet<List<Node>> shortestCycles = new HashSet<List<Node>>(); // Set of shortest cycles
int lengthOfCycles = 0; // Length of shortest cycles
bool cyclesAreFound = false; // Whether or not cycles were found at all
while (!cyclesAreFound && newNodes.Count > 0) // As long as we still had vertices to iterate
{
newNodes.Clear(); // Empties the set of nodes to iterate
HashSet<List<Node>> newPaths = new HashSet<List<Node>>(); // Set of newly found paths
foreach (List<Node> path in paths) // foreach-loop, iterating all current paths
{
Node lastNode = path[path.Count - 1];
newNodes.Add(lastNode); // Adds the final vertex of the path to the list of vertices to iterate
foreach (Node nextNode in lastNode.adjacentNodes) // foreach-loop, iterating all neighbours of the previous node
{
if (path.Count >= 3 && path[0] == nextNode) // If a cycle with length greater or equal 3 was found
{
cyclesAreFound = true;
shortestCycles.Add(path); // Adds the path to the set of cycles
lengthOfCycles = path.Count;
}
if (!path.Contains(nextNode)) // If the path doesn't contain the neighbour
{
newNodes.Add(nextNode); // Adds the neighbour to the set of vertices to iterate
// Creates a new path
List<Node> newPath = new List<Node>();
newPath.AddRange(path); // Adds the current path's vertex to the new path in the correct order
newPath.Add(nextNode); // Adds the neighbour to the new path
newPaths.Add(newPath); // Adds the path to the set of newly found paths
}
}
}
paths = newPaths; // Updates the set of current paths
}
if (shortestCycles.Count > 0) // If cycles were found
{
Console.WriteLine("The graph contains " + shortestCycles.Count + " cycles of length " + lengthOfCycles + "."); // Print to console
foreach (List<Node> cycle in shortestCycles) // foreach-loop, iterating all found cycles
{
Console.WriteLine(ToString(cycle)); // Print to console
}
}
else
{
Console.WriteLine("The graph contains no cycles."); // Print to console
}
Console.ReadLine();
}
}
}
</सिंटैक्सहाइलाइट>
</syntaxhighlight>


== चक्र द्वारा ग्राफ़ को कवर करना ==
== चक्र द्वारा ग्राफ़ को कवर करना ==

Revision as of 15:19, 16 July 2023

एक पथ (ग्राफ़ सिद्धांत) को चित्रित करने के लिए किनारों को रंगीन करने वाला एक ग्राफ #वॉक, ट्रेल, और पथ H-A-B-A-H को हरे रंग में, एक सर्किट जो एक बंद वॉक है जिसमें सभी किनारे अलग-अलग हैं B-D-E -F-D-C-B नीले रंग में, और एक चक्र जो एक बंद चाल है जिसमें सभी शीर्ष अलग-अलग हैं लेकिन पहला और अंतिम शीर्ष H-D-G-H लाल रंग में है।

ग्राफ़ सिद्धांत में, ग्राफ़ (असतत गणित) में एक चक्र एक गैर-रिक्त पथ (ग्राफ सिद्धांत) #वॉक, ट्रेल और पथ है जिसमें केवल पहला और अंतिम वर्टेक्स (ग्राफ़ सिद्धांत) बराबर होते हैं। निर्देशित ग्राफ में एक निर्देशित चक्र एक गैर-रिक्त पथ है (ग्राफ सिद्धांत)#निर्देशित चलना, निर्देशित पथ और निर्देशित पथ जिसमें केवल पहला और अंतिम शीर्ष बराबर होते हैं।

बिना चक्र वाले ग्राफ को एसाइक्लिक ग्राफ कहा जाता है। निर्देशित चक्रों के बिना एक निर्देशित ग्राफ को निर्देशित अचक्रीय ग्राफ कहा जाता है। चक्रों के बिना जुड़े हुए ग्राफ़ को ट्री (ग्राफ़ सिद्धांत) कहा जाता है।

परिभाषाएँ

सर्किट और चक्र

  • एक सर्किट एक गैर-रिक्त पथ है (ग्राफ़ सिद्धांत)#वॉक, ट्रेल और पथ जिसमें पहला और अंतिम शीर्ष बराबर होते हैं (बंद ट्रेल)।[1]
होने देना G = (V, E, ϕ) एक ग्राफ बनें. सर्किट एक गैर-रिक्त पथ है (e1, e2, …, en) शीर्ष क्रम के साथ (v1, v2, …, vn, v1).
  • चक्र या सरल परिपथ एक ऐसा परिपथ है जिसमें केवल प्रथम और अंतिम शीर्ष बराबर होते हैं।[1]

निर्देशित सर्किट और निर्देशित चक्र

  • एक निर्देशित सर्किट एक गैर-रिक्त पथ है (ग्राफ़ सिद्धांत)#निर्देशित चलना, निर्देशित पथ, और निर्देशित पथ जिसमें पहला और अंतिम शीर्ष बराबर होते हैं (बंद निर्देशित पथ)।[1]
होने देना G = (V, E, ϕ) एक निर्देशित ग्राफ बनें। एक निर्देशित सर्किट एक गैर-रिक्त निर्देशित पथ है (e1, e2, …, en) शीर्ष क्रम के साथ (v1, v2, …, vn, v1).
  • एक निर्देशित चक्र या सरल निर्देशित सर्किट एक निर्देशित सर्किट होता है जिसमें केवल पहला और अंतिम शीर्ष बराबर होता है।[1]

तार रहित चक्र

इस ग्राफ़ में हरा चक्र A-B-C-D-E-F-A ताररहित है जबकि लाल चक्र G-H-I-J-K-L-G नहीं है। ऐसा इसलिए है क्योंकि किनारा {K, I} एक राग है।

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

किसी ग्राफ का घेरा (ग्राफ़ सिद्धांत) उसके सबसे छोटे चक्र की लंबाई है; यह चक्र आवश्यक रूप से तार रहित है। केज (ग्राफ़ सिद्धांत) को डिग्री और परिधि के दिए गए संयोजनों के साथ सबसे छोटे नियमित ग्राफ़ के रूप में परिभाषित किया गया है।

एक परिधीय चक्र एक ग्राफ़ में एक चक्र है जिसमें यह गुण होता है कि चक्र पर नहीं होने वाले प्रत्येक दो किनारों को एक पथ से जोड़ा जा सकता है जिसके आंतरिक कोने चक्र से बचते हैं। ऐसे ग्राफ़ में जो किसी चक्र में एक किनारे जोड़कर नहीं बनता है, एक परिधीय चक्र एक प्रेरित चक्र होना चाहिए।

साइकिल स्पेस

चक्र शब्द ग्राफ़ के चक्र स्थान के एक तत्व को भी संदर्भित कर सकता है। कई चक्र स्थान हैं, प्रत्येक गुणांक क्षेत्र या रिंग के लिए एक। सबसे आम है बाइनरी साइकल स्पेस (आमतौर पर इसे केवल साइकल स्पेस कहा जाता है), जिसमें किनारे के सेट होते हैं जिनकी प्रत्येक शीर्ष पर डिग्री भी होती है; यह दो-तत्व परिमित क्षेत्र पर एक सदिश स्थल बनाता है। वेब्लेन के प्रमेय के अनुसार, चक्र स्थान का प्रत्येक तत्व सरल चक्रों के किनारे-असंबद्ध संघ के रूप में बन सकता है। ग्राफ़ का चक्र आधार सरल चक्रों का एक सेट है जो चक्र स्थान का आधार (रैखिक बीजगणित) बनाता है।[2] बीजगणितीय टोपोलॉजी के विचारों का उपयोग करते हुए, बाइनरी चक्र स्थान को अन्य रिंग (गणित) जैसे पूर्णांक, तर्कसंगत या वास्तविक संख्याओं आदि पर वेक्टर रिक्त स्थान या मॉड्यूल (गणित) में सामान्यीकृत किया जाता है।[3]


चक्र का पता लगाना

निर्देशित और अप्रत्यक्ष ग्राफ़ में एक चक्र का अस्तित्व इस बात से निर्धारित किया जा सकता है कि क्या गहराई-पहली खोज (डीएफएस) को एक किनारा मिलता है जो वर्तमान शीर्ष के पूर्वज को इंगित करता है (इसमें गहराई-पहली खोज#गहराई-पहली खोज का आउटपुट शामिल है) ).[4] सभी पिछले किनारे जिन पर डीएफएस छूट जाता है वे चक्रों का हिस्सा हैं।[5] एक अप्रत्यक्ष ग्राफ़ में, किसी नोड के पैरेंट के किनारे को पिछले किनारे के रूप में नहीं गिना जाना चाहिए, लेकिन पहले से देखे गए किसी अन्य शीर्ष को ढूंढना पिछले किनारे का संकेत देगा। अप्रत्यक्ष ग्राफ़ के मामले में, एन-वर्टेक्स ग्राफ़ में एक चक्र खोजने के लिए केवल O(n) समय की आवश्यकता होती है, क्योंकि अधिकतम n − 1 किनारे पेड़ के किनारे हो सकते हैं।

कई टोपोलॉजिकल छँटाई एल्गोरिदम भी चक्रों का पता लगाएंगे, क्योंकि वे टोपोलॉजिकल ऑर्डर के अस्तित्व में बाधाएं हैं। इसके अलावा, यदि एक निर्देशित ग्राफ को दृढ़ता से जुड़े घटकों में विभाजित किया गया है, तो चक्र केवल घटकों के भीतर मौजूद होते हैं, उनके बीच नहीं, क्योंकि चक्र दृढ़ता से जुड़े होते हैं।[5]

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

चक्र पहचान के अनुप्रयोगों में समवर्ती प्रणालियों में गतिरोध का पता लगाने के लिए प्रतीक्षा-ग्राफ़ का उपयोग शामिल है।[6]


एल्गोरिथम

For every vertex v: visited(v) = false, finished(v) = false
For every vertex v:
  DFS(v)
DFS(v):
  if finished(v)
    return
  if visited(v)
    "Cycle found" and return
  visited(v) = true
  for every neighbour w
    DFS(w)
  finished(v) = true

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

प्रोग्रामिंग

प्रोग्रामिंग भाषा C_Sharp_(प्रोग्रामिंग_भाषा)|C# में निम्नलिखित उदाहरण एडजेंसी सूचियों का उपयोग करके एक अप्रत्यक्ष ग्राफ़ के एक कार्यान्वयन को दर्शाता है। अप्रत्यक्ष ग्राफ़ को Class_(computer_programming) UndirectedGraph के रूप में घोषित किया गया है। प्रोग्राम को निष्पादित करने में मुख्य विधि_(कंप्यूटर_प्रोग्रामिंग) का उपयोग किया जाता है, जो - यदि कोई मौजूद है - कंसोल पर सबसे छोटा, गैर-तुच्छ चक्र प्रिंट करता है।[7]

using System;                                                                                             
using System.Collections.Generic;                                                                           
                                                                                                              
// Declares the class for the vertices of the graph                                                          
class Node                                                                                                
{                                                                                                
	public int index;                                                                               
	public string value;                                                                                
	public HashSet<Node> adjacentNodes = new HashSet<Node>(); // Set of neighbour vertices                  
}                                                                                                              
                                                                                                               
// Declares the class for the undirected graph
class UndirectedGraph                                                                                          
{                                                                                                      
	public HashSet<Node> nodes = new HashSet<Node>();                                                    
	                                                                                                  
	// This method connects node1 and node2 with each other                                         
	public void ConnectNodes(Node node1, Node node2)                                                     
	{
		node1.adjacentNodes.Add(node2);                                                    
		node2.adjacentNodes.Add(node1);                                                              
	}                                                                                              
}                                                                                                         

class Program                                                                                    
{
	// This method returns the cycle in the form A, B, C, ... as text.                                   
	public static string ToString(List<Node> cycle)                                                      
	{                                                                                                 
		string text = "";
		for (int i = 0; i < cycle.Count; i++) // for-loop, iterating the vertices                      
		{ 
			text += cycle[i].value + ", ";                                                   
		}
		text = text.Substring(0, text.Length - 2);                                                
		return text;                                                                               
	}                                                                                                  
	
	// Main method executing the program                                                               
	public static void Main(string[] args)                                                             
	{                                                                                              
		// Declares and initialises 5 vertices                                              
		Node node1 = new Node{index = 0, value = "A"};                                           
		Node node2 = new Node{index = 1, value = "B"};                                              
		Node node3 = new Node{index = 2, value = "C"};                                            
		Node node4 = new Node{index = 3, value = "D"};                                              
		// Declares and initialises an array holding the vertices                                     
		Node[] nodes = {node1, node2, node3, node4};                                              
		// Creates an undirected graph                             
		UndirectedGraph undirectedGraph = new UndirectedGraph();
		int numberOfNodes = nodes.Length;
		for (int i = 0; i < numberOfNodes; i++) // for-loop, iterating all vertices
		{                                                                                        
			undirectedGraph.nodes.Add(nodes[i]); // Adds the vertices to the graph
		}                                                                                          
		// Connects the vertices of the graph with each other
		undirectedGraph.ConnectNodes(node1, node1);                                                
		undirectedGraph.ConnectNodes(node1, node2);
		undirectedGraph.ConnectNodes(node2, node3);
		undirectedGraph.ConnectNodes(node3, node1);
		undirectedGraph.ConnectNodes(node3, node4);
		undirectedGraph.ConnectNodes(node4, node1);
		                                                                                        
		HashSet<Node> newNodes = new HashSet<Node>(nodes); // Set of new vertices to iterate
		HashSet<List<Node>> paths = new HashSet<List<Node>>(); // Set of current paths
		for (int i = 0; i < numberOfNodes; i++) // for-loop, iterating all vertices of the graph
		{                                                                                         
			Node node = nodes[i];
			newNodes.Add(node); // Add the vertex to the set of new vertices to iterate
			List<Node> path = new List<Node>();
			path.Add(node);                                                                    
			paths.Add(path); // Adds a path for each node as a starting vertex
		}                                                                                          
		HashSet<List<Node>> shortestCycles = new HashSet<List<Node>>(); // Set of shortest cycles
		int lengthOfCycles = 0; // Length of shortest cycles
		bool cyclesAreFound = false; // Whether or not cycles were found at all
		while (!cyclesAreFound && newNodes.Count > 0) // As long as we still had vertices to iterate
		{
			newNodes.Clear(); // Empties the set of nodes to iterate
			HashSet<List<Node>> newPaths = new HashSet<List<Node>>(); // Set of newly found paths
			foreach (List<Node> path in paths) // foreach-loop, iterating all current paths
			{
				Node lastNode = path[path.Count - 1];
				newNodes.Add(lastNode); // Adds the final vertex of the path to the list of vertices to iterate
				foreach (Node nextNode in lastNode.adjacentNodes) // foreach-loop, iterating all neighbours of the previous node
				{
					if (path.Count >= 3 && path[0] == nextNode) // If a cycle with length greater or equal 3 was found
					{
						cyclesAreFound = true;
						shortestCycles.Add(path); // Adds the path to the set of cycles
						lengthOfCycles = path.Count;
					}
					if (!path.Contains(nextNode)) // If the path doesn't contain the neighbour
					{
						newNodes.Add(nextNode); // Adds the neighbour to the set of vertices to iterate
						// Creates a new path
						List<Node> newPath = new List<Node>();
						newPath.AddRange(path); // Adds the current path's vertex to the new path in the correct order
						newPath.Add(nextNode); // Adds the neighbour to the new path
						newPaths.Add(newPath); // Adds the path to the set of newly found paths
					}
				}
			}
			paths = newPaths; // Updates the set of current paths
		}
		if (shortestCycles.Count > 0) // If cycles were found
		{
			Console.WriteLine("The graph contains " + shortestCycles.Count + " cycles of length " + lengthOfCycles + "."); // Print to console
			foreach (List<Node> cycle in shortestCycles) // foreach-loop, iterating all found cycles
			{
				Console.WriteLine(ToString(cycle)); // Print to console
			}
		}
		else
		{
			Console.WriteLine("The graph contains no cycles."); // Print to console
		}
		
		Console.ReadLine();
	}
}

चक्र द्वारा ग्राफ़ को कवर करना

कोनिग्सबर्ग के सात पुलों पर अपने 1736 के पेपर में, जिसे व्यापक रूप से ग्राफ सिद्धांत का जन्म माना जाता है, लियोनहार्ड यूलर ने साबित किया कि, एक सीमित अप्रत्यक्ष ग्राफ के लिए एक बंद चाल होती है जो प्रत्येक किनारे पर बिल्कुल एक बार जाती है (इसे एक बंद निशान बनाती है), यह आवश्यक और पर्याप्त है कि यह अलग-अलग शीर्षों को छोड़कर जुड़ा हो (अर्थात, सभी किनारे एक घटक में समाहित हों) और प्रत्येक शीर्ष पर सम डिग्री हो। एक निर्देशित ग्राफ़ में प्रत्येक किनारे पर ठीक एक बार जाने वाले बंद वॉक के अस्तित्व के लिए संबंधित लक्षण वर्णन यह है कि ग्राफ़ दृढ़ता से जुड़ा हुआ है और प्रत्येक शीर्ष पर आने वाले और बाहर जाने वाले किनारों की समान संख्या है। किसी भी स्थिति में, परिणामी बंद पथ को यूलेरियन पथ के रूप में जाना जाता है। यदि एक परिमित अप्रत्यक्ष ग्राफ के प्रत्येक शीर्ष पर सम डिग्री है, चाहे वह जुड़ा हुआ हो या नहीं, तो सरल चक्रों का एक सेट ढूंढना संभव है जो एक साथ प्रत्येक किनारे को बिल्कुल एक बार कवर करते हैं: यह वेब्लेन का प्रमेय है।[8] जब एक कनेक्टेड ग्राफ यूलर के प्रमेय की शर्तों को पूरा नहीं करता है, तो मार्ग निरीक्षण समस्या को हल करके प्रत्येक किनारे को कम से कम एक बार कवर करने वाली न्यूनतम लंबाई का एक बंद चलना बहुपद समय में पाया जा सकता है।

एक एकल सरल चक्र खोजने की समस्या जो किनारों को कवर करने के बजाय प्रत्येक शीर्ष को ठीक एक बार कवर करती है, बहुत कठिन है। ऐसे चक्र को हैमिल्टनियन चक्र के रूप में जाना जाता है, और यह निर्धारित करना कि यह अस्तित्व में है या नहीं, एनपी-पूर्ण है।[9] ग्राफ़ के उन वर्गों के संबंध में बहुत से शोध प्रकाशित किए गए हैं जिनमें हैमिल्टनियन चक्र शामिल होने की गारंटी दी जा सकती है; एक उदाहरण ओरे का प्रमेय है कि एक हैमिल्टनियन चक्र हमेशा एक ग्राफ़ में पाया जा सकता है जिसके लिए प्रत्येक गैर-आसन्न युग्म शीर्षों की डिग्री ग्राफ़ में कम से कम शीर्षों की कुल संख्या के बराबर होती है।[10] चक्र डबल कवर अनुमान बताता है कि, प्रत्येक ब्रिजलेस ग्राफ़ के लिए, सरल चक्रों का एक समूह मौजूद होता है जो ग्राफ़ के प्रत्येक किनारे को ठीक दो बार कवर करता है। यह साबित करना कि यह सत्य है (या इसका प्रति उदाहरण ढूंढना) एक खुली समस्या बनी हुई है।[11]


चक्र द्वारा परिभाषित ग्राफ वर्ग

ग्राफ़ के कई महत्वपूर्ण वर्गों को उनके चक्रों द्वारा परिभाषित या चित्रित किया जा सकता है। इसमे शामिल है:

  • द्विदलीय ग्राफ, विषम चक्रों के बिना एक ग्राफ (विषम संख्या में शीर्षों वाला चक्र)
  • कैक्टस ग्राफ़, एक ग्राफ़ जिसमें प्रत्येक गैर-तुच्छ द्विसंबद्ध घटक एक चक्र है
  • चक्र ग्राफ ़, एक ग्राफ़ जिसमें एक चक्र होता है
  • कॉर्डल ग्राफ, एक ग्राफ जिसमें प्रत्येक प्रेरित चक्र एक त्रिकोण है
  • निर्देशित चक्रीय ग्राफ, एक निर्देशित ग्राफ जिसमें कोई निर्देशित चक्र नहीं है
  • रेखा पूर्ण ग्राफ, एक ऐसा ग्राफ जिसमें प्रत्येक विषम चक्र एक त्रिभुज होता है

रेखा पूर्ण ग्राफ़, एक ऐसा ग्राफ जिसमें कोई प्रेरित चक्र या तीन से अधिक विषम लंबाई के उनके पूरक नहीं हैं

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

यह भी देखें

संदर्भ

  1. ↑ 1.0 1.1 1.2 1.3 Bender & Williamson 2010, p. 164.
  2. ↑ Gross, Jonathan L.; Yellen, Jay (2005), "4.6 Graphs and Vector Spaces", Graph Theory and Its Applications (2nd ed.), CRC Press, pp. 197–207, ISBN 9781584885054, archived from the original on 2023-02-04, retrieved 2016-09-27.
  3. ↑ Diestel, Reinhard (2012), "1.9 Some linear algebra", Graph Theory, Graduate Texts in Mathematics, vol. 173, Springer, pp. 23–28, archived from the original on 2023-02-04, retrieved 2016-09-27.
  4. ↑ Tucker, Alan (2006). "Chapter 2: Covering Circuits and Graph Colorings". एप्लाइड कॉम्बिनेटरिक्स (5th ed.). Hoboken: John Wiley & sons. p. 49. ISBN 978-0-471-73507-6.
  5. ↑ 5.0 5.1 Sedgewick, Robert (1983), "Graph algorithms", Algorithms, Addison–Wesley, ISBN 0-201-06672-6
  6. ↑ Silberschatz, Abraham; Peter Galvin; Greg Gagne (2003). Operating System Concepts. John Wiley & Sons, INC. pp. 260. ISBN 0-471-25060-0.
  7. ↑ GeeksforGeeks: Shortest cycle in an undirected unweighted graph Archived 2022-01-11 at the Wayback Machine
  8. ↑ Veblen, Oswald (1912), "An Application of Modular Equations in Analysis Situs", Annals of Mathematics, Second Series, 14 (1): 86–94, doi:10.2307/1967604, JSTOR 1967604.
  9. ↑ Richard M. Karp (1972), "Reducibility Among Combinatorial Problems" (PDF), in R. E. Miller and J. W. Thatcher (ed.), Complexity of Computer Computations, New York: Plenum, pp. 85–103, archived (PDF) from the original on 2021-02-10, retrieved 2014-03-12.
  10. ↑ Ore, Ø. (1960), "Note on Hamilton circuits", American Mathematical Monthly, 67 (1): 55, doi:10.2307/2308928, JSTOR 2308928.
  11. ↑ Jaeger, F. (1985), "A survey of the cycle double cover conjecture", Annals of Discrete Mathematics 27 – Cycles in Graphs, North-Holland Mathematics Studies, vol. 27, pp. 1–12, doi:10.1016/S0304-0208(08)72993-1.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=चक्र_(ग्राफ़_सिद्धांत)&oldid=236517’