ग्राफ में अधिकतम संभव किनारों

Question

एक ग्राफ में 20 कोने हैं। यदि दो कोने समान डिग्री के हैं, तो वे एक किनारे से जुड़े नहीं हैं। ऐसे ग्राफ में किनारों की अधिकतम संभव संख्या ज्ञात करें

मैंने इसे आरेख के माध्यम से बनाने की कोशिश की, लेकिन 19 डिग्री के 1 शीर्ष और अन्य डिग्री के बाकी हिस्सों को प्राप्त कर रहा हूं, लेकिन आगे बढ़ने में सक्षम नहीं हूं। मेरा दृष्टिकोण उपरोक्त स्थिति को पूरा करने वाली डिग्री के साथ कोने की संख्या का पता लगाना है और फिर हैंडशेकिंग लेम्मा का उपयोग करना है लेकिन आगे बढ़ने में असमर्थ हूं।

क्या आप कृपया उसी पर कुछ संकेत सुझा सकते हैं?

Answer 1

मुझे यकीन नहीं है कि यह सच है, लेकिन हम मान लेते हैं कि एक इष्टतम समाधान में, प्रत्येक शीर्ष एक अलग डिग्री के हर दूसरे शीर्ष के निकट है। तो इष्टतम समाधान एक पूर्ण हो सकता है$k$-एक समान आकार के दो विभाजन वर्गों के साथ-साथ ग्राफ ।

मैंने पुनरावृत्ति-मुक्त विभाजन को खोजने के लिए एक कंप्यूटर खोज की $20=n_1+\cdots +n_k$ वह अधिकतम हो जाता है

$$|E|=\sum_{i<j} n_i n_j,$$

चूंकि यह परिणामी रेखांकन के किनारों की संख्या है।

परिणाम है $K_{2,3,4,5,6}$ 155 किनारों के साथ इष्टतम है।

---

बस अगर आप आश्चर्यचकित होते हैं, तो मैंने निम्नलिखित (काफी अपठनीय) मैथेमेटिका कोड का उपयोग किया

MaximalBy[
    { #, Plus @@ Times @@@ Subsets[#,{2}] } & /@ 
        Select[IntegerPartitions[20],DuplicateFreeQ],
    Last
]

आउटपुट के साथ {{{6,5,4,3,2},155}}।

Answer 2

परिणाम यह निकला $155$अधिकतम नहीं है। पूर्णांक रैखिक प्रोग्रामिंग के माध्यम से, मैंने पाया कि अधिकतम इसके बजाय है$156$, डिग्री अनुक्रम के साथ रेखांकन द्वारा प्राप्त की $$(19,18,18,17,17,17,16,16,16,16,15,15,15,15,14,14,14,14,14,12),$$ $$(19,18,18,17,17,17,16,16,16,15,15,15,15,15,14,14,14,14,14,13),$$ तथा $$(19,18,18,17,17,17,16,16,16,16,15,15,15,15,14,14,14,14,13,13),$$ और शायद अन्य।