1. घर
  2. सवाल और जवाब
  3. डीएजी में कितने किनारे हो सकते हैं?

डीएजी में कितने किनारे हो सकते हैं?

2012-07-28 18 views
5

एन वर्टिसेस के साथ एक निर्देशित विश्वकोश ग्राफ में, इसमें निर्देशित किनारों की अधिकतम संभव संख्या क्या है?डीएजी में कितने किनारे हो सकते हैं?

स्रोत

2012-07-28 user1559262

+1

यह सवाल स्टैक ओवरफ़्लो के लिए विषय बंद है । आप http://math.stackexchange.com/ आज़मा सकते हैं जो सभी स्तरों पर गणित प्रश्नों का स्वागत करता है। –

+2

उल्लेख नहीं है, यह होमवर्क समस्या की तरह लगता है। और मैंने चारा लिया: -/ –

+0

इसके अलावा, यह एक डुप्लिकेट है [मैं अधिकतम किनारों को कैसे साबित कर सकता हूं?] (Http://math.stackexchange.com/questions/61579/how-can-i-prove- अधिकतम-संख्या-किनारों के किनारे) –

उत्तर

13

एन वर्टिस/नोड्स मानें, और चलिए अधिकतम किनारों के साथ एक डीएजी बनाने का पता लगाएं। किसी दिए गए नोड पर विचार करें, एन 1 कहें। इस शुरुआती चरण में अधिकतम # नोड्स इंगित कर सकते हैं, या किनारों पर एन -1 है। आइए दूसरा नोड एन 2 चुनें: यह स्वयं को छोड़कर सभी नोड्स को इंगित कर सकता है और एन 1 - यह एन -2 अतिरिक्त किनारों है। शेष नोड्स के लिए जारी रखें, प्रत्येक नोड से पहले एक कम किनारे पर इंगित कर सकते हैं। अंतिम नोड 0 अन्य नोड्स को इंगित कर सकता है।

सभी किनारों का योग: (एन -1) + (एन 2) + .. + 1 + 0 == (एन -1) (एन)/2

स्रोत

2012-07-28 07:19:51

+0

आपके उत्तर के लिए बहुत बहुत धन्यवाद। – user1559262

+0

हम्म, [यह] (http://stackoverflow.com/questions/5058406/what-is-the- अधिकतम- संख्या-of-edges-in-a-directed-graph-with-n-nodes) बहस प्रतीत होता है जवाब के साथ। –

+5

@RealzSlaw भेद यह है कि एक डीएजी "विश्वकोश" है; जिस पोस्ट का आप संदर्भित करते हैं, वह सामान्य रूप से निर्देशित ग्राफ पर चर्चा करता है। –

संबंधित मुद्दे

 संबंधित मुद्दे