logo

Arborele și Pădurea

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

Arborele și Pădurea

Î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

Arborele și Pădurea

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

  1. Fiecare copac care are cel puțin două vârfuri ar trebui să aibă cel puțin două frunze.
  2. 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.
  3. Fiecare margine a unui copac este tăiată.
  4. Adăugarea unei margini la un arbore definește exact un ciclu.
  5. Fiecare graf conectat conține un arbore de acoperire.
  6. 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
Arborele și Pădurea

Din graficul de mai sus G putem implementa următorii trei arbori de acoperire H:

Arborele și Pădurea

Metode de găsire a arborelui care se întinde

Putem găsi spanning tree în mod sistematic utilizând oricare dintre două metode:

  1. Metoda de tăiere
  2. 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,
Arborele și Pădurea
  • Dacă eliminăm muchia ac care distruge ciclul a-d-c-a din graficul de mai sus, atunci obținem următorul grafic:
Arborele și Pădurea
  • Îndepărtați muchia cb, care distruge ciclul a-d-c-b-a din graficul de mai sus, apoi obținem următorul grafic:
Arborele și Pădurea
  • 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:
Arborele și Pădurea

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,

Arborele și Pădurea
  • Alegeți marginea ab ,
Arborele și Pădurea
  • Alegeți marginea de ,
Arborele și Pădurea
  • După aceea, alegeți marginea ec ,
Arborele și Pădurea
  • Apoi, alegeți marginea cb , apoi în cele din urmă obținem următorul spanning tree:
Arborele și Pădurea

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

Arborele și Pădurea

Î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