चक्र (ग्राफ़ सिद्धांत)
ग्राफ़ सिद्धांत में, ग्राफ़ (असतत गणित) में एक चक्र एक गैर-रिक्त पथ (ग्राफ सिद्धांत) #वॉक, ट्रेल और पथ है जिसमें केवल पहला और अंतिम वर्टेक्स (ग्राफ़ सिद्धांत) बराबर होते हैं। निर्देशित ग्राफ में एक निर्देशित चक्र एक गैर-रिक्त पथ है (ग्राफ सिद्धांत)#निर्देशित चलना, निर्देशित पथ और निर्देशित पथ जिसमें केवल पहला और अंतिम शीर्ष बराबर होते हैं।
बिना चक्र वाले ग्राफ को एसाइक्लिक ग्राफ कहा जाता है। निर्देशित चक्रों के बिना एक निर्देशित ग्राफ को निर्देशित अचक्रीय ग्राफ कहा जाता है। चक्रों के बिना जुड़े हुए ग्राफ़ को ट्री (ग्राफ़ सिद्धांत) कहा जाता है।
परिभाषाएँ
सर्किट और चक्र
- एक सर्किट एक गैर-रिक्त पथ है (ग्राफ़ सिद्धांत)#वॉक, ट्रेल और पथ जिसमें पहला और अंतिम शीर्ष बराबर होते हैं (बंद ट्रेल)।[1]
- होने देना G = (V, E, ϕ) एक ग्राफ बनें. सर्किट एक गैर-रिक्त पथ है (e1, e2, …, en) शीर्ष क्रम के साथ (v1, v2, …, vn, v1).
- चक्र या सरल परिपथ एक ऐसा परिपथ है जिसमें केवल प्रथम और अंतिम शीर्ष बराबर होते हैं।[1]
निर्देशित सर्किट और निर्देशित चक्र
- एक निर्देशित सर्किट एक गैर-रिक्त पथ है (ग्राफ़ सिद्धांत)#निर्देशित चलना, निर्देशित पथ, और निर्देशित पथ जिसमें पहला और अंतिम शीर्ष बराबर होते हैं (बंद निर्देशित पथ)।[1]
- होने देना G = (V, E, ϕ) एक निर्देशित ग्राफ बनें। एक निर्देशित सर्किट एक गैर-रिक्त निर्देशित पथ है (e1, e2, …, en) शीर्ष क्रम के साथ (v1, v2, …, vn, v1).
- एक निर्देशित चक्र या सरल निर्देशित सर्किट एक निर्देशित सर्किट होता है जिसमें केवल पहला और अंतिम शीर्ष बराबर होता है।[1]
तार रहित चक्र
ग्राफ़ में एक ताररहित चक्र, जिसे छेद या प्रेरित चक्र भी कहा जाता है, एक ऐसा चक्र है जिसमें चक्र के कोई भी दो शीर्ष किसी ऐसे किनारे से नहीं जुड़े होते हैं जो स्वयं चक्र से संबंधित नहीं होता है। एक एंटीहोल एक ग्राफ़ होल का पूरक ग्राफ़ है। कॉर्डलेस चक्रों का उपयोग सही ग्राफ़ को चिह्नित करने के लिए किया जा सकता है: मजबूत उत्तम ग्राफ ़ प्रमेय के अनुसार, एक ग्राफ़ तभी सही होता है जब उसके किसी भी छेद या एंटीहोल में विषम संख्या में कोने न हों जो तीन से अधिक हो। कॉर्डल ग्राफ़, एक विशेष प्रकार का पूर्ण ग्राफ़, जिसमें तीन से अधिक आकार का कोई छेद नहीं होता है।
किसी ग्राफ का घेरा (ग्राफ़ सिद्धांत) उसके सबसे छोटे चक्र की लंबाई है; यह चक्र आवश्यक रूप से तार रहित है। केज (ग्राफ़ सिद्धांत) को डिग्री और परिधि के दिए गए संयोजनों के साथ सबसे छोटे नियमित ग्राफ़ के रूप में परिभाषित किया गया है।
एक परिधीय चक्र एक ग्राफ़ में एक चक्र है जिसमें यह गुण होता है कि चक्र पर नहीं होने वाले प्रत्येक दो किनारों को एक पथ से जोड़ा जा सकता है जिसके आंतरिक कोने चक्र से बचते हैं। ऐसे ग्राफ़ में जो किसी चक्र में एक किनारे जोड़कर नहीं बनता है, एक परिधीय चक्र एक प्रेरित चक्र होना चाहिए।
साइकिल स्पेस
चक्र शब्द ग्राफ़ के चक्र स्थान के एक तत्व को भी संदर्भित कर सकता है। कई चक्र स्थान हैं, प्रत्येक गुणांक क्षेत्र या रिंग के लिए एक। सबसे आम है बाइनरी साइकल स्पेस (आमतौर पर इसे केवल साइकल स्पेस कहा जाता है), जिसमें किनारे के सेट होते हैं जिनकी प्रत्येक शीर्ष पर डिग्री भी होती है; यह दो-तत्व परिमित क्षेत्र पर एक सदिश स्थल बनाता है। वेब्लेन के प्रमेय के अनुसार, चक्र स्थान का प्रत्येक तत्व सरल चक्रों के किनारे-असंबद्ध संघ के रूप में बन सकता है। ग्राफ़ का चक्र आधार सरल चक्रों का एक सेट है जो चक्र स्थान का आधार (रैखिक बीजगणित) बनाता है।[2] बीजगणितीय टोपोलॉजी के विचारों का उपयोग करते हुए, बाइनरी चक्र स्थान को अन्य रिंग (गणित) जैसे पूर्णांक, तर्कसंगत या वास्तविक संख्याओं आदि पर वेक्टर रिक्त स्थान या मॉड्यूल (गणित) में सामान्यीकृत किया जाता है।[3]
चक्र का पता लगाना
निर्देशित और अप्रत्यक्ष ग्राफ़ में एक चक्र का अस्तित्व इस बात से निर्धारित किया जा सकता है कि क्या गहराई-पहली खोज (डीएफएस) को एक किनारा मिलता है जो वर्तमान शीर्ष के पूर्वज को इंगित करता है (इसमें गहराई-पहली खोज#गहराई-पहली खोज का आउटपुट शामिल है) ).[4] सभी पिछले किनारे जिन पर डीएफएस छूट जाता है वे चक्रों का हिस्सा हैं।[5] एक अप्रत्यक्ष ग्राफ़ में, किसी नोड के पैरेंट के किनारे को पिछले किनारे के रूप में नहीं गिना जाना चाहिए, लेकिन पहले से देखे गए किसी अन्य शीर्ष को ढूंढना पिछले किनारे का संकेत देगा। अप्रत्यक्ष ग्राफ़ के मामले में, एन-वर्टेक्स ग्राफ़ में एक चक्र खोजने के लिए केवल O(n) समय की आवश्यकता होती है, क्योंकि अधिकतम n − 1 किनारे पेड़ के किनारे हो सकते हैं।
कई टोपोलॉजिकल छँटाई एल्गोरिदम भी चक्रों का पता लगाएंगे, क्योंकि वे टोपोलॉजिकल ऑर्डर के अस्तित्व में बाधाएं हैं। इसके अलावा, यदि एक निर्देशित ग्राफ को दृढ़ता से जुड़े घटकों में विभाजित किया गया है, तो चक्र केवल घटकों के भीतर मौजूद होते हैं, उनके बीच नहीं, क्योंकि चक्र दृढ़ता से जुड़े होते हैं।[5]
निर्देशित ग्राफ़ के लिए, वितरित संदेश-आधारित एल्गोरिदम का उपयोग किया जा सकता है। ये एल्गोरिदम इस विचार पर भरोसा करते हैं कि एक चक्र में एक शीर्ष द्वारा भेजा गया संदेश स्वयं वापस आ जाएगा। वितरित चक्र पहचान एल्गोरिदम कंप्यूटर क्लस्टर (या सुपर कंप्यूटर) पर वितरित ग्राफ प्रसंस्करण प्रणाली का उपयोग करके बड़े पैमाने पर ग्राफ़ को संसाधित करने के लिए उपयोगी होते हैं।
चक्र पहचान के अनुप्रयोगों में समवर्ती प्रणालियों में गतिरोध का पता लगाने के लिए प्रतीक्षा-ग्राफ़ का उपयोग शामिल है।[6]
एल्गोरिथम
प्रत्येक शीर्ष v के लिए: विज़िट(v) = गलत, समाप्त(v) = गलत प्रत्येक शीर्ष v के लिए: डीएफएस(वी)
डीएफएस(वी):
यदि समाप्त हो गया(v)
वापस करना
यदि दौरा किया गया(v)
साइकिल मिल गई और वापस आ गए
विज़िट किया गया (v) = सत्य
प्रत्येक पड़ोसी के लिए w
डीएफएस(डब्ल्यू)
समाप्त (v) = सत्य
नेबर का मतलब निर्देशित और अप्रत्यक्ष ग्राफ़ दोनों के लिए v से जुड़े सभी शीर्ष हैं, सिवाय उस शीर्ष को छोड़कर जिसे DFS(v) कहा जाता है। यह एल्गोरिथम को तुच्छ चक्रों को पकड़ने से भी बचाता है, जो कि कम से कम एक किनारे वाले प्रत्येक अप्रत्यक्ष ग्राफ़ में होता है।
प्रोग्रामिंग
प्रोग्रामिंग भाषा C_Sharp_(प्रोग्रामिंग_भाषा)|C# में निम्नलिखित उदाहरण एडजेंसी सूचियों का उपयोग करके एक अप्रत्यक्ष ग्राफ़ के एक कार्यान्वयन को दर्शाता है। अप्रत्यक्ष ग्राफ़ को Class_(computer_programming) UndirectedGraph के रूप में घोषित किया गया है। प्रोग्राम को निष्पादित करने में मुख्य विधि_(कंप्यूटर_प्रोग्रामिंग) का उपयोग किया जाता है, जो - यदि कोई मौजूद है - कंसोल पर सबसे छोटा, गैर-तुच्छ चक्र प्रिंट करता है।[7]<सिंटैक्सहाइलाइट लैंग = सी# > सिस्टम का उपयोग करना; System.Collections.Generic का उपयोग करना;
// ग्राफ़ के शीर्षों के लिए वर्ग की घोषणा करता है क्लास नोड { सार्वजनिक पूर्णांक सूचकांक; सार्वजनिक स्ट्रिंग मान; सार्वजनिक हैशसेट<नोड> आसन्न नोड्स = नया हैशसेट<नोड>(); // पड़ोसी शीर्षों का सेट }
// अप्रत्यक्ष ग्राफ़ के लिए वर्ग घोषित करता है कक्षा अप्रत्यक्ष ग्राफ़ { सार्वजनिक हैशसेट<नोड> नोड्स = नया हैशसेट<नोड>();
// यह विधि नोड1 और नोड2 को एक दूसरे से जोड़ती है सार्वजनिक शून्य कनेक्टनोड्स (नोड नोड 1, नोड नोड 2) { node1.adjacentNodes.Add(node2); 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); // पुनरावृत्त करने के लिए नए शीर्षों का सेट हैशसेट<सूची<नोड>> पथ = नया हैशसेट<सूची<नोड>>(); // वर्तमान पथों का सेट 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-लूप, सभी पाए गए चक्रों को पुनरावृत्त करता हुआ { कंसोल.राइटलाइन(टूस्ट्रिंग(चक्र)); // कंसोल पर प्रिंट करें } } अन्य { कंसोल.राइटलाइन (ग्राफ़ में कोई चक्र नहीं है। ); // कंसोल पर प्रिंट करें }
कंसोल.रीडलाइन(); } } </सिंटैक्सहाइलाइट>
चक्र द्वारा ग्राफ़ को कवर करना
कोनिग्सबर्ग के सात पुलों पर अपने 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.
