Question

Un graf neorientat cu 5 noduri este reprezentat prin matricea de adiacență alăturată. Indicați numărul grafurilor parțiale conexe ale acestuia care sunt diferite de graful dat.
0 1 0 1 1
1 0 1 0 0
0 1 0 1 0
1 0 1 0 0
10000
a. 4 b. 6 C. 8 d. 30 ​

Answer 1

Răspuns:

a. 4

Explicație:

• Graful parțial se obține din graful inițial păstrând nodurile și eliminând eventual niște muchii.
• Graful conex este acela în care între orice două noduri, există un lanț.

Uitându-ne pe matricea de adiacență, vom observa ca avem 5 muchii.
Ca un graf să fie conex, condiția necesară este ca oricare nod al lanțului, excluzând capetele (primul și ultimul), să aibă gradul cel puțin 2.

Ne uităm la nodurile noastre și observăm că nodurile 2, 3 și 4 au gradul 2, nodul 1 are gradul 3, iar nodul 5 are gradul 1, ceea ce înseamnă că acesta va fi mereu unul dintre capete.

• Nodurile 2, 3 și 4 având gradul 2, înseamnă ca putem elimina o muchie de la fiecare, obținând 3 grafuri parțiale conexe
• Nodul 1 având gradul 3, putem elimina 2 muchii obținând 2 grafuri parțiale conexe, DAR nodul 1 se leagă de nodul 5 care are gradul 1, ceea ce înseamnă că nu putem elimina muchia (1,5), graful nemaifiind conex daca am face-o, înseamnă că putem elimina doar o muchie și de la nodul 1, obținând în final încă un graf parțial conex.

În final, putem elimina pe rând muchiile (1,2), (1,4), (2,3), (3,4) obținând 4 grafuri parțiale conexe diferite de graful dat.