Exemplu de subiect AG 3


1. Sa se det numarul cromatic al grafului desenat mai jos (argumentare). ( un graf complet cu 10 noduri era – cred.)

2. T – un arbore reprezentat cu ajutprul tabloului (p[v]) unde p[v] este parintele lui v in T: varfului dinaintea lui v de pe drumul unic de la o radacina fixata? r la v in T …. ??. descrieti un alg care sa construiasca in timp 0(n) listele de adiacenta ale lui T

3. dem ca daca M este un cuplaj maxim in raport cu incluziunea intr un graf G, at multimea e(m) a varfurilor expuse relativ la cuplajul m este o multime stabila in graful g.

4. dem ca orice graf bipartit cu toate varfurie de acelasi grad k>0 are un graf partial cu toate varfurile de grad k-1.

5. fie urm prob de decizie

P:
instanta : g graf
intrebare : are g o unica multime stabila de cardinal maxim ?

dem ca daca exista un algoritm polinomial pt rezolvarea lui p atunci se poate determina in timp polinomial numarul de stabilitate al oricarui graf.

multumim Irinei si Simonei [5B]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: