Exemplu de subiect AG 4


1. iti da un graf..si te pe pune sa ii spui numarul de conexitate si argumentare
2
da un graf, adica V si lista de muchii si tu trebuie sa faci un algorim care sa generezee lista de adiacenta a unui subgraf poiectat de o multime A( [A]g)
3.
demonstrezi printr-un contraexemplu ca dijkstra nu e bun pentru grafuri cu muchii de cost minim
4.
asta nu mai tin minte…ca nu am facut…ceva ca daca se deduce in timp polnomial drumul de cost minimi atunci graful are….nu mai tin minte..srry

5. pentru n>=2 se sa demonstreze ca este un graf de ordin 2n 3-regulat

la 2 ne-a dat un graf ciclic cu costuri si sa aflam arborele de cost minim
la 3 ne-a dat sa dem pt un arbore conex ca k(g)>
Andrei:
la 4 ne-a spus sa spunem cate drumuri se afla intr-un arbore
la 1 ne-a dat un graf si sa spunem multimea de stabilitate pt acel graf

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: