Hat jeder primitive Digraph einen gerichteten Kreis?
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$heißt primitiv , wenn es eine positive ganze Zahl gibt$k$so dass$A^k >0$(alle Einträge von$A^k$sind positiv).
Ich brauche nur die Existenz eines Pfades mit der Struktur$i_0 i_1...i_k i_0$(Folge unterschiedlicher Kanten) mit$k\geq 1$.
Antworten
Ja. Für alle$i,j$,$(A^k)_{ij}>0$, also gibt es mindestens eine Gehlänge$k$aus$v_1$zu$v_2$und es gibt mindestens einen langen Weg$k$aus$v_2$zu$v_1$. Dieser geschlossene gerichtete Spaziergang, der von geht$v_1$zu$v_2$und dann zurück zu$v_1$muss einen nicht-trivialen gerichteten Zyklus enthalten (dh einen Zyklus der Länge mindestens 2).