1. Ce este Arborele și Pădurea?
Copac
- În teoria grafurilor, a copac este o graf nedirecționat, conex și aciclic . Cu alte cuvinte, un graf conectat care nu conține nici măcar un singur ciclu se numește arbore.
- Un arbore reprezintă structura ierarhică într-o formă grafică.
- Elementele copacilor se numesc nodurile lor, iar marginile arborelui se numesc ramuri.
- Un arbore cu n vârfuri are (n-1) muchii.
- Arborii oferă multe aplicații utile, atât de simple ca un arbore genealogic, la fel de complexe ca arborii în structurile de date ale informaticii.
- A frunze într-un copac este un vârf de gradul 1 sau orice vârf care nu are copii se numește frunză.
Exemplu
În exemplul de mai sus, toți sunt copaci cu mai puțin de 6 vârfuri.
pădure
În teoria grafurilor, a pădure este un graf nedirecționat, deconectat, aciclic . Cu alte cuvinte, o colecție disjunctă de copaci este cunoscută sub numele de pădure. Fiecare componentă a unei păduri este copac.
Exemplu
Graficul de mai sus arată ca două sub-grafice, dar este un singur grafic deconectat. Nu există cicluri în graficul de mai sus. Prin urmare este o pădure.
2. Proprietățile arborilor
- Fiecare copac care are cel puțin două vârfuri ar trebui să aibă cel puțin două frunze.
- Copacii au multe caracterizări:
Fie T un grafic cu n vârfuri, atunci următoarele afirmații sunt echivalente:- T este un copac.
- T nu conține cicluri și are n-1 muchii.
- T este conectat și are (n -1) muchie.
- T este un grafic conex și fiecare muchie este o muchie tăiată.
- Orice două vârfuri ale graficului T sunt conectate printr-o singură cale.
- T nu conține cicluri, iar pentru orice muchie nouă e, graficul T+ e are exact un ciclu.
- Fiecare margine a unui copac este tăiată.
- Adăugarea unei margini la un arbore definește exact un ciclu.
- Fiecare graf conectat conține un arbore de acoperire.
- Fiecare copac are cel puțin două vârfuri de gradul doi.
3. Spanning Tree
A copac spanning într-un graf conex G este un subgraf H al lui G care include toate vârfurile lui G și este, de asemenea, un arbore.
Exemplu
Luați în considerare următorul grafic G:
masa din latex
Din graficul de mai sus G putem implementa următorii trei arbori de acoperire H:
Metode de găsire a arborelui care se întinde
Putem găsi spanning tree în mod sistematic utilizând oricare dintre două metode:
- Metoda de tăiere
- Metoda de construire
1. Metoda tăierii
- Începeți să alegeți orice ciclu din graficul G.
- Scoateți una dintre marginile ciclului.
- Repetați acest proces până când nu mai rămân cicluri.
Exemplu
- Luați în considerare un grafic G,
- Dacă eliminăm muchia ac care distruge ciclul a-d-c-a din graficul de mai sus, atunci obținem următorul grafic:
- Îndepărtați muchia cb, care distruge ciclul a-d-c-b-a din graficul de mai sus, apoi obținem următorul grafic:
- Dacă eliminăm muchia ec, care distruge ciclul d-e-c-d din graficul de mai sus, atunci obținem următorul arbore de acoperire:
2. Metoda de construire
- Selectați marginile graficului G pe rând. În așa fel încât să nu existe cicluri sunt create.
- Repetați acest proces până când toate vârfurile sunt incluse.
Exemplu
Luați în considerare următorul grafic G,
- Alegeți marginea ab ,
- Alegeți marginea de ,
- După aceea, alegeți marginea ec ,
- Apoi, alegeți marginea cb , apoi în cele din urmă obținem următorul spanning tree:
Rangul circuitului
Numărul de muchii pe care trebuie să le ștergem din G pentru a obține un arbore care se întinde.
Arborele de întindere G = m- (n-1) , care se numește rangul circuitului a lui G.
pyspark sql
Where, m = No. of edges. n = No. of vertices.
Exemplu
În graficul de mai sus, muchiile m = 7 și vârfurile n = 5
Atunci rangul circuitului este,
G = m - (n - 1) = 7 - (5 - 1) = 3