Ogni digrafo primitivo ha un ciclo orientato?
Un digrafo è un grafo orientato.
Un ciclo diretto o circuito diretto semplice è un circuito diretto in cui gli unici vertici ripetuti sono il primo e l'ultimo vertice.
Un digrafo è primitivo se la sua matrice di adiacenza è primitiva.
Una matrice quadrata non negativa $A$si dice primitivo se esiste un numero intero positivo$k$tale che$A^k >0$(tutte le voci di$A^k$sono positivi).
Ho bisogno solo dell'esistenza di un percorso con la struttura$i_0 i_1...i_k i_0$(sequenza di spigoli distinti) con$k\geq 1$.
Risposte
Sì. Per tutti$i,j$,$(A^k)_{ij}>0$, quindi c'è almeno un cammino di lunghezza$k$da$v_1$a$v_2$e c'è almeno una passeggiata di lunghezza$k$da$v_2$a$v_1$. Questa passeggiata diretta chiusa che va da$v_1$a$v_2$e poi di nuovo a$v_1$deve contenere un ciclo diretto non banale (cioè un ciclo di lunghezza almeno 2).