Zestaw II

2. Graf poniżej jest modelem pewnego obiektu rzeczywistego. Ile wynosi odległość drogi maksymalnej w tym grafie?

a)6

b)3

c)4

d)5

3.Który ze zbioru wierzchołków jest maksymalnym zbiorem wewnętrznie stabilnym grafu z zad 2?

a)1,3

b)3,4,7

c)1,5

d)1,3,5

4. Dla jednoznacznej reprezentacji macierzowej grafu Berge'a wystarczy użyć:

a)binarną macierzy przejść

b)binarną macierz przyległości wierzchołków

c)binarną macierz przyległości gałęzi

d)macierz przyległości wierzchołków

5. Przekształcamy graf z zad 2 w układzie warstwowym. Które wierzchołki należą do warstwy o numerze 2?:

a)2,4

b)5

c)3

d)6

6. Załóżmy, że sieć z zad 2 jest siecią przepływową, a wartości przepustowości wszystkich łuków są równe 1. Koszty wszystkich łuków są równe 1. Ile wynosi wartość minimalnego kosztu zaspokajającego przepływ równy 2 z wierzchołka 1 do 6.

a) 4

b)5

c)6

d)7

7.Optymalna liczba kolorów, którą można pokolorować gałęzie grafu z zad 1 (nie bierzemy pod uwagę klienta pierwszego od góry) wynosi:

a) 2

b) 3

c) 4

d)5

8. droga prosta w grafie spełnia następujący warunek

a) zawiera wszystkie gałęzie grafu

b) zawiera niektóre wierzchołki i niektóre gałęzie grafu

c) zawiera niepowtarzające się gałęzie i wierzchołki

d) zawiera wszystkie wierzchołki i wszystkie gałęzie grafu.

9. Załóżmy że sieć z zad 2 jest siecią przepływową a wartości przepustowości wszystkich łuków SA równe 1. Który z zestawów wartości przepływów łukowych spełnia własności przepływu z wierzchołka 1 do 7?

a) A-1 B-1, pozostałe zero

b) A-1, C-1, D-1, pozostałe zero

c)B=1, E=1, G=1, H=1 pozstałe0

d) A=1, C=1, f=1, H=1, pozostałe 0

10. Maksymalny stopień wierzchołka w grafie z zad 2 wynosi

a) 3

b) 4

c)1

d)2

11. algorytm Bellmana służy do poszukiwania dróg ekstremalnych w sieciach

a) dowolnych

b) acyklicznych

c)w których koszty łukowe są nieujemne

d) acyklicznych z nieujemnymi kosztami łukowymi

12. Maksymalne skojarzenie najliczniejsze w grafie z zad 1 ma wartość:

a) 1

b) 2

c)3

d)4

13. Składowa spójności grafu to:

a) część grafu, która składa się z wszystkich wierzchołków i niektórych gałęzi

b) maksymalny podzbiór gałęzi przyległych do siebie

c) maksymalny podzbiór wierzchołków przyległych do siebie

d) maksymalny podgraf spójny

14. stopień grafu z zad1 wynosi

a) 1

b)2

c)3

d)4

15. Dla grafu z zad 2 niech koszty łukowe będą równe 1. Wartość kosztu najtańszego Karkasu wynosi

a) 6

b)4

c)3

d)5

16. Graf zwykły to graf

a)bez krawędzi

b)bez łuków

c. bez wierzchołków i gałęzi

d) bez pętli

Syriusz ©