चक्र (ग्राफ़ सिद्धांत)
ग्राफ़ सिद्धांत में, ग्राफ़ (असतत गणित) में एक चक्र एक गैर-रिक्त पथ (ग्राफ सिद्धांत) या वॉक, ट्रेल और पथ है जिसमें केवल प्रथम और अंतिम वर्टेक्स (ग्राफ़ सिद्धांत) समान होते हैं। निर्देशित ग्राफ में एक निर्देशित चक्र एक गैर-रिक्त पथ है (ग्राफ सिद्धांत) या निर्देशित चलना, निर्देशित पथ और निर्देशित पथ जिसमें केवल प्रथम और अंतिम शीर्ष समान होते हैं।
इस प्रकार से बिना चक्र वाले ग्राफ को एसाइक्लिक ग्राफ कहा जाता है। निर्देशित चक्रों के बिना एक निर्देशित ग्राफ को निर्देशित अचक्रीय ग्राफ कहा जाता है। और चक्रों के बिना जुड़े हुए ग्राफ़ को ट्री (ग्राफ़ सिद्धांत) कहा जाता है।
परिलैंग्वेज एँ
परिपथ और चक्र
- एक परिपथ एक गैर-रिक्त पथ है (ग्राफ़ सिद्धांत) या वॉक, ट्रेल और पथ जिसमें प्प्रथम और अंतिम शीर्ष समान (बंद ट्रेल) होते हैं ।[1]
- मान लीजिए G = (V, E, ϕ) एक ग्राफ है। और परिपथ एक शीर्ष अनुक्रम (v1, v2, …, vn, v1) के साथ एक गैर-रिक्त पथ (e1, e2, …, en) है।
- चक्र या सरल परिपथ एक ऐसा परिपथ है जिसमें केवल प्रथम और अंतिम शीर्ष समान होते हैं।[1]
निर्देशित परिपथ और निर्देशित चक्र
- एक निर्देशित परिपथ एक गैर-रिक्त पथ है (ग्राफ़ सिद्धांत) या निर्देशित चलना, निर्देशित पथ, और निर्देशित पथ जिसमें पहला और अंतिम शीर्ष समान होते हैं (बंद निर्देशित पथ)।[1]
मान लीजिए G = (V, E, ϕ) एक निर्देशित ग्राफ है। एक निर्देशित परिपथ एक शीर्ष अनुक्रम (v1, v2, …, vn, v1) के साथ एक गैर-रिक्त निर्देशित पथ (e1, e2, …, en) है।.
- एक निर्देशित चक्र या सरल निर्देशित परिपथ एक निर्देशित परिपथ होता है जिसमें केवल पहला और अंतिम शीर्ष समान होता है।[1]
तार रहित चक्र
ग्राफ़ में एक ताररहित चक्र, जिसे छिद्र या प्रेरित चक्र भी कहा जाता है, यह एक ऐसा चक्र है जिसमें चक्र के कोई भी दो शीर्ष किसी ऐसे किनारे से नहीं जुड़े होते हैं जो की स्वयं चक्र से संबंधित नहीं होता है। किन्तु एंटीहोल एक ग्राफ़ होल का पूरक ग्राफ है। इस प्रकार से कॉर्डलेस चक्रों का उपयोग सही ग्राफ़ को चिह्नित करने के लिए किया जा सकता है: जटिल उत्तम ग्राफ प्रमेय के अनुसार, एक ग्राफ़ तभी सही होता है जब उसके किसी भी छिद्र या एंटीहोल में विषम संख्या में कोने न हों जो तीन से अधिक हो। कॉर्डल ग्राफ, एक विशेष प्रकार का पूर्ण ग्राफ़, जिसमें तीन से अधिक आकार का कोई छिद्र नहीं होता है।
चूंकि किसी ग्राफ का घेरा (ग्राफ़ सिद्धांत) उसके सामान्य लघु चक्र की लंबाई है; यह चक्र आवश्यक रूप से तार रहित होते है। जिससे केज (ग्राफ़ सिद्धांत) को डिग्री और परिधि के दिए गए संयोजनों के साथ अधिक लघु नियमित ग्राफ़ के रूप में परिभाषित किया गया है।
एक परिधीय चक्र एक ग्राफ़ में एक चक्र है जिसमें यह गुण होता है कि चक्र पर नहीं होने वाले प्रत्येक दो किनारों को एक पथ से जोड़ा जा सकता है जिसके आंतरिक कोने चक्र से बचते हैं। ऐसे ग्राफ़ में जो किसी चक्र में एक किनारे जोड़कर नहीं बनता है, एक परिधीय चक्र एक प्रेरित चक्र होना चाहिए।
चक्र स्थान
इस प्रकार से चक्र शब्द ग्राफ़ के चक्र स्थान के एक तत्व को भी संदर्भित कर सकता है। और अनेक चक्र स्थान हैं, प्रत्येक गुणांक क्षेत्र या रिंग के लिए कई चक्र स्थान होते हैं। जो की अधिक महत्वपूर्ण होते है बाइनरी चक्र स्थान (सामान्यतः इसे केवल चक्र स्थान कहा जाता है), जिसमें किनारे के समुच्च होते हैं जिनकी प्रत्येक शीर्ष पर डिग्री भी होती है; यह दो-तत्व परिमित क्षेत्र पर एक सदिश स्थल बनाता है। वेब्लेन के प्रमेय के अनुसार, चक्र स्थान का प्रत्येक तत्व सरल चक्रों के किनारे-असंबद्ध संघ के रूप में बन सकता है। ग्राफ़ का चक्र आधार सरल चक्रों का एक समुच्च है जो की चक्र स्थान का आधार (रैखिक बीजगणित) बनाता है।[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 से जुड़े सभी शीर्ष हैं, सिवाय उस शीर्ष को छोड़कर जिसे डीएफएस(वी) कहा जाता है। यह एल्गोरिथम को सामान्य चक्रों को पकड़ने से भी बचाता है, जो कि लघु से लघु एक किनारे वाले प्रत्येक अप्रत्यक्ष ग्राफ़ में होता है।
प्रोग्रामिंग
प्रोग्रामिंग लैंग्वेज सी_शार्प_(प्रोग्रामिंग_लैंग्वेज ) सी# में निम्नलिखित उदाहरण एडजेंसी सूचियों का उपयोग करके एक अप्रत्यक्ष ग्राफ़ के एक कार्यान्वयन को दर्शाता है। अप्रत्यक्ष ग्राफ़ को क्लास_(कंप्यूटर_प्रोग्रामिंग) अनडायरेक्टेडग्राफ के रूप में घोषित किया गया है। प्रोग्राम को निष्पादित करने में मुख्य विधि_(कंप्यूटर_प्रोग्रामिंग) का उपयोग किया जाता है, जो - यदि कोई उपस्तिथ है - कंसोल पर सबसे छोटा, गैर-सामान्य चक्र प्रिंट करता है।[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)
{
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.0 1.1 1.2 1.3 Bender & Williamson 2010, p. 164.
- ↑ 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.
- ↑ 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.
- ↑ 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.0 5.1 Sedgewick, Robert (1983), "Graph algorithms", Algorithms, Addison–Wesley, ISBN 0-201-06672-6
- ↑ Silberschatz, Abraham; Peter Galvin; Greg Gagne (2003). Operating System Concepts. John Wiley & Sons, INC. pp. 260. ISBN 0-471-25060-0.
- ↑ GeeksforGeeks: Shortest cycle in an undirected unweighted graph Archived 2022-01-11 at the Wayback Machine
- ↑ 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.
- ↑ 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.
- ↑ Ore, Ø. (1960), "Note on Hamilton circuits", American Mathematical Monthly, 67 (1): 55, doi:10.2307/2308928, JSTOR 2308928.
- ↑ 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.
- Balakrishnan, V. K. (2005). Schaum's outline of theory and problems of graph theory ([Nachdr.] ed.). McGraw–Hill. ISBN 978-0070054899.
- Bender, Edward A.; Williamson, S. Gill (2010). Lists, Decisions and Graphs. With an Introduction to Probability.
