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

From Vigyanwiki
Revision as of 15:19, 16 July 2023 by alpha>Neetua08
एक पथ (ग्राफ़ सिद्धांत) को चित्रित करने के लिए किनारों को रंगीन करने वाला एक ग्राफ #वॉक, ट्रेल, और पथ 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’