Teoria dei grafi: matrice di adiacenza e path (sentieri)
Salve a tutti
Mi sono stati posti diversi quesiti durante le prime settimane del corso, ma ne ho uno al quale proprio non riesco a rispondere. Abbiamo dimostrato che preso un grafo $G$ e la sua matrice di adiacenza $A$ (il cui elemento $a_{i,j}$ vale $1$ se esiste il lato $v_i,v_j$, $0$ altrimenti), nella matrice $A^k$ (elevamento a potenza) l'elemento $a_{i,j}$ indica il numero di walk (cammini, ossia percorsi da un vertice ad un altro durante i quali si possono ripetere spigoli e vertici) da $v_i$ a $v_j$ o viceversa (si parla di grafi semplici non orientati). Ho dimostrato (è piuttosto banale) che se i vertici $v_i,v_j$ sono a distanza $n$ allora l'elemento $a_{i,j}$ della matrice $A^n$ è pari al numero di path (sentieri, ossia percorsi da un vertice ad un altro dove non si ripetono nè spigoli nè vertici) tra i due. E anche che se $d(v_i,v_j)=n$ (la distanza tra i vertici è $n$) l'elemento $a_{i,j}$ di $A^{n+1}$ mi dà comunque il numero di path di lunghezza $n+1$.
Il nodo viene adesso perchè sotto le stesse ipotesi, ossia $d(v_i,v_j)=n$, in grafi senza 4-cicli (perchè?), cosa posso dire sull'elemento $a_{i,j}$ di $A^{n+2}$?
Non so nemmeno da che parte iniziare.
Mi sono stati posti diversi quesiti durante le prime settimane del corso, ma ne ho uno al quale proprio non riesco a rispondere. Abbiamo dimostrato che preso un grafo $G$ e la sua matrice di adiacenza $A$ (il cui elemento $a_{i,j}$ vale $1$ se esiste il lato $v_i,v_j$, $0$ altrimenti), nella matrice $A^k$ (elevamento a potenza) l'elemento $a_{i,j}$ indica il numero di walk (cammini, ossia percorsi da un vertice ad un altro durante i quali si possono ripetere spigoli e vertici) da $v_i$ a $v_j$ o viceversa (si parla di grafi semplici non orientati). Ho dimostrato (è piuttosto banale) che se i vertici $v_i,v_j$ sono a distanza $n$ allora l'elemento $a_{i,j}$ della matrice $A^n$ è pari al numero di path (sentieri, ossia percorsi da un vertice ad un altro dove non si ripetono nè spigoli nè vertici) tra i due. E anche che se $d(v_i,v_j)=n$ (la distanza tra i vertici è $n$) l'elemento $a_{i,j}$ di $A^{n+1}$ mi dà comunque il numero di path di lunghezza $n+1$.
Il nodo viene adesso perchè sotto le stesse ipotesi, ossia $d(v_i,v_j)=n$, in grafi senza 4-cicli (perchè?), cosa posso dire sull'elemento $a_{i,j}$ di $A^{n+2}$?
Non so nemmeno da che parte iniziare.
Risposte
Ok vediamo se butto giù qualcosina. Siano $v_i$ e $v_j$ a distanza $n$ nel grafo $G$.
Partiamo col considerare l'elemento di posto $i,j$ della matrice $A^{n+2}$. Questo conterà i cammini di lunghezza $n+2$ tra questi si troveranno i path (che è quanto voglio trovare) e anche quei cammini che non sono path. Come sono fatti questi due?
I secondi possono originare dai path lunghi $n$ in cui da ogni vertice $v$ passo ad uno adiacente e torno indietro (del tipo $v_i...w-a-w...v_j$). Questi saranno pari al numero di 2-cicli possibili partendo dai vertici visitati dal path meno $n$ poichè i due cicli che passano da un vertice all'altro del path e tornano indietro vengono contati due volte. Siano $p_k$ i path da $v_i$ a $v_j$ lunghi $n$, questi sono in numero pari $a_{ij}^{(n)}$ (dove uso impropriamente la notazione esponenziale per indicare il l'elemento della matrice $A^n$, sarà così anche nel proseguo) e siano $v_{k_i}$ i vertici visitati da $p_k$. Il numero di cammini non path definiti come sopra è pari a
$$M=(\sum_{k}\sum_{i}deg(v_{k_i}))-n\cdot a_{ij}^{(n)}$$
dove $deg(v)$ è il grado del vertice.
Per quanto riguarda i path lunghi $n+2$ potrei avere quelli che "deviano" da un path di lunghezza $n$ in questo modo $v_i- ... v_k-a-b-v_{k+1}... v_j$, ma nel mio $G$ non ci possono essere per ipotesi $v_k-a-b-v_{k+1}$ in cui primo e ultimo vertice sono connessi dallo spigolo del primo path è un 4-ciclo. Questo mi permette di dire che i path lunghi $n+2$ hanno al più $n-2$ lati in comune con un path lungo $n$.
Nella mia idea mi basterebbe fare $$a_{ij}^{(n+2)}-M$$
Ma come calcolo $M$ senza conoscere i sentieri in particolare?
In generale il grado di tutti i vertici li posso calcolare senza problemi, sarà pari all'elemento sulla diagonale di $A^2$.
Partiamo col considerare l'elemento di posto $i,j$ della matrice $A^{n+2}$. Questo conterà i cammini di lunghezza $n+2$ tra questi si troveranno i path (che è quanto voglio trovare) e anche quei cammini che non sono path. Come sono fatti questi due?
I secondi possono originare dai path lunghi $n$ in cui da ogni vertice $v$ passo ad uno adiacente e torno indietro (del tipo $v_i...w-a-w...v_j$). Questi saranno pari al numero di 2-cicli possibili partendo dai vertici visitati dal path meno $n$ poichè i due cicli che passano da un vertice all'altro del path e tornano indietro vengono contati due volte. Siano $p_k$ i path da $v_i$ a $v_j$ lunghi $n$, questi sono in numero pari $a_{ij}^{(n)}$ (dove uso impropriamente la notazione esponenziale per indicare il l'elemento della matrice $A^n$, sarà così anche nel proseguo) e siano $v_{k_i}$ i vertici visitati da $p_k$. Il numero di cammini non path definiti come sopra è pari a
$$M=(\sum_{k}\sum_{i}deg(v_{k_i}))-n\cdot a_{ij}^{(n)}$$
dove $deg(v)$ è il grado del vertice.
Per quanto riguarda i path lunghi $n+2$ potrei avere quelli che "deviano" da un path di lunghezza $n$ in questo modo $v_i- ... v_k-a-b-v_{k+1}... v_j$, ma nel mio $G$ non ci possono essere per ipotesi $v_k-a-b-v_{k+1}$ in cui primo e ultimo vertice sono connessi dallo spigolo del primo path è un 4-ciclo. Questo mi permette di dire che i path lunghi $n+2$ hanno al più $n-2$ lati in comune con un path lungo $n$.
Nella mia idea mi basterebbe fare $$a_{ij}^{(n+2)}-M$$
Ma come calcolo $M$ senza conoscere i sentieri in particolare?
In generale il grado di tutti i vertici li posso calcolare senza problemi, sarà pari all'elemento sulla diagonale di $A^2$.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo