14 co to jest graf?

Grafem nazywamy trójkę uporządkowaną G<W,U,Q> w której W jest zbiorem wierzchołków grafu, U zbiorem jego gałęzi a Q jest relacją trójczłonową Q <WxUxW spełniającą warunki:

Dla każdej gałęzi u єU istnieje taka para wierzchołków x,y є W , że <x,u,y>є Q

Jeśli dla pewnej gałęzi uєU istnieją <x,u,y>єQ oraz <v,u,z> єQ to albo x=v i y=z lub x=z i y=v.

15 co to jest sieć? (+)

Siecią nazywamy trójkę uporządkowaną : S= <G,{δ_i},{Ψ_j}>

Przy czym : G=<W,U,Q> -dowolny graf

{ δ_i } –Zbiór funkcji δ_i : W→R określonych na zbiorze wierzchołków grafu

{ Ψ_j }- zbiór funkcji Ψ_j : U→R określonych na zbiorze gałęzi grafu

Jeżeli oba zbiory funkcji są puste to sieć staje się grafem

16 czym różni się sieć od grafu?

Siec jest pojęciem szerszym. Stanowi ja graf oraz funkcje określone na zbiorze wierzchołków grafu i na zbiorze krawędzi grafu.

17 kiedy sieć stanie się grafem?

Jeżeli oba zbiory funkcji (określonych na zbiorze wierzchołków i na zbiorze krawędzi garfu) są puste to sieć staje się grafem( pyt.15)

18 wymień rodzaje gałęzi w grafie. (+)

Krawędzie , łuki , pętle

19 Co to jest łuk w grafie? (+)

Strzałka łącząca odpowiednie wierzchołki

20 Co to jest pętla w grafie? (+)

Linia zamknięta wychodząca i wchodząca do tego samego wierzchołka

21 Co to jest krawędź w grafie? (+)

Linia łącząca odpowiednie wierzchołki

22 Kiedy dwa wierzchołki są przyległe? (+)

Wierzchołki są przyległe gdy istnieje przynajmniej jedna gałąź incydentna jednocześnie z obu tymi wierzchołkami.

23 Kiedy dwie gałęzie są przyległe? (+)

Dwie gałęzie są przyległe jeżeli istnieje przynajmniej jeden wierzchołek incydentny jednocześnie z obu tymi gałęziami.

24 co to znaczy, że wierzchołek i gałąź są incydentne? (+)

Mówimy że wierzchołek xєW i gałąź uєU są incydentne , jeśli istnieje wierzchołek yєW taki , że <x,u,y>єQ lub <y,u,x>єQ.

25 co to jest macierz przyległości wierzchołków grafu?

Jest to macierz symetryczna, której elementy określają liczbę gałęzi łączących odpowiednie pary wierzchołków grafu. (( R=[r_ij] i,j=1,2,..n) chyba niepotrzebne)

26 co to jest macierz przejść grafu?

Macierz której elementy określają liczbę łuków łączących wierzchołek i z j. (P=[p_ij] (i,j=1,2..n) niepotrzebne?)

27 o czym informuje binarna macierz przejść grafu?O możliwości lub braku możliwości przejścia pomiędzy wierzchołkami

28 o czym informuje binarna macierz przyległości grafuO przyległości lub braku przyległości danych wierzchołków grafu (jest symetryczna)

29 co to jest stopień stopień wierzchołka grafu? (+)

s(x)=s^̃(x)+s⁺(x)+s^-(x)+s⁰(x) (krawędzie + łuki wychodzące + łuki wchodzące + pętle) jest to suma wszystkich gałęzi incydentnych

30 co to jest rozwidlenie wierzchołka grafu?

r(x)=s^̃(x)+s⁺(x)+s^-(x)+2s⁰(x) gdzie: s^̃(x)-suma krawędzi ; s⁺(x)-suma łuków wychodzących; s^-(x)-suma łuków wchodzących ; 2s⁰(x)-suma pętli liczona podwójnie.

31 czym różni się rozwidlenie wierzchołka od jego stopnia?

