Componentele conexe sunt bucățile din graf care ar putea zbura liniștite dacă ar fi lăsate în spațiu. :))
Adică, dacă ai un graf în care 1 e conectat cu 2, iar 3 e conectat cu 4. Ai 2 bucăți care pot zbura independent una de alta, așadar 2 componente conexe. (Figura 1)
Dacă ai un graf în care 1 nu e conectat cu nimic, 2 nu e conectat cu nimic, iar 3 e conectat de 4 și de 5, ai 3 componente conexe(prima - 1, a doua - 2, a treia 3-4-5). (Figura 2)
Acum, pentru întrebarea ta: graf cu 6 noduri:
Maximul
Un graf cu 6 noduri... ar putea avea cel mult 6 componente conexe. De ce?
Pentru că, dacă lași toate cele 6 noduri neconectate, niciunul cu niciunul dintre ele, vor fi exact 6 bule zburătoare independente una de alta, așadar 6 componente conexe. (Figura 3)
Minimul
Iar cel puțin, un graf cu 6 noduri are 1 component. De ce? Pentru că dacă le conectezi pe toate (e destul și în lanț, nu mai mult, ci doar 1-2-3-4-5-6, de ex), deja sunt dependente unele de altele și rămâne un singur element care zboară :)) așadar un singur component conex. (Figura 4)
Partea cu „plutesc/zboară în spațiu” nu face parte din teorie, e doar un artificiu de exprimare pentru a fi înțeles mai ușor. :))
În manuale definiția e dată așa:
„Se numeşte componentă conexă a grafului G=(X,U), un subgraf C=(X1,U1) conex al lui G care are
proprietatea că nu există nici un lanţ în G care să lege un vârf din mulţimea X1 cu un vârf din mulţimea X-X1.” de obicei, doar că nu e atât de clară, aș zice. :))
