Question

Se dă un graf neorientat cu 75 de noduri numerotate de la 1 la 75, şi muchiile [21,40], [30,38], [21,30], [60,75]. Atunci numărul de componente conexe ale grafului este:

Answer 1

Răspuns:

Numărul de componente conexe ale grafului este de 74.

Explicație:

O componentă conexă a unui graf neorientat este un set de noduri care sunt toate conectate prin cel puțin o cale. Când sunt adăugate muchiile menționate, acestea creează doar patru conexiuni între nodurile specifice. Deci, acestea nu au un impact asupra celorlalte 71 de noduri, care rămân în componente separate individuale. Prin urmare, numărul total de componente conexe ale grafului este de 74 noduri separate + 1 componentă formată din cele 4 noduri conectate = 75.