Rozwidlenie wierzchołka jest to stopień wierzchołka powiększony o liczbę pętli.

32 Dla których wierzchołków stopień i rozwidlenie wierzchołków są równe?

Dla wierzchołków na których nie ma pętli.

33 Dla których wierzchołów stopień i rozwidlenie wierzchołków są różne?

Jeżeli na danym wierzchołku znajdują się pętle.

(czy można powiedzieć,że na wierzchołku znajduja się petle???)

34 Co to jest graf skierowany? (+)

Jest to graf który posiada tylko łuki i pętle

35.        Jakich gałęzi nie posiada graf skierowany?

Nie posiada krawędzi.

36.        Co to jest graf niezorientowany?

Graf posiadający tylko krawędzie i pętle.

37.        Jakich gałęzi nie posiada graf niezorientowany?

Nie posiada łuków.

38.        Co to jest graf pusty?

Jest to graf, który nie posiada żadnych gałęzi - pętli, krawędzi ani łuków.

39.        Jakich gałęzi nie posiada graf pusty?

Nie posiada pętli, krawędzi ani łuków.

40.        Jaka jest krotność unigrafu?

Jego krotność wynosi jeden.

41.        Jaka jest krotność multigrafu?

Jego krotność jest większa od jedności.

42.        Co to jest graf zwykły? (+)

Jest to unigraf niezorientowany bez pętli (tylko po jednej krawędzi dla każdej pary różnych wierzchołków).

43.        Co to jest graf Berge’a? (+)

Jest to digraf (graf skierowany) i unigraf.

44.        Co to jest podgraf? (+)

Wybrana część wierzchołków grafu i wszystkie gałęzie incydentne z nimi.

45.        Co to jest graf częściowy?

Wszystkie wierzchołki grafu i wybrana część gałęzi incydentnych z nimi.

46.        Co to jest podgraf pusty? (+)

Każdy taki podgraf, który jest grafem pustym.

47.        Co to jest maksymalny podgraf pusty? (+)

Taki podgraf pusty grafu, że zbiór jego wierzchołków nie jest podzbiorem właściwym żadnego innego zbioru wierzchołków tworzącego podgraf pusty.

48.        Wymień etapy metody wyznaczania optymalnego kolorowania wierzchołków grafu. (+)

Maksymalne podgrafy puste, pokrycie minimalne, dobór kolorów (?)

49.        Zdefiniuj problem pokryć minimalnych zbioru.Znalezienie najmniejszej liczby podzbiorów danego zbioru tworzących cały ten zbiór.

50.        Co to jest suboptymalne kolorowanie wierzchołków grafu. 

Jest to takie pokolorowanie grafu, aby zużyć jak najmniejszą liczbę kolorów i aby wierzchołki przyległe nie posiadały tego samego koloru. Daje rozwiązanie niewiele gorsze od optymalnego.

51.        Wymień metody suboptymalnego kolorowania wierzchołków grafu. (+)

Metoda redukcji wierzchołków grafu, metoda minimalnego stopnia wierzchołka

52.        Zdefiniuj problem kolorowania wierzchołków grafu. (+)

Problem decyzyjny polegający na określeniu w jaki sposób należy przyporządkować kolory wszystkim wierzchołkom grafu, aby zużyć jak najmniejszą liczbę barw i aby żadne dwa przyległe wierzchołki nie miały tego samego koloru.

53.        Podaj przykład zastosowania metody kolorowania wierzchołków grafu. (+)

Problem magazynowania materiałów chemicznych. Chcąc zaprojektować magazyn materiałów chemicznych należy uwzględnić, że niektóre z tych materiałów reagują ze sobą na tyle silnie, że nie mogą być przechowywane razem w jednym pomieszczeniu. Koszt budowy i eksploatacji magazynu rośnie wraz z liczbą pomieszczeń. Dla danego asortymentu materiałów chemicznych zaprojektować magazyn o minimalnej (najmniejszej) lecz wystarczającej liczbie pomieszczeń.

54.        Co to jest marszruta w grafie?

