Graficul conectat

Un graf conectat  este un graf care conține exact o componentă conectată . Aceasta înseamnă că există cel puțin o cale între orice pereche de vârfuri din acest grafic .

Exemple de aplicații

O aplicație directă a teoriei grafurilor este teoria rețelelor, iar aplicarea sa este teoria rețelelor electronice. De exemplu, toate computerele conectate la Internet formează un grafic conectat și, deși o pereche separată de computere poate să nu fie conectată direct (în formularea graficelor, să nu fie conectată printr-o muchie), informațiile pot fi transmise de la fiecare computer la orice altele (există o cale de la orice vârf al graficului la oricare altul).

Conectivitate pentru grafice direcționate

În graficele direcționate , se disting mai multe concepte de conectivitate.

Se spune că un grafic direcționat este puternic conectat dacă are o cale (direcționată) de la orice vârf la oricare altul sau, în mod echivalent, graficul conține exact o componentă puternic conectată .

Un graf direcționat se numește slab conectat dacă este un graf nedirecționat conexat obținut din acesta prin înlocuirea muchiilor direcționate cu cele nedirecționate.

Câteva criterii de conectivitate

Iată câteva definiții de criteriu (echivalente) ale unui graf conectat:
Un graf se numește simplu conex (conectat) dacă:

  1. Are o componentă conectată
  2. Există o cale de la orice vârf la orice alt vârf
  3. Există o cale de la un vârf dat la orice alt vârf
  4. Conține un subgraf conectat care include toate vârfurile graficului original
  5. Conține ca subgraf un arbore care include toate vârfurile graficului original (un astfel de arbore se numește arbore de întindere )
  6. Când vârfurile sale sunt împărțite în mod arbitrar în două grupuri, există întotdeauna cel puțin o muchie care conectează o pereche de vârfuri din grupuri diferite.

Vezi și