85940

-Co to jest sieć standardowa?

♦S=<G,ó,{L(u)}> G-digraf acykliczny, <J>-zbiór pusty charakt. ilościowych na wierzch., ♦(L(u)}- zb.char. na gałęziach.

-Co to jest cykl prosty?

♦Jest to cykl, w któiym nie ma powtórzeń wierzchołków.

-Co to jest klika?

♦Każdy zbiór wierzchołków tworzących podgraf pełny.

-Co to jest graf prosty?

*<0,1,0> +p=2

-Co to jest przekrój rozdzielający?

♦Jest to podział sieci na dwa rozłączne kawałki takie, by w jednym z nich

*    znalazło się źródło, a w drugim odpływ.

-Co to jest metoda PERT?

♦Jest to teclinika modyfikacji programów działania- można porównać różne programy ♦(strategie) znajdując najlepszy program bazujący na kryteriach innych niż sieci krytyczne. -Co to jest “zbiór niezależnych oczek dopuszczałnych”?

♦Jest to przydział.

-Co określa stopień wewnętrzny grafu?

♦ilość łuków wchodzących do wierzchołka grafu S+(x).

-Czy graf Hertza może być grafem zwykłym?

♦Nie może, bo graf Hertza to graf skierowany, a graf zwykły może zawierać

♦    tylko pojedyńcze krawędzie między wierzchołkami <1,0,0>.

-Czy sieć PERT może być cykliczna?

♦Nie, bo z definicji jest zbudowana na digrafie acyklicznym.

-Czy każdy graf posiada graf Hertza?

♦Tak (można go zawsze zbudować).

-Czym różni się rozwidlenie od stopnia wierzchołka?

♦Rozwidlenie może być różne od stopnia wierzchołka jedynie, gdy istnieją pęde-♦w przypadku stopnia pęde liczą się pojedyńczo, a w przypadku rozwidlenia podwójnie. ♦a)stopień=liczba łuków wych.+wch.+liczba krawędzi + liczba pętli.

♦b)rozwidłenie=liczba łuków wych.+wch.+liczba krawędzi+2*liczba pętli

-Czym różni się graf od swego szkieletu?

♦szk.grafu: bierzemy wszystkie wierzchołki i tam gdzie w grafie pierwotnym były ♦jakiekolwiek połączenia łączymy tylko jedną gałęzią. Jest uproszczeniem danego grafa ♦W przypadku szczególnym szkielet i graf mogą być identyczne.

-Czym różni się graf dopełnieniowy od dopełnienia grafu?

♦To samo. Graf dopełnieniowy = graf pełny.

-Czym różni się łańcuch Hamiltona od łańcucha Eulera?

♦W łańcuchu Eul przez każdą z gałęzi przechodzimy 1 raz,

♦a w łańcuchu Ham. 1 raz przez wierzchołki.

-Czym różni się graf od sieci?

♦graf to uporządkowany zbiór gałęzi, a sieć to trójka:

♦graf +zbiór charakt. na wierzchołkach+ zbiór charakt. na gałęziach.

-Czemu równa jest liczba cyklomatyczna w grafie acyklicznym?

♦Zeru (nie ma łańcuchów cyklicznych).

-Podaj definicję sieci standardowej dla drzewa ekonomicznego?

♦S=<G,ó,{L(u)}> G-digraf acykliczny, ó-zbiór pusty charakt. ilościowych na wierzch.