Grafic conectat, grafic separat, componentă conectată, proprietăți
Un grafic neorientat este considerat conectat dacă din orice vârf există o cale către orice alt vârf (traseul poate consta din orice număr de margini). Exemplu: în figura de mai jos, graficul este conectat. Cu toate acestea, dacă ștergem o margine între nodurile 4 și 5, atunci nu va fi conectată - din punctul 5 nu va fi posibil să ajungeți la nici un alt vârf.
Dacă proprietatea de conectare nu se menține, graficul se numește deconectat.
Mai mult, nu considerăm multigrafe, adică grafice, în care două noduri pot fi unite cu două sau mai multe marginile. Ne limităm la analizarea graficelor în care fiecare pereche de vârfuri fie nu este conectată, fie este conectată printr-o singură margine.
Pentru un grafic cu n noduri care trebuie conectate, acesta trebuie să aibă cel puțin (n -1) marginile.
Dacă graficul are cel puțin margini (n * n - 3n + 4) / 2, atunci este garantată conectarea.
Dacă graficul este conectat, acesta are în mod necesar noduri de grad cel puțin 2, adică noduri, fiecare având cel puțin două noduri adiacente.
Dacă graficul este conectat și fără cicluri (adică acest arbore), atunci ștergerea oricărei margini va duce la pierderea conectivității.
Un grafic disjunctiv constă din componente conectate. O componentă conectată este un set de vârfuri, astfel încât din orice vârf al acestui set există o cale către orice alt vârf al acestui set, dar din orice vârf al acestui set nu se poate ajunge la un anumit vertex în afara acestui set. Evident, suma vârfurilor componentelor conectate este egală cu numărul de vârfuri ale graficului.
Figura arată un grafic cu două componente conectate.
Rețineți că componenta conectată poate consta dintr-un singur vertex. Dacă graficul are n noduri, atunci acesta nu poate consta în mai mult de n componente conectate. Pentru un grafic conectat, componenta conectată este unică.
Într-un grafic deconectat, fiecare componentă conectată constă din nu mai mult de n-1 vârfuri. Dacă știm că graficul k are o componentă conectată, atunci dăm o legătură mai puternică: orice componentă conectată constă din cel mult n-k + 1 noduri.
Dacă graficul conectat nu are un grafic k conectat, atunci pentru a obține un grafic conectat, adăugați cel puțin k-1 marginile graficului.
Cum se stabilește dacă este conectat un grafic?
Vom selecta un vertex A și îl vom marca ca vizitat (1), restul, respectiv, nu este încă vizitat (0):
A se presupune că este vârful actual. Procedăm după cum urmează. Marcați nodurile adiacente adăpostite: pentru punctul curent pe care îl căutăm adiacent la acesta, care nu este încă vizitat, și marcați-le ca vizitate.
Să presupunem că avem vârfuri k cu stea (în figura deasupra celor 3). Selectați unul dintre ele unul câte unul și marcați recursiv vârfurile adiacente nevizuse. Pentru vârful curent, recursiunea nu este efectuată dacă vârful dat nu are noduri adiacente care încă nu sunt marcate ca vizitate.
Dacă, după astfel de acțiuni, toate vârfurile sunt etichetate ca vizitate, graficul este coerent, altfel incoerent.
Să luăm un exemplu mic:
Aici numărul natural la vârf semnifică ceea ce a fost denumit ca fiind vizitat, culoarea verde a numărului înseamnă că a fost făcut un apel recursiv pentru acest vârf.
Am ales un vertex (1). Apoi, trei noduri adiacente sunt marcate (2, 3, 4). Vertexul curent devine acum (2). Recursion: Marcați două vârfuri adiacente care nu au fost încă vizitate (numerele 5 și 6). Pentru a (5), nu este nevoie de recurență - nu are noduri adiacente nevizitate, pentru este necesară (6) recursivitatea: marcăm numărul 7. 7 numere care nu au fost încă vizitat de „vecin“ - numărul 8, și aici, la numărul 8 nu exista noduri adiacente nevizitate. Toate apelurile recursive generate de vertex (2) sunt completate. Acum, vârful (3) este pe coadă, dar nu este nevoie de recurs. În partea de sus (4) rămâne. Unul dintre vârfurile sale adiacente (9) nu a fost încă marcat, corectăm. total:
Concluzie: nu toate vârfurile vizitate, graficul a fost deconectat.
Articole similare
-
Cunoștințe, prelegere, concepte de bază ale teoriei grafurilor
-
Supliment - grafic - o enciclopedie mare de petrol și gaze, articol, pagina 1
Trimiteți-le prietenilor: