Badania operacyjne - ćwiczenia - graf

-Podaj definicję grafu Berge'a?
*digraf unigraf (tylko łuki i pętle)
-Podaj definicję drogi w grafie?
*Taki łańcuch, w którym przez wszystki łuki idziemy zgodnie z ich skierowaniem.
-Podaj definicję krotności grafu?
*max(V,Ξ,Φ)=K(G)
-Podaj definicję łańcucha prostego?
*Jest to łańcuch ,w którym nie ma powtórzeń wierzchołków.
-Podaj definicję liczby skojarzeniowej grafu?
*Jest to liczba podgrafów częściowych o nieprzyległych gałęziach *(bez wierzch. izolowanych); ozn: Pi(G).
-Podaj definicję sieci?
*sieć jest to trójka S= G-graf, φi-zbiór charakt. ilościowych na wierzch. *ξij-zbiór charakt. ilościowych na gałęziach. -Podaj definicję podgrafu?
*G'= W'⊂W + U'⊂U
-Podaj twierdzenie Forda-Fulkersona?
*wartość przepływu maksymalnego w sieci skierowanej jest równa * przepustowości minimalnego przekroju : Vmax=C(Pmin).
-Podaj oba warunki definicyjne przepływu?
*∑y∈Γ(x) f(x,y)- ∑y∈Γ-1(x) f(z,x)= ax*v(t).
-Podaj własności grafu pełnego?
*posiada max ilość dopuszczalnych gałęzi- nie można dopisać np. krawędzi.
-Podaj cechy łańcucha prostego maksymalnego?
*nie ma powtórzeń wierzchołków i jest najdłuższy z możliwych.
-Podaj inną nazwę najtańszego karkasu grafu sieci?
*drzewo ekonomiczne
-Podaj kryterium algorytmu wyznaczania przedziału typu “wąskie gardło”?
*max(min(wyd(i,j)))
-Podaj warunki istnienia łańcucha Eulera w grafie?
*Istnieje, jeśli liczba wierzchołków o nieparzystym rozwidleniu=0 lub 2
-Zdefiniuj maksymalną składową spójności?
*maksymalny podgraf spójny.
-Zdefiniuj wierzchołek wiszący w grafie?
*2S(X)-r(x)=1
-Zdefiniuj graf częściowy?
... zobacz całą notatkę