Grafuri-Fisa de lucru 2

5. Orice graf neorientat cu n noduri are o matrice de adiacen'[ cu urm[toarea proprietate:

       a) este simetrică faţă de diagonala principală;

       b) suma valorilor de 1 din matricea de adiacenţă este egală cu n- număril de noduri;

       c) este simetrică faţă de diagonala secundară;

       d) conţine doar următoarele valori: -1, 0, 1.

6. Scrieţi un program C++ care să verifice dacă graful G, memorat în fișierul text graf.in conține noduri izolate. Fișierul text graf.in conține pe prima linie un număr natural n, care reprezintă numărul de noduri din graf, iar pe următoarele linii perechi de valori naturale care reprezintă muchiile grafului.

Exemplu:

Dacă conținutul fișierului text graf.in este:

6. Scrieti un program C++ care să determine nodurile de grad maxim din graful G, memorat în fișierul text graf.in. Fișierul  text  graf.in conține pe prima linie un număr natural n, care reprezintă numărul de noduri din graf iar pe următoarele linii perechi de valori naturale care reprezintă muchiile grafului.

Exemplu:

Dacă conținutul fișierului text graf.in este:

 7. Scrieți un program care verifică dacă graful memorat în fișierul text graf.txt este neorientat. Fișierul text graf.txt conține pe prima linie linie un număr natural ce reprezintă numărul de noduri din graf, iar în continuare matricea de adiacență.

Exemplu:

  Dacă conținutul fișierului text graf.txt este:

8. Să se afișeze muchiile incidente cu un nod x. Graful se va citi din fișierul text graf.in care are pe prima linie două numere naturale: n- numărul de noduri și x un nod din graf. Pe următoarele linii sunt memorate perechi de numere naturale ce reprezintă muchiile grafului.

Exemplu:

Dacă conținutul fișierului text graf.in este:

9. Scrieți un program care verifică dacă graful memorat în fișierul text graf.txt este graf complet. Fișierul text graf.txt conține pe prima linie linie un număr natural ce reprezintă numărul de noduri din graf, iar în continuare matricea de adiacență.

Exemplu:

  Dacă conținutul fișierului text graf.txt este:

10. Scrieți un program care verifică dacă graful memorat în fișierul text graf.txt este graf regulat (un graf neorientat este regulat dacă și numai dacă gradele tuturor nodurilor sunt egale). Fișierul text graf.txt conține pe prima linie linie un număr natural ce reprezintă numărul de noduri din graf, iar în continuare matricea de adiacență.

Exemplu:

  Dacă conținutul fișierului text graf.txt este:

11. Scrieţi un program care generează şi afisează toate grafurile neorientate cu n noduri. Pentru fiecare soluţie se va afişa matricea de adiacenţă şi mulţimea muchiilor.

Exemplu:

Dacă n=4 atunci soluţiile pot fi de forma:

12. PROBLEMA COLORĂRII UNEI HĂRȚI: Se dă structura unei hărți care conține desenate N tări, numerotate de la 1 la N. Se cere să se determine toate posibilitățile de colorare a țărilor cu 4 culori astfel încât, două țări care au graniță comună să nu fie colorate cu aceiași culoare.

13. PROBLEMA COLORĂRII MUCHIILOR UNUI GRAF:Se dă un graf neorientat cu N noduri. Se cere să se coloreze muchiile grafului utilizând un număr minim de culori, astfel încât două muchii incidente în același nod să nu fie colorate cu aceiași culoare.

14. Din fişierul graf.in se citeşte de pe prima linie valorile n (numărul de noduri) şi m  (numărul de muchii) ale unui graf neorientat G=(X, U). De pe următoarele m linii se citeşte lista muchiilor. Scrieţi funcţiile pentru: 

    a) Citirea grafului; 

    b) Afişaţi matricea de adiacenţă a grafului; 

    c) Afişaţi gradele tuturor nodurilor 

    d) Afişaţi toate nodurile de grad maxim 

    e) Afişaţi toate nodurile terminale 

    f) Afişaţi toate nodurile izolate

15. Din fişierul graf.in se citeşte de pe prima linie valorile n (numărul de noduri) şi m  (numărul de muchii) ale unui graf neorientat G=(X,U). De pe următoarele m linii se citeşte lista muchiilor. Scrieţi funcţiile pentru: 

    a) Citirea grafului; 

    b) Afişaţi listele de adiacentă; 

    c) Afişaţi vârfurile cu număr maxim de vecini; 

    d) Afişaţi vărfurile cu un singur vecin; 

    e) Afişati vărfurile fără vecini

16. PRIETENI: Într-un grup de n persoane se cunosc relaţiile de prietenie dintre membrii grupului, care sunt reciproce. Scrieţi un program C++ care determină persoana cu cei mai mulţi prieteni şi numărul acestora. Verificaţi apoi dacă în grup există un “morocănos” (adică o persoană care nu este prieten cu nici unul din membrii grupului). 

18. Relaţii de căsătorie: La o petrecere sunt invitaţi să participe n persoane.  Între invitaţi există relaţii directe de rudenie de două tipuri:    

b) dacă există persoane necăsătorite