1. Cos'è Albero e foresta?
Albero
- Nella teoria dei grafi, a albero è un grafo non orientato, connesso e aciclico . In altre parole, un grafo connesso che non contiene nemmeno un singolo ciclo è chiamato albero.
- Un albero rappresenta la struttura gerarchica in forma grafica.
- Gli elementi degli alberi sono chiamati nodi e i bordi dell'albero sono chiamati rami.
- Un albero con n vertici ha (n-1) spigoli.
- Gli alberi forniscono molte applicazioni utili, da semplici come un albero genealogico a complesse come gli alberi nelle strutture dati dell'informatica.
- UN foglia in un albero c'è un vertice di grado 1 oppure qualsiasi vertice che non ha figli è chiamato foglia.
Esempio
Nell'esempio sopra, sono tutti alberi con meno di 6 vertici.
foresta
Nella teoria dei grafi, a foresta È un grafo non orientato, disconnesso, aciclico . In altre parole, un insieme disgiunto di alberi è noto come foresta. Ogni componente di una foresta è un albero.
Esempio
Il grafico sopra sembra composto da due sottografi ma è un singolo grafico disconnesso. Non ci sono cicli nel grafico sopra. Quindi è una foresta.
2. Proprietà degli alberi
- Ogni albero che ha almeno due vertici dovrebbe avere almeno due foglie.
- Gli alberi hanno molte caratterizzazioni:
Sia T un grafo con n vertici, allora le seguenti affermazioni sono equivalenti:- T è un albero.
- T non contiene cicli e ha n-1 archi.
- T è connesso e ha (n -1) archi.
- T è un grafo connesso e ogni arco è un arco tagliato.
- Due vertici qualsiasi del grafo T sono collegati esattamente da un percorso.
- T non contiene cicli e per ogni nuovo arco e, il grafico T+ e ha esattamente un ciclo.
- Ogni bordo di un albero è tagliato.
- L'aggiunta di un bordo ad un albero definisce esattamente un ciclo.
- Ogni grafo connesso contiene uno spanning tree.
- Ogni albero ha almeno due vertici di grado due.
3. Albero di copertura
UN albero di copertura in un grafo connesso G è un sottografo H di G che include tutti i vertici di G ed è anche un albero.
Esempio
Consideriamo il seguente grafico G:
Dal grafo G sopra possiamo implementare i seguenti tre spanning tree H:
Metodi per trovare lo spanning Tree
Possiamo trovare sistematicamente lo spanning tree utilizzando uno dei due metodi:
- Metodo di riduzione
- Metodo di costruzione
1. Metodo di riduzione
- Inizia a scegliere qualsiasi ciclo nel grafico G.
- Rimuovere uno dei bordi del ciclo.
- Ripetere questo processo fino a quando non rimangono più cicli.
Esempio
- Consideriamo un grafo G,
- Se rimuoviamo il bordo ac che distrugge il ciclo a-d-c-a nel grafico sopra, otteniamo il seguente grafico:
- Rimuovendo il bordo cb, che distrugge il ciclo a-d-c-b-a dal grafico sopra, otteniamo il seguente grafico:
- Se rimuoviamo l'arco ec, che distrugge il ciclo d-e-c-d dal grafico sopra, otteniamo il seguente spanning tree:
2. Metodo di costruzione
- Seleziona i bordi del grafico G uno alla volta. In modo tale che non si creino cicli.
- Ripeti questo processo fino a includere tutti i vertici.
Esempio
Consideriamo il seguente grafico G,
- Scegli il bordo ab ,
- Scegli il bordo Di ,
- Successivamente, scegli il bordo ecc ,
- Quindi, scegli il bordo cb , quindi finalmente otteniamo il seguente spanning tree:
Classifica del circuito
Il numero di archi che dobbiamo eliminare da G per ottenere uno spanning tree.
Albero di supporto G = m- (n-1) , che si chiama rango del circuito di G.
Where, m = No. of edges. n = No. of vertices.
Esempio
Nel grafico sopra, i bordi m = 7 e i vertici n = 5
Quindi il rango del circuito è,
G = m - (n - 1) = 7 - (5 - 1) = 3