Question

Va rog mult! Cu explicatii!

1. Un graf orientat cu 6 vârfuri, numerotate de la 1 la 6, este reprezentat prin
matricea de adiacență ale cărei prime 5 linii sunt scrise alăturat. Două drumuri
sunt distincte dacă diferă prin cel puțin un arc traversat. Indicați gradul exterior
maxim al vârfului 6, astfel încât să existe doar trei drumuri elementare cu
extremitatea inițială în vârful 2 și extremitatea finală în vârful 4.

0 0 0 1 0 0
1 0 0 0 1 1
0 0 0 1 0 0
0 0 0 0 0 0
0 0 1 0 0 1
...........

a. 1 b. 2 c. 3 d. 4



2.Un graf orientat cu 5 vârfuri este reprezentat prin matricea de adiacență alăturată.
Indicați numărul de vârfuri ale unui subgraf al acestuia care are un număr maxim de
vârfuri izolate.
0 0 1 0 0
1 0 1 1 0
0 0 0 0 0
0 0 1 0 1
0 0 1 0 0
a. 1 b. 2 c. 3 d. 4

Answer 1

Răspuns:

1.b 2.b

Explicație:

La prima problema trebuie sa il unesti pe notul 6 cu cat mai multe noduri, dar nu trebuie sa formezi noi drumuri, deci el poate fi unit doar (6,2) si (6,4).

Daca il unesti cu 3(spre exemplu) atunci o sa formezi un noi drum 2-6-3-4 si trebuie sa ramana doar 3 drumuri (dar poate fi unit cu 3 daca nu este unit cu 4).

La cea de a doua problema subgrafurile se formeaza prin eliminarea de noduri ale grafului pricipal alaturi de muchii, ai in imagine.

Sper ca am reusit sa te ajut :))