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.