Dowolny ciąg przemienny wierzchołków i gałęzi (nie ma ograniczeń).

Dowolny sposób poruszania się po grafie

55.        Co to jest łańcuch w grafie? (+)

Ł(x^p, x^k) Marszruta łącząca wierzchołek początkowy x^p z wierzchołkiem końcowym x^k, w której wszystkie gałęzie są różne (nie można 2x przemieszczać się po tej samej gałęzi).

56.        Podaj definicję drogi w grafie?

Droga µ jest to łańcuch skierowany, tzn. marszruta skierowana o różnych gałęziach.

Poruszamy się zgodnie ze skierowaniami.

57.        Podaj definicję drogi prostej w grafie?

Łańcuch skierowany, w którym nie powtarzają się wierzchołki.

58.        Podaj definicję drogi cyklicznej prostej w grafie?

Łańcuch skierowany, w którym powtarzają się wierzchołki.

Droga cyklicznie prosta jest to droga, w której jedynie x^p = x^k a poza tym wszystkie wierzchołki i gałęzie są różne.(?)

59.        Podaj definicję łańcucha prostego w grafie? (+)

Łańcuchem prostym nazywamy łańcuch o różnych wierzchołkach.

60.        Podaj definicję łańcucha cyklicznego prostego w grafie?

Łańcuchem cyklicznie prostym nazywamy taki łańcuch (cykl), w którym jedynie x^p = x^k a poza tym wszystkie wierzchołki i gałęzie są różne.

61.        Jaką marszrutą jest droga cykliczna?

Marszrutą cykliczną (skierowaną).

62.        Jakim łańcuchem jest droga prosta?

Łańcuchem prostym (skierowanym).

63.        Co to jest łańcuch najkrótszy?

Ł_min (x^p, x^k) łańcuch zawierający najmniejszą liczbę gałęzi spośród wszystkich łańcuchów łączących x^p z x^k.

64.        Podaj zastosowanie algorytmu znajdowania łańcucha najkrótszego?

Znalezienie najkrótszej drogi z punktu A do punktu B. ??

65.        Kiedy graf jest spójny?

Kiedy ma jedną składową spójności.

66.        Co to jest składowa spójności grafu? (+)

Składową spójności grafu jest każdy maksymalny podgraf będący grafem spójnym.

67.        Co to jest składowa silnej spójności grafu? (+)

Składową silnej spójności nazywamy każdy maksymalny podgraf będący grafem silnie spójnym.

68.        Co oznacza, że graf posiada trzy składowe spójności ?

Oznacza to, że graf posiada trzy podgrafy będące grafami spójnymi.

69.        Co to jest łańcuch Eulera? (+)

Łańcuch zawierający wszystkie gałęzie grafu i każda z nich pojawia się tylko jeden raz.

70.        Co to jest droga Hamiltona? (+)

Droga zawierająca wszystkie wierzchołki grafu i każdy z nich pojawia się tylko raz.

71.        Jaka jest różnica pomiędzy drogą Eulera a drogą Hamiltona. (+)

W drodze Eulera przez każdą krawędź przechodzi się tylko jeden raz, zaś w drodze Hamiltona przez każdy wierzchołek przechodzi się tylko jeden raz (oprócz wierzchołka pierwszego).

72.        Podaj warunki istnienia łańcucha Eulera. (+)

Dowolny graf zawiera łańcuch Eulera wtedy i tylko wtedy, gdy jest spójny (z wyjątkiem wierzchołków gołych) i gdy liczba wierzchołków o nieparzystych rozwidleniach w tym grafie jest równa 0 lub 2.

73.        Podaj warunki istnienia drogi Eulera. (+)

W digrafie istnieje droga cykliczna Eulera wtedy i tylko wtedy, gdy dla każdego wierzchołka x grafu spełniona jest równość: s⁺(x) = s^-(x) (tyle samo łuków wchodzi co wychodzi).

