ग्राफ के अंदर एक त्रिकोण कैसे खोजें?

Question

यहां Algorithm Design Manual में एक अभ्यास है।

यह निर्धारित किया जाता अनिर्दिष्ट ग्राफ जी = (वी, ई) एक त्रिकोण या लंबाई के चक्र होता है कि क्या करने की समस्या पर विचार करें 3.

(क) एक हे दें (| वी |^3) यदि कोई अस्तित्व में है तो त्रिकोण ढूंढने के लिए।

(बी) समय में चलाने के लिए अपने एल्गोरिदम को सुधारें ओ (| वी | · | ई |)। आप मान सकते हैं | वी | ≤ | ई |

का निरीक्षण करें कि इन सीमाओं को आप समय जी

यहाँ की निकटता मैट्रिक्स और निकटता सूची अभ्यावेदन के बीच परिवर्तित करने के लिए देता है मेरे विचार है:

(क) ग्राफ एक के रूप में दिया जाता है आसन्नता सूची, मैं ओ (| वी |^2) द्वारा सूची को मैट्रिक्स में परिवर्तित कर सकता हूं। तो मैं करता हूं:

for (int i = 0;i < n;i++) 
    for (int j = i+1;j < n;j++) 
    if (matrix[i][j] == 1) 
     for (int k = j+1;k < n;k++) 
     if (matrix[i][k] == 1 && matrix[j][k] == 1) 
      return true; 

यह त्रिभुज का परीक्षण करने के लिए ओ (| वी |^3) देना चाहिए।

(बी) मेरा पहला अंतर्ज्ञानी यह है कि यदि ग्राफ को आसन्नता सूची के रूप में दिया जाता है, तो मैं एक बीएफएस करूंगा। जब भी एक क्रॉस एज पाया जाता है, उदाहरण के लिए, if y-x is a cross edge, तो मैं check whether parent[y] == parent[x], if true, then a triangle is found होगा।

क्या कोई मुझे बता सकता है कि मेरी सोच सही है या नहीं?

इसके लिए भी (बी), मुझे इसकी जटिलता सुनिश्चित नहीं है। क्या यह ओ (| वी | + | ई |) होना चाहिए, है ना?

मैं इसे ओ (| वी | * | ई |) में कैसे कर सकता हूं?

Answer 1

एक संभावित O(|V||E|) समाधान, में (क) जानवर बल का एक ही विचार है:

for each edge (u, v): 
    for each vertex w: 
    if (v, w) is an edge and (w, u) is an edge: 
      return true 
return false 

जांच सभी किनारों, और नहीं सभी कोने जोड़े - एक और शिखर है कि एक रूपों के साथ त्रिकोण - यह निर्धारित करने के लिए पर्याप्त जानकारी है कि किनारे और कशेरुक एक व्यवहार्य समाधान बनाते हैं या नहीं।

काउंटर BFS समाधान के लिए उदाहरण:

 A 
    /| \ 
    /| \ 
    B C D 
    | | | 
    | | | 
    F---G---H 
    |  | 
    --------- 
    (F, H) is also an edge 

ध्यान दें कि father[F] != father[G] != father[H], इस प्रकार एल्गोरिथ्म अवास्तविक लौटाते हैं - लेकिन फिर भी, (एफ, जी, एच) एक संभव समाधान है! जैसा कि ऊपर बताया

origianl BFS समाधान गलत है:

Answer 2

यहाँ मैं क्या सोचता है। लेकिन हम डीएफएस को संशोधित कर सकते हैं। जब हम डीएफएस में प्रत्येक चरम पर जाते हैं तो नोड्स को संख्याएं असाइन करें। अब, अगर हम एक कशेरुक तक पहुंचते हैं (प्रश्न में मैंने क्रॉस किनारों को देखा, तो अप्रत्यक्ष ग्राफ में कोई भी नहीं है), हम इसकी आसन्नता सूची की जांच करते हैं और मान लीजिए कि एक कशेरुका की खोज की गई है (लेकिन संसाधित नहीं हुई है, ऐसा नहीं हो सकता है), फिर हम इसकी संख्या जांचते हैं । यदि अंतर 2 है तो लंबाई 3 का चक्र होता है।

Answer 3

मुझे वास्तव में the matrix multiplication solution discussed in this blog post पसंद है।

दें एक = निकटता मैट्रिक्स

• एक * में समीपवर्ती एक (A2) मैट्रिक्स गुणा 2-लंबाई रास्तों में से नंबर दिए गए हैं
• a2 में समीपवर्ती * एक मैट्रिक्स गुणा के नंबर दिए गए हैं 3-लंबाई रास्तों

समस्या है, आव्यूह गुणन धीमी है, हालांकि ... आप मैट्रिक्स गुणा करने GPGPU उपयोग कर सकते हैं और आधुनिक आर्किटेक्चर है कि एक GPU शामिल पर एक performant समाधान हो सकता है।

Answer 4

यदि आपके पास आसन्नता मैट्रिक्स है, तो आप मैट्रिक्स को स्क्वायर करके त्रिकोण ढूंढ सकते हैं और देख सकते हैं कि मूल मैट्रिक्स और स्क्वायर मैट्रिक्स में एक ही स्थान पर एक गैर-शून्य प्रविष्टि है या नहीं।

एक बेवकूफ मैट्रिक्स गुणा में समय O(n^3) लगता है, लेकिन तेजी से मैट्रिक्स गुणा एल्गोरिदम हैं जो बेहतर करते हैं। सबसे अच्छी तरह से ज्ञात Coppersmith-Winograd एल्गोरिदम है, जो O(n^2.4) समय में चलता है। इसका मतलब है कि एल्गोरिदम कुछ ऐसा होता है:

• O(V^2) का उपयोग आसन्नता मैट्रिक्स में कनवर्ट करने के लिए करें।
• आसन्नता मैट्रिक्स के वर्ग की गणना करने के लिए O(V^2.4) समय का उपयोग करें।
• गैर-शून्य प्रविष्टियों को मेल करने के लिए मैट्रिस को जांचने के लिए O(V^2) समय का उपयोग करें।
• पंक्ति और कॉलम की अनुक्रमणिका जहां आपको गैर-शून्य प्रविष्टियों (अगर कोई है) मिलती है तो आपको दो शामिल नोड्स बताते हैं।
• ज्ञात नोड्स के लिए सामान्य तीसरे नोड को कम करने के लिए O(V) का उपयोग करें।

तो कुल मिलाकर O(V^2.4) समय लगता है; अधिक सटीक यह लेता है हालांकि लंबे मैट्रिक्स गुणा लेता है। O(V min(V^1.4, E)) में सुधार करने के लिए आप इस एल्गोरिदम और यदि-किसी-किनारे-अंत-बिंदु-एक-आम-पड़ोसी एल्गोरिदम that amit explains in their answer के बीच गतिशील रूप से स्विच कर सकते हैं।

यहां एक paper that goes more in-depth into the problem है।

यह कितना निर्भर है कि इस समस्या पर निर्भर-पर-सैद्धांतिक-खोज कैसे है। यदि मैट्रिक्स गुणा के बारे में अनुमान वास्तव में चौकोर होने के लिए सही साबित होते हैं, तो आपको O(V^2) या O(V^2 log(V)) या उस तरह कुछ ऐसा वास्तव में अच्छा समय लगेगा। लेकिन अगर क्वांटम कंप्यूटर काम करते हैं, तो हम even better than that (O(V^1.3) जैसे कुछ करने में सक्षम होंगे)!