Teoria dei grafi - Alberi
Gli alberi sono grafici che non contengono nemmeno un singolo ciclo. Rappresentano la struttura gerarchica in forma grafica. Gli alberi appartengono alla classe di grafici più semplice. Nonostante la loro semplicità, hanno una struttura ricca.
Gli alberi forniscono una gamma di applicazioni utili da semplici come un albero genealogico a complesse come alberi nelle strutture dati dell'informatica.
Albero
UN connected acyclic graphsi chiama albero. In altre parole, un grafo connesso senza cicli è chiamato albero.
I bordi di un albero sono noti come branches. Gli elementi degli alberi sono chiamati i loro nodi. Vengono chiamati i nodi senza nodi figlioleaf nodes.
Un albero con vertici "n" ha bordi "n-1". Se ha un bordo in più rispetto a 'n-1', allora il bordo extra dovrebbe ovviamente accoppiarsi con due vertici che portano a formare un ciclo. Quindi, diventa un grafico ciclico che è una violazione per il grafico ad albero.
Example 1
Il grafico mostrato qui è un albero perché non ha cicli ed è connesso. Ha quattro vertici e tre bordi, cioè per 'n' vertici bordi 'n-1' come menzionato nella definizione.
Note - Ogni albero ha almeno due vertici di primo grado.
Example 2
Nell'esempio sopra, i vertici "a" e "d" hanno il grado uno. E gli altri due vertici "b" e "c" hanno il grado due. Ciò è possibile perché per non formare un ciclo, dovrebbero esserci almeno due bordi singoli ovunque nel grafico. Non è altro che due bordi con un grado di uno.
foresta
UN disconnected acyclic graphsi chiama foresta. In altre parole, una raccolta disgiunta di alberi è chiamata foresta.
Example
Il grafico seguente assomiglia a due sottografi; ma è un unico grafo disconnesso. Non ci sono cicli in questo grafico. Quindi, chiaramente è una foresta.
Spanning Trees
Sia G un grafo connesso, allora il sottografo H di G è chiamato spanning tree di G se -
- H è un albero
- H contiene tutti i vertici di G.
Uno spanning tree T di un grafo non orientato G è un sottografo che include tutti i vertici di G.
Example
Nell'esempio sopra, G è un grafo connesso e H è un sottografo di G.
Chiaramente, il grafo H non ha cicli, è un albero con sei spigoli che è uno in meno del numero totale di vertici. Quindi H è lo Spanning tree di G.
Classifica del circuito
Sia 'G' un grafo connesso con 'n' vertici e bordi 'm'. Uno spanning tree 'T' di G contiene (n-1) archi.
Pertanto, il numero di archi che è necessario eliminare da "G" per ottenere uno spanning tree = m- (n-1), che è chiamato rango del circuito di G.
Questa formula è vera, perché in uno spanning tree è necessario avere bordi "n-1". Fuori dagli archi 'm', è necessario mantenere gli archi 'n – 1' nel grafico.
Quindi, cancellando 'n – 1' archi da 'm' si ottengono gli archi da rimuovere dal grafico per ottenere uno spanning tree, che non dovrebbe formare un ciclo.
Example
Dai un'occhiata al grafico seguente:
Per il grafico dato nell'esempio sopra, hai m = 7 spigoli en = 5 vertici.
Quindi la classifica del circuito è -
Example
Sia 'G' un grafo connesso con sei vertici e il grado di ogni vertice è tre. Trova il rango del circuito "G".
Per la somma del teorema del grado dei vertici,
Teorema di Kirchoff
Il teorema di Kirchoff è utile per trovare il numero di spanning tree che possono essere formati da un grafo connesso.
Example
La matrice "A" deve essere riempita come se ci fosse un bordo tra due vertici, allora dovrebbe essere data come "1", altrimenti "0".
$$ A = \ begin {vmatrix} 0 & a & b & c & d \\ a & 0 & 1 & 1 & 1 \\ b & 1 & 0 & 0 & 1 \\ c & 1 & 0 & 0 & 1 \\ d & 1 & 1 & 1 & 0 \ end {vmatrix} = \ begin {vmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \ end {vmatrix} $$Usando il teorema di Kirchoff, dovrebbe essere modificato sostituendo i valori diagonali principali con il grado dei vertici e tutti gli altri elementi con -1.A
$$ = \ begin {vmatrix} 3 & -1 & -1 & -1 \\ - 1 & 2 & 0 & -1 \\ - 1 & 0 & 2 & -1 \\ - 1 & -1 & -1 & 3 \ end {vmatrix} = M $$ $$ M = \ begin {vmatrix} 3 & -1 & -1 & -1 \\ - 1 & 2 & 0 & -1 \\ - 1 & 0 & 2 & -1 \\ - 1 & -1 & -1 & 3 \ end {vmatrix} = 8 $$ $$ Co \: \: factor \: \: of \: \: m1 \: \: = \ begin {vmatrix } 2 & 0 & -1 \\ 0 & 2 & -1 \\ - 1 & -1 & 3 \ end {vmatrix} $$Pertanto, il numero di spanning tree = 8.