Hat jeder primitive Digraph einen gerichteten Zyklus?
Ein Digraph ist ein gerichteter Graph.
Ein gerichteter Zyklus oder eine einfache gerichtete Schaltung ist eine gerichtete Schaltung, bei der die einzigen wiederholten Scheitelpunkte die ersten und letzten Scheitelpunkte sind.
Ein Digraph ist primitiv, wenn seine Adjazenzmatrix primitiv ist.
Eine quadratische nicht negative Matrix $A$wird als primitiv bezeichnet, wenn eine positive ganze Zahl existiert$k$ so dass $A^k >0$ (alle Einträge von $A^k$ sind positiv).
Antworten
Sie können interpretieren $(A^n)_{i,j}$ als Anzahl der Pfade mit Länge $n$ vom Scheitelpunkt $i$ zum Scheitelpunkt $j$.
Seit wir ... Haben $A^k>0$haben wir auch für $n\in\mathbb N$, Das $A^{nk}>0$.
Daher können wir Pfade beliebiger Länge im Diagramm finden, daher muss es einen Zyklus enthalten.