85930

-Zdefiniuj optymalne pokolorowanie grafu?

•wyznaczyć bazy minimalne i maks podgrafy puste i wtedy jednym kolorem •pomalować niesąsiad. wierzch.

-Zdefiniuj drogę Hamiltona w grafie?

•jest to taka droga, która przechodzi przez wszystkie wierzchołki dokładnie 1 raz.

-Zdefiniuj luz czasowy na ścieżce krytycznej?

•LCi=Ti-ti

-Zdefiniuj graf Koniga?

•graf zwykły o liczbie podz.=2 <l,0,0>+p=2 -Zdefiniuj sieć standardową dla przepływów?

•S=<G,{a(x)},{c(x,y)}>

-Zdefiniuj gęstość grafu?

•    (D=l W| =max -Zdefiniuj sieć CPM?

*S=<G,<l>,Ti,j> G-digraf acykliczny, ti,j - czas wykonania czynności (i,j). -Zdefiniuj przepływ zaspokajający?

•Dobudowywujemy sztuczne luki a przepływ jest zaspokajający,

•    gdy sa nasycone sztuczne luki na odpływach.

-Wymień metody suboptymalnego kolorowania grafu?

*I)metoda redukcji grafu (Burlage) IIjmetody macierzy podobieństw (Wood)

-W jaki sposób definiujemy rozwidlenie wierzchołka?

*r(x)=S+(x) + S-(x) + S~(x) + 2S'(x)

•r(x)=S(x)+S'(x) -Jak nazywamy liczbę podgrafów spójnych grafu?

•liczbą składowych spójności.

-Jak nazywa się liczba wierzchołków bazy minimalnej grafu?

•liczba bazowa.

-Jak nazywamy skojarzenie grafu Koniga?

•przydział.

-Jak określamy stopień grafu?

*maxS(x)xeG =S(G)

-Jak nazywamy liczbę wierzchołków w najliczniejszym podgrafie pełnym? •gęstością grafu (0=1 Wl =max

-Jaka jest krotność grafu Koniga?

*k=l.

-Jaka jest krotność unigrafu?

•k=l.

-Jakie grafy są opisywane w sposób ścisły przez binarną macierz incyd...w? •grafy krotności co najwyżej 1, czyli <1,1,1>.

-Jakie znasz rodzaje gałęzi grafu?

•gałąź skierowana (luk), gałąź nieskierowana (gałąź), pętla.

-Jaki zbiór tworzą wierzchołki podgrafu pustego?

•zbiór wewnętrznie stabilny.