85941

-Jakich gałęzi nie posiada digraf?

♦gałęzi nieskierowanej.

-Jakim zbiorem jest zbiór wierzchołków warstwy di grafu?

♦tworzą one pocłgraf pusty- nie może być między nimi połączenia.

-Jaką gałąź w grafie nazywamy krawędzią?

*    gałąź nie skierowana.

-Kiedy graf można przedstawić warstwowo?

♦o wszystkie maxSSS są jednowierzchołkowe <=>

♦graf jest acykliczny w sensie dróg.

-Kiedy graf jest nieskierowany?

*    kiedy nie posiada łuków.

-Kiedy graf jest spójny?

♦jeśli dla każdej pary wierzchołków istnieje marszruta (dowolne połączenie).

-Kiedy graf jest silnie spójny?

♦jeśli dla każdych 2 wierzchołków istnieje droga łącząca te wierzchołki.

-Kiedy sieć jest grafem?

♦kiedy zbiory charakterystyk na gałęziach i na wierzchołkach są zbiorami pustymi. -Kiedy liczba podzielności jest równa liczbie chromatycznej grafu?

♦jeśli graf nie ma pędi.

-Kiedy dwa wierzchołki są przyległe?

♦jeśli są połączone lukiem lub krawędzią.

-O czym mówi liczba cyklomatyczna grafu?

♦o liczbie łańcuchów cyklicznych w grafie ?

-O czym możemy się dowiedzieć znając liczbę chromatyczną grafu?

♦(Y) o min liczbie kolorów użytej do pokolorowania grafu.

-Do czego służy algorytm Leiffmana?

♦a) sprawdza acykliczność grafu b)do wyznaczania max SSS.

-Na jakich grafach można zbudować sieć PERT?

♦Na digrafach acyklicznych.