85929

-Co to jest graf?

♦    G=<W,U,P> W-wierzchołki, U-gałęzie, P-relaeje ;PcWxUxW.

♦Wskazuje od którego do którego wierzchołka można przejść.

-Co to jest wierzchołek gdy?

♦brak gałęzi S(x)=0.

-Co to jest zbiór wewnętrznie stabilny?

♦zbiór wierzchołków podgrafu pustego.

-Co to jest składowa spójności grafu?

♦podgraf spójny (dla każdej paiy wierzchołków istnieje marszruta).

-Co to jest wierzchołek izolowany?

♦brak połączeń z resztą grafu (tylko pętle) 2S(x)-r(x)=0 -Co to jest łuk w grafie?

♦gałąź skierowana -Co to jest rodzaj grafu?

♦trójka uporządkowana <V;S;<I» V-max.l.kraw.,<l>-max.l.pętli,E-max.l.łuków.

-Co to jest łańcuch w grafie?

♦przejście przez graf bez powtórzenia gałęzi, niekoniecznie zgodnie

♦    ze skierowaniem łuków.

-Co to jest rząd grafu?

♦Liczba wierzchołków najliczniejszej składowej spójności.

-Co to jest skojarzenie grafu?

♦Podgraf częściowy o nie przyległych gałęziach (bez wierzchołków izolowanych).

-Co to jest liczba podzielności grafu?

♦podzielenie grafu na podzbiory, które będą zawierały wierzchołki nie przylegające.

♦    Najmniejsza liczba tych zbiorów jest liczbą podziel.

-Co to jest liczba stabilności wewnętrznej grafu?

♦a=l W'| =max ilość wierzchołków w max podgrafie pustym.

-Co to jest przepływ?

*f(x,y) spełniająca dwa warunki: a) Oęf(x,y) ęc(x,y) c(x,y)-przepustowość;

*b)£v f(x,y)- Ez f(z,x)= a(x)*v(f) v(f)-przepływ a(x)=-1,0,1.Przepływ ma ♦tę własność, że w wierzchołkach pośrednich nic nie może powstać, ani zginąć.

-Co to jest digraf?

♦graf skierowany (tylko łuki i pętle)

-Co to jest karkas grafu?

♦jest to graf częściowy powstały poprzez usunięcie nadmiarowych gałęzi ♦cyklicznych z grafu.

-Co to jest przydział?

♦a) odpowiednie przydzielenie środków do zadań;

♦b) zbiór nie zależnych oczek dopuszczalnych;

-Co to jest graf zwykły?

♦unigraf nieskierowany bez pętli i łuków <1,0,0> (tylko pojedyncze gałęzie).

-Co to jest marszruta w grafie?

♦jest to dowolne połączenie w grafie między jej punktem początkowym i końcowym.

-Co to jest łańcuch skierowany?

♦droga

-Co to jest ranga grafu?

♦@(G)= m-X=n-X=m(T) X-l.cyklomatyczna grafu, x-l.spójności grafu,

♦m.-l.gałęzi n-Lwierzch. Ranga grafu równa jest liczbie karkasu gałęzi tego grafu.