क्या प्रत्येक आदिम डिग्राफ का एक निर्देशित चक्र है?
एक संयुक्ताक्षर एक निर्देशित ग्राफ है।
एक निर्देशित चक्र या सरल निर्देशित सर्किट एक निर्देशित सर्किट है जिसमें केवल दोहराए गए कोने पहले और अंतिम कोने हैं।
एक खुदाई प्राइमरी है अगर इसकी आसन्न मैट्रिक्स आदिम है।
एक वर्ग गैर-नकारात्मक मैट्रिक्स $A$कहा जाता है कि अगर कोई सकारात्मक पूर्णांक मौजूद है तो उसे आदिम कहा जाता है$k$ ऐसा है कि $A^k >0$ (सभी प्रविष्टियों की $A^k$ सकारात्मक हैं)।
मुझे संरचना के साथ एक पथ के अस्तित्व की आवश्यकता है $i_0 i_1...i_k i_0$ (भेद किनारों का क्रम) के साथ $k\geq 1$।
जवाब
हाँ। सभी के लिए$i,j$, $(A^k)_{ij}>0$, इसलिए लंबाई का कम से कम एक चलना है $k$ से $v_1$ सेवा मेरे $v_2$ और लंबाई का कम से कम एक चलना है $k$ से $v_2$ सेवा मेरे $v_1$। यह बंद निर्देशित चलना है, जो से जाता है$v_1$ सेवा मेरे $v_2$ और फिर वापस $v_1$ एक गैर-तुच्छ निर्देशित चक्र (यानी कम से कम 2 की लंबाई का चक्र) होना चाहिए।