Jeżeli istnieją tylko dwa takie wierzchołki x_o i y_o że s⁺(x_o) – s^-(x_o) = 1 i s⁺(x_o) – s^-(x_o) = -1, to istnieje droga Eulera o początku w x_o i końcu w y_o (do jednego wierzchołka wchodzi o jeden więcej łuków niż wychodzi, zaś z drugiego o jeden więcej wychodzi niż wchodzi).

74.        Kiedy w grafie istnieje cykliczny łańcuch Eulera?

Dowolny graf zawiera cykliczny łańcuch Eulera wtedy i tylko wtedy, gdy jest spójny (z wyjątkiem wierzchołków gołych) i gdy liczba wierzchołków o nieparzystych rozwidleniach w tym grafie jest równa 0.

75.        Kiedy w grafie istnieje cykliczna droga Eulera?

W digrafie istnieje droga cykliczna Eulera wtedy i tylko wtedy, gdy dla każdego wierzchołka x grafu spełniona jest równość: s⁺(x) = s^-(x) (tyle samo łuków wchodzi co wychodzi).

76.    Kiedy graf skierowany jest cykliczny w sensie dróg?

Graf skierowany (digraf) jest cykliczny w sensie dróg, kiedy zawiera drogi cykliczne.

77.    Kiedy graf skierowany jest acykliczny w sensie dróg?

Graf skierowany (digraf) jest acykliczny w sensie dróg, kiedy nie zawiera dróg cyklicznych.

78.    Jakie warunki spełniają wierzchołki warstwy grafu?

Do warstwy zerowej należą takie wierzchołki x digrafu dla których zbiór poprzedników jest pusty.

Każdy wierzchołek należący do warstwy W_k(k>0)ma poprzedniki tylko w warstwach od 0 do k-1.

Każdy wierzchołek, który ma poprzedniki i jest w k-tej warstwie, musi mieć przynajmniej jeden ze swoich poprzedników w warstwie bezpośrednio poprzedzającej.

79.    Dla jakich grafów można wyznaczyć jego warstwy?

Graf skierowany(digraf)

80.   Jaki podgraf tworzą wierzchołki warstwy grafu?

Maksymalny podgraf pusty ?????????????

81.    Do czego służy algorytm Leifmana? (+)

Algorytm ten służy do wyznaczania wszystkich składowych silnej spójności.

86.    Co to jest karkas grafu? (+)

Karkas jest nośnikiem informacji o spójności wierzchołków grafu. Jest nim dowolny graf

częściowy spełniający dowolne dwa z podanych trzech warunków:

m(T)=m(G)-λ(G),

œ (T)= œ (G),

λ(T)=0

87.    Co to jest najtańszy karkas grafu?

Jest to taki karkas T = <W, U’, Q’> grafu G, gdzie suma Σ k(u) dla u ϵ U’ ma wartość minimalną.

88.    Podaj przykład zastosowania algorytmu wyznaczania drzewa ekonomicznego.

Budowa sieci dróg łączących miasta, budowa sieci połączeń między komputerami.

89.    Wymień znane ci algorytmy wyznaczania najtańszego karkasu grafu. (+)

Algorytm Prima, algorytm Kruskala

90.    Co to jest długość drogi łączącej wybrane wierzchołki w grafie?Ilość gałęzi wchodzących w skład tej drogi

91.    Co to jest maksymalny dendryt dróg najkrótszych w grafie?Spójny digraf i unigraf bez pętli, mający jeden wierzchołek zwany początkiem dendrytu (bez poprzedników) i pozostałe wierzchołki mające po jednym następniku. Drogi od początku dendrytu do poszczególnych wierzchołków są drogami najkrótszymi.

92.    Co to jest maksymalny dendryt dróg najdłuższych w grafie?Spójny digraf i unigraf bez pętli, mający jeden wierzchołek zwany początkiem dendrytu (bez poprzedników) i pozostałe wierzchołki mające po jednym następniku. Drogi od początku dendrytu do poszczególnych wierzchołków są drogami najdłuższymi.

93.    Co decyduje o wyborze algorytmu wyznaczania dróg ekstremalnych w sieciach?

wyborze algorytmu decyduje to czy siec jest cykliczna czy acykliczna.

