3582326897

-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-1i

-Zdefiniuj graf Koniga?

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

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

-Zdefiniuj gęstość grafu?

*    (0=1 wj =max -Zdefiniuj sieć CPM?

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

*Dobudowywujemy sztuczne łuki a przepływ jest zaspokajający,

*    gdy sa nasycone sztuczne łuki na odpływach.

-Wymień metody suboptymalnego kolorowania grafu?

*I)metoda redukcji grafu (Burlage) II)metody 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?

*1113x5 (x) xe G =S(G)

-Jak nazywamy liczbę wierzchołków w najliczniejszym podgrafie pełnym?

*    gęstością grafu (0=1 w| =max

-Jaka jest krotność grafu Koniga?

*k=l.

-Jaka jest kromość 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 (łuk), gałąź nieskierawana (gałąź), pętla.

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

*zbiór wewnętrznie stabilny.