Grafuri-Fisa de lucru 4

Fisa de lucru 4

I.Aplicaţii Bacalaureat

    1. Fie un graf neorientat cu n=6 noduri, care are următoarele muchii: (1, 2), (1, 3), (3, 5),(3, 6), (5, 6), (4, 6).Care este numărul minim de muchii ce trebuie mutate în graful din figură astfel încât acesta să fie conex şi fiecare nod să aparţină unui ciclu?

    1. Graful neorientat cu 60 de noduri, numerotate de la 1 la 60, are numai muchiile: [1,60], [60,20], [2,30] şi [4,30]. Numărul componentelor conexe ale grafului este egal cu:

    1. Fie un graf neorientat cu n=5 noduri, care are următoarele muchii:(1,2), (1,4), (1,3), (3,4), (2,4), (4,5), (2,5).Care este numărul minim de muchii ce se pot elimina astfel încât graful parţial obţinut să aibă exact 3 componente conexe?

  1. Care este numărul maxim de muchii pe care-l poate avea un graf neorientat cu 6 noduri, care nu este conex?

    1. Dacă G este un graf neorientat cu 11 noduri şi 13 muchii, fără noduri cu gradul 0, atunci numărul maxim de componente conexe pe care le poate avea graful este:

  1. Dacă G este un graf neorientat cu 8 noduri şi 2 componente conexe, atunci graful are cel mult:

    1. Se consideră graful neorientat definit prin mulţimea nodurilor {1,2,3,4,5,6} şi muchiile [1,2],[1,3],[2,3],[6,5],[3,4],[4,5],[4,6]. Care este numărul maxim de muchii care pot fi eliminate din graf pentru a se obţine un graf parţial al său care să fie conex?

    1. Fie un graf neorientat cu n=5 noduri care are următoarele muchii: (1,5), (2,5), (3,5), (4,5).Care este numărul minim de noduri ce trebuie eliminate din graful alăturat astfel încât subgraful obţinut să nu fie conex?

  1. Se consideră un graf neorientat G cu 12 noduri si 7 muchii. Care este numărul maxim de componente conexe din care poate fi format graful G?

  2. Se consideră graful neorientat definit prin mulţimea vârfurilor {1, 2, 3, 4, 5, 6} şi mulţimea muchiilor {[1,2], [2,3], [3,4], [3,5], [4,5], [1,3], [2,6], [2,4], [4,6]}. Care este numărul minim de muchii ce pot fi eliminate astfel încât graful parţial obţinut să nu mai fie conex?

  3. Scrieţi listele de adiacenţă prin care este reprezentat un exemplu de graf neorientat conex, cu 6 noduri, numerotate de la 1 la 6, care este eulerian, dar NU este hamiltonian.

  4. Un graf neorientat cu 10 noduri, numerotate de la 1 la 10, este reprezentat cu ajutorul listelor de adiacenţă alăturate. Câte componente conexe are graful şi care este numărul minim de muchii ce trebuie adăugate pentru ca graful să fie conex?

          1. Listele de adiacentă:

          2. 1:3, 5

          3. 2:4

          4. 3:1, 5

          5. 4:2, 8

          6. 5:1, 3

          7. 6:

          8. 7:10

          9. 8:4

          10. 9:

          11. 10:7

  1. Se consideră un graf neorientat cu 7 noduri, numerotate de la 1 la 7 şi muchiile [1,5], [2,3], [2,4], [2,5], [3,4], [4,5], [4,7], [5,6], [5,7]. Care este numărul minim de muchii care trebuie eliminate astfel încât graful parţial obţinut să aibă 3 componente conexe?

    1. Se consideră un graf neorientat cu 8 noduri, numerotate de la 1 la 8, şi muchiile [1,5], [1,6], [2,6], [3,4], [3,6], [3,7], [4,6], [6,8], [7,8]. Dacă se elimină nodul 6 şi toate muchiile incidente cu acesta câte componente conexe va avea subgraful rezultat?

    2. Care este numărul maxim de muchii pe care îl poate avea un graf neorientat cu 6 noduri şi 3 componente conexe?

            1. Se consideră un graf neorientat dat prin listele de adiacenţă alăturate. Care este numărul maxim de muchii care pot fi eliminate din graf astfel încât graful parţial rezultat să fie conex ?

            1. Listele de adiacenta sunt:

            2. 1: 2 3

            3. 2:1 3 4

            4. 3:1 2 4 5

            5. 4:2 3 5

            6. 5:3 4

    1. Fie un graf neorientat cu n=10 noduri, care are următoarele muchii: (1,2), (1,3), (3,9), (6,7), (7,8), (6,5), (8,5). Care este numărul minim de muchii care trebuie adăugate grafului alăturat pentru a deveni conex şi eulerian?

    2. Se consideră un graf neorientat cu 8 noduri, numerotate de la 1 la 8, şi muchiile: [1,4], [1,8], [2,1], [2,3], [3,1], [4,5], [4,7], [5,7], [6,5]. Scrieţi câte componente conexe are graful dat şi care este nodul ce trebuie eliminat astfel încât subgraful obţinut să aibă un număr maxim de componente conexe.

    3. Care este numărul minim de noduri cu gradul 1 pentru un graf neorientat conex cu 21 noduri şi 20 muchii?

    4. Care este numărul minim de muchii ale unui graf neorientat conex, cu 100 de noduri?

    5. Considerăm un graf neorientat cu 5 noduri şi 3 muchii format din două componente conexe. Ştiind că doar patru dintre noduri au gradul 1, scrieţi matricea de adiacenţă a grafului.

    6. Se consideră graful neorientat cu 6 noduri, numerotate cu 1, 2, 3, 4, 5, 6, şi 9 muchii dat prin listele de adiacenţă alăturate.

  1. 1: 2, 5, 6

  2. 2: 1, 3, 4

  3. 3: 2, 4, 6

  4. 4: 2, 3, 5

  5. 5: 1, 4, 6

  6. 6: 1, 3, 5

  7. a) Care este cel mai scurt lanţ cu o extremitate în nodul 1 şi cealaltă extremitate în nodul 3?

  8. b) Care este numărul maxim de muchii ce pot fi eliminate astfel încât graful parţial obţinut să rămână conex?

    1. Se consideră graful neorientat cu 6 noduri, numerotate de la 1 la 6 şi următoarele muchii: [1,3] [1,5] [2,3] [2,4] [2,6] [5,3] [6,4].

  9. a) Care este numărul minim de muchii ce trebuie eliminate din acest graf, astfel încât graful parţial obţinut să nu conţină niciun ciclu?

  10. b) Care este numărul minim de muchii ce trebuie eliminate din graful iniţial dat, astfel încât graful parţial obţinut să aibă exact două componente conexe?

