Ogni digrafo primitivo ha un ciclo diretto?
Aug 18 2020
Un digrafo è un grafo diretto.
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 che sia primitivo se esiste un numero intero positivo$k$ tale che $A^k >0$ (tutte le voci di $A^k$ sono positivi).
Risposte
3 Sudix Aug 18 2020 at 09:06
Puoi interpretare $(A^n)_{i,j}$ come il numero di percorsi con lunghezza $n$ dal vertice $i$ al vertice $j$.
Dal momento che abbiamo $A^k>0$, abbiamo anche, per $n\in\mathbb N$, quello $A^{nk}>0$.
Pertanto, possiamo trovare percorsi di lunghezza arbitraria nel grafico, quindi deve contenere un ciclo.