अंशों का योग $\sum_{v\in V} id(v)$ और बाहर की डिग्री $\sum_{v\in V} od(v)$ हमेशा बराबर होते हैं?

Dec 02 2020

मैं Ralph P. Grimaldi's Discrete और Combinatorial Mathematics के सेक्शन 11.3 के प्रॉब्लम # 24 पर काम कर रहा हूं, एक अप्लायड इंट्रोडक्शन, पांचवा एडिशन।

सवाल:

लश्कर $G=(V,E)$ एक निर्देशित ग्राफ हो, जहां $|V|=n$ तथा $|E|=e$। के लिए मूल्य क्या हैं$\sum_{v\in V} id(v)$ तथा $\sum_{v\in V} od(v)$?

$id(v)$ तथा $od(v)$ इन-डिग्री और आउट-डिग्री हैं।

में और बाहर की डिग्री सेक्शन 11.3 के अंत में पास होने का उल्लेख किया जाता है, इसलिए इस प्रश्न का उत्तर देने के लिए किसी को अपने आप छोड़ दिया जाता है।

मैंने आवश्यक तथ्यों के बारे में बताने की कोशिश की $\sum_{v\in V} id(v)$ तथा $\sum_{v\in V} od(v)$ और मुझे पता है कि क्या मेरा तर्क सही है,

वर्टिकल संख्या को देखते हुए $n$ आपके द्वारा जोड़े गए प्रत्येक 'निर्देशित' किनारे के लिए आप जोड़ रहे हैं $1$ सेवा मेरे $\sum_{v\in V} id(v)$ तथा $\sum_{v\in V} od(v)$ क्रमशः, और उन्हें हमेशा बराबर होना चाहिए?

यदि हां, तो $\sum_{v\in V} id(v)=\sum_{v\in V} od(v)=e?$

जवाब

1 user21820 Dec 06 2020 at 20:43

अपने विचार को कठोर बनाने के लिए, आपको प्रेरण का उपयोग करने की आवश्यकता है। लश्कर$Q(k)$ कथन है कि हर निर्देशित ग्राफ बिल्कुल $k$किनारों वांछित दावे को संतुष्ट करता है। फिर इंडक्शन ऑन का इस्तेमाल करें$Q$। ऐसा करते समय, सावधान रहें कि आप ऐसा कुछ भी नहीं करते हैं "अगर$Q(k)$ सच है, तो चलो $G$ किसी भी निर्देशित ग्राफ के साथ हो $k$किनारों और एक बढ़त जोड़ें ... "! यह सुनिश्चित करने के लिए कि आप सही ढंग से प्रेरण करते हैं, प्रेरण की इस व्याख्या को पढ़ें ।