Question

Cum se afla maximul/minimul de componente conexe a unui graf de ex cu 6 noduri? Cum imi dau seama cate componente conexe are un graf? Daca se poate si desen

Answer 1

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. :))