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 .
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).
Î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.
Iată câteva definiții de criteriu (echivalente) ale unui graf conectat:
Un graf se numește simplu conex (conectat) dacă: