Graf conex

1. Scrieți listele de adiacență pentru un graf neorientat cu 10 noduri și 2 componente conexe, astfel încât componenta conexă ce conține nodul 1 să reprezinte un subgraf care e hamiltonian, dar nu e eulerian, iar componenta conexă ce conține nodul 2 să reprezinte un subgraf care nu e hamiltonian, dar e eulerian.

2. Se consideră un graf nerientat cu n noduri (n>2). Scrieți valoarea de adevăr a fiecărei propoziții:

a) Un graf complet este întotdeauna un graf hamiltonian

b) Un graf complet este întotdeauna un graf eulerian

c) Un graf hamiltonian este întotdeauna conex.

d) Un graf eulerian este întotdeauna conex.

e) Un graf conex cu n noduri și n-1 muchii poate fi Hamiltonian.

3. Se consideră un graf neorientat complet cu 20 de noduri.

a) Să se determine numărul minim de muchii ce pot fi eliminate, pentru ca graful partial obținut să fie Eulerian.

b) Să se determine numărul maxim de muchii ce pot fi eliminate, pentru ca graful partial obținut să rămână Hamiltonian.

4. Se consideră un graf neorientat cu 80 de noduri și 65 de muchii.

a) Care este numărul maxim de componente conexe pe care le poate avea graful?

b) Care este numărul minim de componente conexe pe care le poate avea graful?

5. Se consideră graful neorientat G cu 7 noduri și muchiile: [1,2], [2,3], [3,6], [6,7], [2,4], [3,4], [3,5], [4,5], [5,6]. Să se adauge un nr minim de muchii astfel încât graful obținut să fie Hamiltonian.

a) Dați exemplu de astfel de muchii ce pot fi adăugate.

b) Scrieți un ciclu Hamiltonian pentru graful obținut.

6. Se consideră graful neorientat G cu 7 noduri și muchiile: [1,2], [2,3], [3,6], [6,7], [2,4], [3,4], [3,5], [4,5], [5,6]. Să se adauge un nr minim de muchii astfel încât graful obținut să fie Eulerian.

a) Dați exemplu de astfel de muchii ce pot fi adăugate.

b) Scrieți un ciclu Eulerian pentru graful obținut.

7. Se consideră graful neorientat G cu 7 noduri și muchiile: [1,2], [2,3], [3,6], [6,7], [2,4], [3,4], [3,5], [4,5], [5,6]. Să se adauge un nr minim de muchii astfel încât graful obținut să fie bipartit.

a) Dați exemplu de astfel de muchii ce pot fi adăugate.

b) Scrieți elementele celor două mulțimi A și B obținute, care formează o partiție a mulțimii nodurilor.

8. a) Scrieți nodurile obținute în urma parcurgerii în lățime (BFS), începând de la nodul 1.

b) Scrieți nodurile obținute în urma parcurgerii în adâncime (DFS), începând de la nodul 7.

9. Fie n>1 număr natural. Care este numărul minim de muchii ale unui graf neorientat cu 2*n noduri care are exact două componente conexe, cele 2 componente conexe fiind grafuri complete?