Grafuri-Fisa de lucru 2
Fișa de lucru 2
1. Fie un graf neorientat cu 6 noduri memorat prin următoarea listă de adiacență. Reprezentați grafic graful neorientat.
1: 2 5 6
2:1 3 4
3:2 4 6
4:2 3 5
5:1 4 6
6: 1 3 5
2. Fie un graf neorientat cu 5 noduri memorat în următoarea matrice de adiacență. Răspundeţi la următoarele întrebări:
a) Care este lista vecinilor nodului 4?
b) Există în graf noduri izolate sau noduri terminale?
c) Care este nodul de grad maxim?
d) Câte muchii conţine graful?
0 1 0 1 1
1 0 1 0 1
0 1 0 1 1
1 0 1 0 1
1 1 1 1 0
3. Pentru următorul graf cu 5 noduri realizaţi:
a) matricea de adiacență;
b) listele de vecini pentru fiecare nod utilizând reprezentarea statică
c) vectorul de muchii
4. Care dintre următoarele variante poate fi o linie din matrice de adiacență a graful următor:
a. 0 1 1 1 0 0
b. 0 0 0 0 1 0
c. 0 0 1 1 0 1
d. 1 1 1 0 1 1
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:
4
4
1 2
1 4
se va afișa mesajul
1 2
1 4
4 3
3 2
se va afișa mesajul
Graful nu conține noduri izolate!
Graful conține noduri izolate!
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:
5
1 2
2 3
2 4
2 5
4 3
4 5
3 5
3 1
se va afișa mesajul
Gradul maxim este 4.
Nodurile de grad maxim sunt: 2 3
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:
5
0 1 0 1 1
1 0 1 0 1
0 1 0 1 1
1 0 1 0 1
1 1 1 1 0
se va afișa mesajul:
5
0 1 0 1 1
1 0 1 0 1
0 0 0 1 1
1 0 1 0 1
1 0 1 0 1
se va afișa mesajul:
Este graf neorientat!
Nu este graf neorientat!
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:
5 3
1 2
2 3
2 4
2 5
4 3
4 5
3 5
3 1
se va afișa mesajul
Muchiile incidente cu nodul 3 sunt: (1,3),(2,3),(4,3),(5,3)
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:
5
0 1 1 1 1
1 0 1 1 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0
se va afișa mesajul:
5
0 1 0 1 1
1 0 1 0 1
0 1 0 1 1
1 0 1 0 1
1 1 1 1 0
se va afișa mesajul:
Este graf complet!
Nu este graf complet!
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:
4
0 1 1 0
1 0 0 1
1 0 0 1
0 1 1 0
se va afișa mesajul:
5
0 1 0 1 1
1 0 1 0 1
0 1 0 1 1
1 0 1 0 1
1 1 1 1 0
se va afișa mesajul:
Este graf regulat!
Nu este graf regulat!
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:
Număr solutie
Soluţia 1:(0,0,0,0,0,0)
Soluţia 2:(0,0,0,0,0,1)
Solutia 3:(0,0,0,0,1,1)
ultima solutie:(1,1,1,1,1,1)
Matrice de adiacenta
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 1
0 0 1 0
Multimea muchiilor:
U={(3,4)}
0 0 0 0
0 0 0 1
0 0 0 1
0 1 1 0
Multimea muchiilor:
U={(2,4), (3,4)}
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
Multimea muchiilor:
U={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}
Graf desenat
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:
- de tipul 1: relaţie de căsătorie
- de tipul 2: relaţie de tip părinte-fiu ( nu are importanţă cine este părintele şi cine este fiul)
Să se verifice:
a) dacă relaţiile de căsătorie sunt corecte, adică nu există persoane căsătorite cu mai mult de o persoană. In cazul in care astfel de situatii sunt intalnite, sa se afiseze persoana cu mai multi pateneri si partenerii acestora
b) dacă există persoane necăsătorite