Krzysztof Borzęcki
Zadanie 1.
Spójność krawędziowa grafu λ(G) to moc najmniejszego rozcięcia w grafie G, czyli najmniejsza liczba krawędzi których usunięcie rozspaja graf G.
1. Cn - graf cykliczny o n wierzchołkach - λ(G)=2; ponieważ w takim grafie stopień wierzchołka jest zawsze 2, to usunięcie dwóch dowolnych krawędzi powoduje rozspojenie grafu.
2. Wn - graf kołowy to zespolenie grafów Nn i Cn-1 (n≥3) - λ(G)=3; ponieważ w takim grafie każdy wierzchołek na obwodzie koła jest stopnia 3, to aby rozspoić graf należy usunąć wszystkie krawędzie wychodzące z wybranego wierzchołka.
3. Kr,s - graf dwudzielny - λ(G)=r lub λ(G)=s; należy usunąć wszystkie krawędzie wychodzące z wierzchołka o najniższym stopniu.
4. Graf Petersena - λ(G)=3; jest zbliżony do grafu kołowego, wszystkie wierzchołki są stopnia 3, wobec czego należy usunąć wszystkie krawędzie wychodzące z jednego wierzchołka.
5. Qk - graf kubiczny (k-kostka) - λ(G)=3; jest to graf stopnia 3, wobec czego, aby rozspoić ten graf należy usunąć wszystkie krawędzie wychodzące z jednego wierzchołka.
Spójność wierzchołkowa grafu κ(G) to moc najmniejszego zbioru rozdzielającego graf G.
1. Cn - jeżeli n<4 to usunięcie wierzchołka nie rozdziela grafu, tylko zmienia go w graf liniowy, a następnie w graf pusty z jednym wierzchołkiem. κ(G)=2 jeżeli n>=4 - usunięcie dwóch niesąsiadujących ze sobą wierzchołków rozdziela graf.
2. Wn - κ(G)=3; należy usunąć środkowy wierzchołek oraz dwa niesąsiadujące ze sobą wierzchołki.
3. Kr,s - κ(G)=r lub κ(G)=s; należy usunąć wszystkie wierzchołki należące do r lub s (w zależności, która wartość jest niższa).
4. Graf Petersena - κ(G)=3; aby rozdzielić graf należy usunąć wszystkie wierzchołki połączone z wierzchołkiem, który ulegnie oddzieleniu od pozostałej części grafu.
5. Qk - κ(G)=3; tak jak graf Petersena.
Zadanie 7.
Graf orientowalny
Aby określić graf mianem orientowalnego, należy najpierw przedstawić definicję grafu spójnego. Graf spójny to taki graf skierowany, który nie może być przedstawiony w postaci sumy dwóch rozłącznych grafów skierowanych. Graf może być silnie spójny, jeśli jest skierowany i zawiera drogę pomiędzy dwoma dowolnymi wierzchołkami. Oznacza to, że każdy graf silnie spójny jest spójny, ale nie jest to równoważne z twierdzeniem odwrotnym.
Zdefiniowany jak powyżej graf jest grafem orientowalnym, jeśli każda jego krawędź może być uporządkowana w taki sposób, że uzyskany graf skierowany jest silnie spójny. Proces porządkowania krawędzi nosi nazwę „orientowania” lub „skierowywania”.
Pochodną tego twierdzenia jest wniosek, że każdy graf eulerowski jest grafem orientowalnym. Można to łatwo sprawdzić, przechodząc dowolny graf eulerowski i orientując krawędzie zgodnie z kierunkiem ruchu. Wynika z tego też twierdzenie, że graf spójny jest orientowalny wtedy i tylko wtedy, gdy każda krawędź tego grafu jest zawarta w przynajmniej jednym cyklu. Aby to udowodnić należy wyznaczyć w grafie dowolny cykl i go zorientować. Jeśli wszystkie krawędzie zawarły się w tym cyklu to dowód jest zakończony. Jeżeli nie, to należy wybrać dowolną krawędź sąsiadującą z cyklem i zorientować ją zgodnie z ruchem wcześniejszego cyklu, zamykając go. Postępowanie to należy powtarzać do momentu wprowadzenia wszystkich krawędzi do cyklu.
Zadanie 8.
Łańcuch Markowa
Proces Markowa - ciąg zdarzeń, w którym prawdopodobieństwo każdego zdarzenia zależy jedynie od wyniku poprzedniego.
Przykładowo przyjmujemy, że dla badanego dla obiektu możliwe są trzy zdarzenia, które mają różne prawdopodobieństwo wystąpienia (1/2 - ruch w prawo, 1/3 - ruch w lewo, 1/6 - pozostanie w miejscu). Dają sumę 1, gdyż któreś z nich musi zajść w danym momencie.
Stan początkowy E0 to stan w którym znajduje się obiekt w chwili k0. Kolejny stan obiektu zależy od prawdopodobieństwa wystąpienia danego zdarzenia oraz stanu obiektu w czasie k-1. Można ręcznie przeliczać prawdopodobieństwo znalezienia się obiektu w stanie Ek, jednakże przy dużej wartości k jest to problematyczne. Jeśli przestrzeń stanów jest zbiorem skończonym, rozkład prawdopodobieństw przejść między poszczególnymi stanami może być przedstawiony jako macierz, zwaną macierzą prawdopodobieństw przejścia. Jest to macierz kwadratowa, a oznaczamy ją literą P, gdzie elementy p(i, j) oznaczają prawdopodobieństwo przejścia z elementu i do elementu j, czyli element p13 oznacza prawdopodobieństwo przejścia ze stanu pierwszego E1 do stanu trzeciego E3. Jej wielkość zależy od ilości stanów w jakich może znajdować się obiekt, natomiast pozycje Ei nazywane są stanami łańcucha.
Na macierzy można zdefiniować wektor prawdopodobieństwa jako wektor wierszowy o nieujemnych współrzędnych, których suma jest równa jeden. Wobec tego macierz przejść jest macierzą kwadratową, której wiersze są wektorami prawdopodobieństwa.
Skończony łańcuch Markowa to para (P,x), w której P to macierz przejść o wymiarach nxn, a x jest n-wymiarowym wektorem wierszowym.
Łańcuch Markowa, w którym możemy przejść z dowolnego stanu do każdego innego nazywa się łańcuchem nieprzywiedlnym.
Na przestrzeni dyskretnej całkowanie k-tego stopnia macierzy przejścia jest zwykłym sumowaniem i może być obliczane jako k-ta potęga macierzy przejścia. Czyli jeśli P jest macierzą przejścia w jednym kroku, wówczas Pk jest macierzą przejścia w k krokach.