24. Fie următorul graf:

Răspundeţi la următoarele întrebări:

a. care este rezultatul parcurgerii în lăţime dacă nodul de start este:

3:

5:

8:

b. care este rezultatul parcurgerii în adâncime dacă nodul de start este:

3:

5:

8:

c. Câte circuite elementare conţine graful

d. Care sunt nodurile de grad maxim?

e. Câte noduri terminale conţine graful?

f. Graful este bipartit? Demonstraţi răspunsul folosind una dintre parcurgeri.

II. Probleme

  1. SPEOLOGIE: Un grup de speologi cercetează mai multe încăperi subterane (n >= 1) şi culoarele care le leagă pentru a stabili dacă acestea formează una sau mai multe peşteri. O peşteră este formată din toate încăperile între care se poate circula. Cercetătorii marchează traseul de deplasare propunându-şi să nu viziteze două camere de două ori. De fiecare dată, speologii se vor îndrepta spre camera cu numărul de ordine minim în care se poate ajunge plecând din camera curentă. Dacă la un moment dat traseul nu mai poate continua, ei se vor întoarce pe acelaşi drum până la o cameră din care mai există culoare nemarcate sau până părăsesc peştera. Stabiliţi dacă cercetătorii au parcurs întreaga peşteră şi care este traseul urmat.

    1. Date de intrare se citesc din fişierul text PESTERI .TXT care are forma:

    2. N - numărul de camere subterane

    3. Ns - camera principală ( intrarea in peşteră ) Perechi de numere de forma i j cu semnificaţia că între camera i şi camera j există un culoar.

  2. SATELITI ARTIFICIALI :

    1. Se preconizează lansarea pe orbită a unui grup de n sateliţi artificiali. Doi sateliţi pot transmite date de la unul la altul fie în mod direct fie prin intermediul altor sateliţi intermediari. Spunem că doi sateliţi sunt vecini numai dacă ei pot transmite date unul altuia în mod direct. Scrieţi un program care verifică dacă se poate transmite o informaţie de pe planeta Pământ către toţi sateliţii de pe orbită ştiind că semnalul iniţial este transmis satelitului cu număr maxim de vecini. În caz negativ precizaţi câte grupuri sunt şi care sunt sateliţi între care se poate comunica.

  1. FILIALE: O firmă are n filiale in judeţ. Drumurile sunt înzăpezite, dar se cunoaşte între ce filiale se poate ajunge cu maşina. Se cere:

      • ce filiale poate vizita un reprezentant ce pleacă de la sediu;

      • care este suma pe care o strânge in drumul sau, cunoscând ce profit a realizat fiecare filială

      • care este filiala cu cel mai mic profit si care este filiala cu cel mai mare profit.

    1. GRAF CONEX: Se citeşte matricea de adiacenţă a unui graf conex. Sa se elimine un nod astfel încât graful obţinut astfel sa rămână conex