94.    Wymień etapy algorytmu wyznaczania dróg ekstremalnych w sieciach acyklicznych

-stwierdzenie acykliczności sieci (np. stosując algorytm Leifmana),

-przedstawienie digrafu w postaci warstwowej

-met programowania dynamicznego wyznaczenie wartości zmiennych decyzyjnych optymalizujących długość dróg

-zgodnie z zasadą Bellmana wyznaczenie dróg ekstremalnych

95.    W jakich sieciach możemy stosować metodę dekompozycji przy wyznaczaniu dróg

ekstremalnych w sieciach?W sieciach zawierających łuki i krawędzie.

96.    Jakim grafem powinna być opisana sieć czynnościowa w metodzie CPM/PERT.

Powinna być grafem skierowanym, acyklicznym w sensie dróg, unigrafem.

97.    Co reprezentuje łuk w metodzie CPM/PERT?

Łuk reprezentuje kierunek przebiegu czynności.

98.    Czy w metodzie CPM/PERT sieć czynnościowa może być cykliczna?

Nie

99.    Czym jest ścieżka krytyczna w metodzie CPM/PERT?

Ścieżka krytyczna będąca najdłuższą sekwencją czynności niezbędnych do wykonania procesu technologicznego , wyznacza jednocześnie najkrótszy czas realizacji procesu.

100.    Jak wyznaczamy najwcześniejszy możliwy czas realizacji przedsięwzięcia w metodzie CPM/PERT?

Szukamy ścieżki krytycznej.

101.    Co to jest luz czasowy w sieci czynnościowej?

Jest to zapas czasu dla poszczególnych zdarzeń.

102.    Ile wynosi luz czasowy na ścieżce krytycznej w metodzie CPM?

Wynosi 0.

103.    Jakie zapasy czasu wyznacza się w metodzie analizy czynnościowej?

-zapas całkowity

-zapas swobodny

-zapas niezależny

104.    Co to jest przepływ w sieci?

Przepływem w sieci S nazywamy dowolną funkcję f: U→R spełniającą następujące warunki:

Dla każdej gałęzi przepływ jest większy równy zero, ale nie większy od przepustowości.

Dla pośrednich wierzchołków różnica sumy przepływu towaru wypływającego z wierzchołka i sumy przepływu towaru wpływającego do wierzchołka musi być równa zero.

105.    Co to jest przepływ zaspokajający w sieci?

Przepływ towarów pomiędzy „magazynami” a „odbiorcami”, który zaspokaja ich zapotrzebowania.

106.    Co to jest przepływ zaspokajający o minimalnym koszcie w sieci?

Przepływ towarów pomiędzy „magazynami” a „odbiorcami”, który zaspokaja ich zapotrzebowania i dodatkowo zapewnia minimalizację kosztów transportu..

107.    Co to jest wartość przepływu w sieci?

Wartością przepływu f nazywamy wielkość v(f), która jest określana następująco:

v(f) = Σ_yϵГs f(s,y) – Σ_zϵГs^-1 f(z,s)

108.    Czemu jest równa wartość przepływu maksymalnego w sieci?

Sumie przepustowości gałęzi skierowanych od W₁ do W₂ przechodzących przez minimalny przekrój rozdzielający

109.    Podaj warunki definiujące przepływ w sieci.

Dla każdej gałęzi przepływ jest większy równy zero, ale nie większy od przepustowości.

Dla pośrednich wierzchołków różnica sumy przepływu towaru wypływającego z wierzchołka i sumy przepływu towaru wpływającego do wierzchołka musi być równa zero.

110.    Co to jest ścieżka powiększalna w algorytmie wyznaczania przepływu maksymalnego w sieci?

Droga, na której można zwiększyć przepływ, o tyle jednostek, ile wynosi aktualna (z tego etapu cechowania) druga cecha odpływu.

111.    Kiedy przepływ maksymalny w sieci jest przepływem zaspokajającym?

Gdy łuki łączące źródło z magazynami i odbiorców z odpływem są nasycone. (w sieci poszerzonej)