-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 +p=2
-Zdefiniuj sieć standardową dla przepływów?
*S=
-Zdefiniuj gęstość grafu?
* ω=W=max
-Zdefiniuj sieć CPM?
*S= G-digraf acykliczny, τi,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?
*maxS(x) x∈G =S(G)
-Jak nazywamy liczbę wierzchołków w najliczniejszym podgrafie pełnym?
*gęstością grafu ω=W=max
-Jaka jest krotność grafu Koniga?
*k=1.
-Jaka jest krotność unigrafu?
*k=1.
-Jakie grafy są opisywane w sposób ścisły przez binarną macierz incyd...w?
*grafy krotności co najwyżej 1, czyli .
-Jakie znasz rodzaje gałęzi grafu?
*gałąź skierowana (łuk), gałąź nieskierowana (gałąź), pętla.
-Jaki zbiór tworzą wierzchołki podgrafu pustego?
*zbiór wewnętrznie stabilny.
... zobacz całą notatkę
Komentarze użytkowników (0)