क्या ग्राफ़ में अनावश्यक किनारों को खोजने के लिए कोई स्थापित एल्गोरिदम है?ग्राफ या पेड़ में अनावश्यक किनारों को ढूंढने के लिए एल्गोरिदम
उदाहरण के लिए, मैं खोजने के लिए कि a-> घ और a-> ई अनावश्यक हैं चाहते हैं, और उसके बाद इस तरह उनमें से छुटकारा पाने,:
=>
संपादित करें: स्ट्रिलैंक मेरे लिए मेरे दिमाग को पढ़ने के लिए काफी अच्छा था। उपरोक्त उदाहरण में, "अनावश्यक" एक शब्द का बहुत मजबूत था, न तो ए-> बी या ए-> सी को अनावश्यक माना जाता है, लेकिन एक-> डी है।
आप सबसे छोटे ग्राफ की गणना करना चाहते हैं जो वर्टेक्स पहुंच क्षमता को बनाए रखता है।
इसे ग्राफ़ के transitive reduction कहा जाता है। विकिपीडिया लेख आपको सही सड़क से शुरू करना चाहिए।
धन्यवाद, यह वही है जो मैं ढूंढ रहा हूं। विकिपीडिया लेख में ग्राफविज़ के लिए 'tred' का भी उल्लेख है, जो विशेष रूप से आसान है, क्योंकि यही वह है जिसके साथ मैं काम कर रहा हूं। –
वहां है। मैं देख सकता था कि संक्रमणीय बंद होना बंद था। –
किसी दिए गए ग्राफ का एक उप-ग्राफ जिसमें "अनावश्यक किनारों" शामिल नहीं है उसे उस ग्राफ के 'spanning tree' कहा जाता है। किसी दिए गए ग्राफ के लिए, कई फैलाने वाले पेड़ संभव हैं।
तो, अनावश्यक किनारों से छुटकारा पाने के लिए, आपको बस अपने ग्राफ के किसी भी एक पेड़ के पेड़ को ढूंढना है। आप किसी भी depth-first-search या breadth-first-search एल्गोरिदम का उपयोग कर सकते हैं और ग्राफ में प्रत्येक चरम पर जाने तक खोज जारी रख सकते हैं।
देर हो चुकी है, लेकिन क्या वह वास्तव में एक स्पैनिंग पेड़ का वर्णन करता है? –
हां। वह एक उप-ग्राफ रखना चाहता है जिसमें मूल ग्राफ के सभी शीर्षकों को एक कशेरुक से दूसरे तक पहुंचने के लिए केवल एक ही रास्ता है। यह वही है जो एक स्पैनिंग पेड़ है। –
नहीं, यहां तक कि कम ग्राफ में भी डी से जाने के 2 तरीके हैं। – xuanji
चेक करें: Minimum Spanning Tree
यदि उसे आवश्यक सभी अनावश्यक किनारों से छुटकारा मिलता है, तो उसे _minimum_ स्पैनिंग पेड़ के बारे में चिंता करने की ज़रूरत नहीं है। कोई भी ओले स्पैनिंग पेड़ करेगा। –
यह भी याद रखें "एक कनेक्टेड, अप्रत्यक्ष ग्राफ को देखते हुए, उस ग्राफ का एक स्पैनिंग पेड़ एक सबग्राफ है जो एक पेड़ है और सभी कोष्ठकों को एक साथ जोड़ता है।" फिर भी उसका ग्राफ अप्रत्यक्ष नहीं है। –
कई मायनों इस पर हमला करने की है, लेकिन पहले आप एक छोटे से अधिक सटीक समस्या परिभाषित करने की जरूरत जा रहे हैं। सबसे पहले, आपके पास यहां ग्राफ है जो विश्वकोश है और निर्देशित है: क्या यह हमेशा सत्य होगा?
अगला, आपको "अनावश्यक किनारे" से क्या मतलब है, इसे परिभाषित करने की आवश्यकता है। इस मामले में, आप एक ग्राफ से शुरू करते हैं जिसमें दो पथ होते हैं-> सी: बी के माध्यम से एक और एक सीधा। इससे मैं अनुमान लगाता हूं कि "अनावश्यक" से आपका मतलब कुछ ऐसा है। जी = < वी, ई> एक ग्राफ होना, वीकोने और ई ⊆ वी × वी किनारों के सेट के सेट के साथ करते हैं। यह थोड़े लगता है कि आप मैंवी जे के रूप में "अनावश्यक" सबसे लंबा किनारा से कम करने के लिए वी से सभी किनारों को परिभाषित कर रहे हैं। तो सबसे आसान बात गहराई से पहली खोज का उपयोग करना, पथों की गणना करना, और जब आपको एक नया समय मिल जाए, तो इसे सर्वश्रेष्ठ उम्मीदवार के रूप में सहेजें।
मैं कल्पना नहीं कर सकता कि आप इसके लिए क्या चाहते हैं, हालांकि। क्या तुम बता सकते हो?
मैं सबसे आसान तरीका है कि ऐसा करने के लिए लगता है, वास्तव में यह असली काम में इस तरह दिखाई देंगे कल्पना, कल्पना करें कि आप जोड़ों है, जैसा
(A-> बी) (बी> सी) (ए > सी), कल्पना करता है, तो पास रेखांकन के बीच की दूरी है के बराबर होती है 1, इसलिए
(A-> बी) = 1, (बी> सी) = 1, (A-> सी) = 2.
तो आप संयुक्त (ए-> सी) को हटा सकते हैं।
दूसरे शब्दों में, कम करें।
यह सिर्फ मेरा विचार है कि मैं इसके बारे में कैसे सोचूंगा। नेट पर विभिन्न लेख और स्रोत हैं, आप उन्हें देख सकते हैं और गहरे जा सकते हैं।
संसाधन, कि आप मेरी मदद करेंगे:
Algorithm for Removing Redundant Edges in the Dual Graph of a Non-Binary CSP
Graph Data Structure and Basic Graph Algorithms
Google Books, On finding minimal two connected Subgraphs
Redundant trees for preplanned recovery in arbitraryvertex-redundant or edge-redundant graphs
इस तरह के ग्राफ में कमी को विशेष रूप से सेट-सैद्धांतिक शर्तों में एक संक्रमणकारी कमी कहा जाता है: http://en.wikipedia.org/wiki/Transitive_reduction – Gracenotes
हाँ, लेकिन फिर भी आप इसे हल करने के लिए विभिन्न क्षेत्रों से अल्गोस का उपयोग कर सकते हैं आपकी जरूरतों से समस्या। –
मैं एक ऐसी ही समस्या थी और यह इस तरह से सुलझाने समाप्त हो गया:
मेरे डेटा संरचना है कि (में उस पर निर्भर यानी अपने अनुयायियों नोड्स की एक सूची के लिए एक नोड आईडी से, dependends शब्दकोश से बना है। DAG)। ध्यान दें कि यह केवल एक डीएजी के लिए काम करता है - जिसे निर्देशित किया जाता है, विश्वकोश ग्राफ।
मैंने इसकी सटीक जटिलता की गणना नहीं की है, लेकिन यह एक विभाजित दूसरे में कई हजारों के अपने ग्राफ को निगल लिया है।
_transitive_closure_cache = {}
def transitive_closure(self, node_id):
"""returns a set of all the nodes (ids) reachable from given node(_id)"""
global _transitive_closure_cache
if node_id in _transitive_closure_cache:
return _transitive_closure_cache[node_id]
c = set(d.id for d in dependents[node_id])
for d in dependents[node_id]:
c.update(transitive_closure(d.id)) # for the non-pythonists - update is update self to Union result
_transitive_closure_cache[node_id] = c
return c
def can_reduce(self, source_id, dest_id):
"""returns True if the edge (source_id, dest_id) is redundant (can reach from source_id to dest_id without it)"""
for d in dependents[source_id]:
if d.id == dest_id:
continue
if dest_id in transitive_closure(d.id):
return True # the dest node can be reached in a less direct path, then this link is redundant
return False
# Reduce redundant edges:
for node in nodes:
dependents[node.id] = [d for d in dependents[node.id] if not can_reduce(node.id, d.id)]
सिर्फ पिछले उत्तरों पर टिप्पणी करना चाहता था - अनावश्यक किनारों को कम करना स्पैनिंग ट्री के समान नहीं है, यहां तक कि न्यूनतम स्पैनिंग ट्री के समान नहीं है। और यदि ए से बी का एक पथ ए से बी के दूसरे पथ से अधिक लंबा होता है तो इसका मतलब यह नहीं है कि किन किनारों (यदि कोई है) अनावश्यक हैं। ऊपर दिए गए उनके उदाहरण में आप किनारे के बिना एक स्पैनिंग पेड़ बना सकते हैं-> बी लेकिन यह अनावश्यक नहीं है। – Iftah
क्या हम इसके बजाय बी ---> सी को अनावश्यक मान सकते हैं? –
क्या अनावश्यक मतलब है "एक्स से वाई तक गैर किनारे पथ होने पर एक किनारे एक्स-> वाई अनावश्यक है" या आप बस एक स्पैनिंग पेड़ की तलाश में हैं? –
@Zach: नहीं, बी-> सी अनावश्यक नहीं है, क्योंकि अगर इसे हटा दिया जाता है तो बी से सी – ShreevatsaR