क्या प्रत्येक आदिम डिग्राफ का एक निर्देशित चक्र है?
Aug 18 2020
एक संयुक्ताक्षर एक निर्देशित ग्राफ है।
एक निर्देशित चक्र या सरल निर्देशित सर्किट एक निर्देशित सर्किट है जिसमें केवल दोहराए गए कोने पहले और अंतिम कोने होते हैं।
यदि कोई समीपता मैट्रिक्स आदिम है तो एक डिग्राफ आदिम है।
एक वर्ग गैर-नकारात्मक मैट्रिक्स $A$कहा जाता है कि अगर कोई सकारात्मक पूर्णांक मौजूद है तो उसे आदिम कहा जाता है$k$ ऐसा है कि $A^k >0$ (सभी प्रविष्टियों की $A^k$ सकारात्मक हैं)।
जवाब
3 Sudix Aug 18 2020 at 09:06
आप व्याख्या कर सकते हैं $(A^n)_{i,j}$ लंबाई के साथ पथ की संख्या के रूप में $n$ शीर्ष से $i$ शीर्ष करने के लिए $j$।
चूंकि हमारे पास है $A^k>0$, हम भी, के लिए है $n\in\mathbb N$, उस $A^{nk}>0$।
इसलिए, हम ग्राफ़ में मनमानी लंबाई के पथ पा सकते हैं, इसलिए इसमें एक चक्र होना चाहिए।