Grafuri-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. 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.

3. 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:

   2. • 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