Nume si prenume: Clasa a XI-a Data:

Pagin2TestGrafuri neorientate

Subiectul I1. Se consider un graf neorientat cu n=6 si muchiile:

(5 p)(1,2), (1,4), (2,3), (3,4) , (3,5), (4,6), (5,6).

(5 p)a) Graful este hamiltonian? Justificai rspunsul dat.b) Graful este eulerian? Justificai rspunsul dat. 2. Se consider un graf neorientat cu n=9 i muchiile:

(10 p)(3,2), (3,4), (2,1), (4,5), (4,6), (5,7), (5,8), (6,9).Graful dat este arbore? Justificai rspunsul dat. Dac rspunsul este afirmativ, menionai care dintre vrfuri sunt frunze.

(10 p)Subiectul II1. Care este numrul maxim de muchii pe care l poate avea un graf neorientat cu 6 vrfuri i 3 componente conexe?

(10 p)2. xxxxxx135Se consider graful din figura urmtoare. Care este numrul minim de muchii care se pot elimina astfel nct graful s aib exact 3 componente conexe? a) 2; b) 4; c) 1; d) 3.

42

Subiectul III1. Se d graful neorientat cu 8 vrfuri numerotate de la 1 la 8 i muchiile:

(9 p)(1,2), (1,3), (1,5), (2,4), (2,7), (3,5), (3,6), (3,7), (4,5), (5,7).

(8 p)a) Pentru graful dat realizai lista vecinilor i matricea de adiacen.

(8 p)b) Parcurgei graful in lime pornind din vrful 3 i n adncime pornind din vrful 1.c) Graful dat este complet? Dac graful nu este complet, precizai cte muchii mai sunt necesare pentru ca acesta s devin.

(25 p)2. Harta rutier a unei ri poate fi reprezentat de un graf neorientat G={x, U} unde x reprezintmulimea oraelor (n elemente), iar U - mulimea oselelor (m elemente) existente (o sosea leag oricare 2 orae), fiecare osea fiind caracterizat prin distana n kilometri (numr natural). Trei prieteni se gsesc n 3 orae distincte (X, Y i Z) i i propun s se ntlneasc ntr-un ora T.Calculai i afiai distana minim pe care o parcurge fiecare prieten din oraul de pornire pn n oraul T de destinaie. Afiai cele trei orae de plecare (X,Y i Z) n ordinea n care cei trei prieteni ajung n oraul T.

Not: Programul va conine cel puin un subprogram definit de utilizator.

Exemplu:date.indate.out

8 10 (n,m)1 2 20 (oras 1, oras 2, distanta)1 3 351 7 202 4 30 3 4 40 3 6 40 3 8 80 4 5 25 5 6 5 6 8 30 1 5 3 6 (X,Y,Z,T)

Distanele parcurse de cei trei prieteni: 80 5 70 Oraele de plecare n ordinea n care ajung cei trei prieteni: 5 3 1

Se vor acorda 10 puncte din oficiu.

Pagin1Clasa a XI-a CBoriaru Elena, Grigore Iulia, Rdulescu Alexandru

Clasa a XI-a CBoriaru Elena, Grigore Iulia, Rdulescu Alexandru