अधिकतम संख्या खोजें। ग्राफ

Question

में किनारों के किनारे पर एक अप्रत्यक्ष ग्राफ के 'एन' कोने और 0 किनारे हैं। किनारों की अधिकतम संख्या क्या हो सकती है जिसे हम आकर्षित कर सकते हैं कि ग्राफ डिस्कनेक्ट हो गया है।

मैंने समाधान बनाया है कि हम एक वर्टिस को बाहर कर सकते हैं और अप्रत्यक्ष ग्राफ के एन -1 अक्षरों के बीच अधिकतम संख्या में किनारों को पा सकते हैं, ताकि ग्राफ अभी भी डिस्कनेक्ट हो जाए। जो n (n-1)/2 n n vertices के लिए है और n-1 vertices के लिए (n-1) (n-2)/2 होगा (क्या बेहतर समाधान हो सकता है?

Answer 1

आपका समाधान सबसे अच्छा समाधान होना चाहिए।

क्योंकि किसी भी नए किनारे को एक छोर पर एनएचटी वर्टेक्स होना चाहिए।

Answer 2

यदि ग्राफ में बहु किनारे हो सकते हैं, तो उत्तर n> = 3 के लिए अनंत है।
यदि इसमें स्वयं-लूप भी हो सकते हैं, तो उत्तर n> = 2,

के लिए अनन्तता है यदि उनमें से कोई भी आपका समाधान सही नहीं है।

Answer 3

आप विश्लेषण का उपयोग कर इसे हल कर सकते हैं। अपना विचार लो और इसे सामान्यीकृत करें। आप n vertes को दो समूहों में आकार x और n-x विभाजित करते हैं। अब किनारों की संख्या x के एक समारोह, द्वारा

f(x)= x(x-1)/2 + (n-x)(n-x-1)/2 
    f(x) = 1/2(2x^2 - 2nx +n^2 - n) 

मूल्य जो अधिकतम इस समारोह विभाजन आकार आप चाहते है व्यक्त किया जाता है। यदि आप गणना करते हैं तो आपको लगता है कि यह x=0 से x=n/2 तक घटता है, फिर x=n तक बढ़ता है। चूंकि x = 0 या x = n का अर्थ है कि ग्राफ़ एकत्र किया जाता है, तो आप अगले सबसे बड़े मान को लेते हैं जो x=1 है। तो आपका अंतर्ज्ञान इष्टतम है।