मेरे पास एक ग्राफ है जो एकल, रूट नोड के साथ शुरू होता है। नोड्स को ग्राफ में एक करके जोड़ा जाता है। नोड निर्माण समय पर, उन्हें एक ही किनारे से रूट नोड, या किसी अन्य नोड से जोड़ा जाना चाहिए। किनारों को भी बनाया और हटाया जा सकता है (एक-एक करके, किसी भी दो नोड्स के बीच)। एक समय में नोड्स को हटाया जा सकता है। नोड और एज निर्माण, किसी भी मनमाने ढंग से क्रम में हटाना संचालन हो सकता है।कैसे पता लगाया जाए कि किनारे को तोड़ने से ग्राफ़ डिसजॉइंट हो जाएगा?
ठीक है, तो यहां मेरा प्रश्न है: जब कोई किनारा हटा दिया जाता है, तो क्या यह संभव है, निरंतर समय (यानी ओ (1) एल्गोरिदम के साथ) निर्धारित करना संभव है, यदि ऐसा करने से ग्राफ को दो अपमानित उपग्राफों में विभाजित किया जाएगा? यदि यह होगा, तो किनारे के किनारे रूट नोड संबंधित होंगे?
मैं उचित सीमाओं के भीतर, किसी भी अतिरिक्त डेटा संरचना को बनाए रखने के लिए तैयार हूं जो इस जानकारी के व्युत्पन्न को सुविधाजनक बना सकता है।
शायद ओ (1) में ऐसा करना संभव नहीं है, यदि साहित्य के किसी भी संकेतक की सराहना की जाएगी।
संपादित करें: आलेख एक निर्देशित ग्राफ है।
संपादित करें 2:
ठीक है, शायद मैं रूट नोड
से किनारों को हटाने के लिए केस को प्रतिबंधित कर सकता हूं। [संपादित करें 3: नहीं, असल में] इसके अलावा, रूट नोड में कोई किनारा नहीं है।
, एक पत्ता नोड के लिए ग्राफ जोड़ने बढ़त हटाया जाने वाला है, तो वह पत्ती नोड को हटाने के लिए मान लिया है? वैकल्पिक रूप से, क्या एक पत्ता नोड को हटाने से ग्राफ़ को शेष ग्राफ से कनेक्ट किया जा सकता है? – VeeArr
@VeeArr: एक पत्ता नोड को हटाने से सभी किनारों को भी लिंक किया जाता है। एक किनारे को हटाने के लिए जो एक पत्ता-नोड और एक गैर-पत्ता नोड को जोड़ता है, जिसे स्वयं प्रश्न से ढंकना चाहिए (एक मनमाना किनारा हटाना)। –
तुम मुझे क्यों नहीं बताते हो ?! आप ** the_graph_guy ** !! –