# Grafy

## :small_blue_diamond: Wykład 1 - Wprowadzenie i pojęcia podstawowe

* Graf - uporządkowana para (V,E), gdzie V to zbiór wierzchołków a E to zbiór krawędzi
* Graf zerowy - V i E są puste
* Graf skierowany - to samo co nieskierowany tylko E zawiera uporządkowaną parę wierzchołków ze zbioru V (początek i koniec)
* Graf prosty - bez pętli (v,v) i krawędzi wielokrotnych {(v,w), (v,w)}
* Multigraf - uogólnienie grafu prostego, może posiadać krawędzie wielokrotne
* Stopień wierzchołka - deg(v) - liczba krawędzi incydentnych z wierzchołkiem (w grafach nieprostych, pętla dodaje 2 do stopnia wierzchołka)
* Wierzchołek o stopniu 0 - izolowany
* delta małe - stopień minimalny, delta duże stopień maksymalny
* Graf i-regularny - wszystkie stopnie są równe i
* Graf 3-regularny - graf kubiczny
* Twierdzenie: lemat o uściskach dłoni: suma stopni wierzchołków jest parzysta
* Wniosek: liczba wierzchołków nieparzystego stopnia musi być parzysta
* W skierowanych - stopień wejściowy (indeg(v)) i stopień wyjściowy (outdeg(v))
* Twierdzenie: suma stopni wejściowych jest równa sumie stopni wyjściowych
* Graf izomorficzny - dwa grafy są izomorficzne kiedy istnieje bijekcja f: V1 -> V2 pomiędzy zbiorami wierzchołków V1 i V2 taka że krawędze v i w w grafie G1 są połączone wtedy gdy f(v) i f(w) są połączone w G2. Lub inaczej te grafy są "takie same" z punktu widzenia teorii grafów
* Podgraf grafu - graf H=(V',E') taki że V' jest podzbiorem V i E' jest podzbiorem E
* Podgraf indukowany - to taki że usuwamy podzbiór wierzchołków z grafu G i przylegające do nich krawędzie
* Operacje:
1. Suma, tworzy graf niespójny, te same wierzchołki i krawędzie, traktujemy jak jeden graf
2. Odjęcie krawędzi G-e
3. Odjęcie wierzchołka G-v (uwaga usuwamy też wszystkie krawędzie incydentne)
4. Ściągnięcie krawędzi G\e, usuwamy krawędź i utożsamiamy wierzchołki
5. Dodatnie wierzchołka G+v dodajemy wierzchołek i łączymy go z wszystkimi pozostałymi
6. Dopełnienie grafu G' - tylko te krawędzie których nie ma w G
7. Iloczyn kartezjański grafów G1xG2 = (V1xV2, (V1xE2)U(V2xE1))
* Ważne typy grafów
1. Pusty N_n - same wierzchołki
2. Pełny K_n wszystkie krawędzie między n wierzchołkami - dopełnienie pustego
3. Dwudzielny - zbiór wierzchołków da się podzielić na dwa rozłączne podzbiory, tak że krawędzie występują tylko między podzbiorami, pełny dwudzielny K_m,n - tak jak dwudzielny, tylko wszystkie mozliwe krawędzie między podzbiorami
4. Ścieżkowy P_n
5. Cykliczny C_n
6. Kołowy W_i - cykliczny C_i z dodatkowym wierzchołkiem połączonym ze wszystkimi

7. Hiperkostka Q_i - wierzchołki są reprezentowane przez ciągi binarne długości i, i są sąsiednie tylko gdy różnią się jednym bitem
8. Drabinkowy LD_i (LD_i = Pi x P2) - drabinka o 'i' szczebelkach
* Reprezentacje grafów:
1. Macierz sąsiedztwa
2. Macierz incydencji - wiersze to wierzchołki, a kolumny to krawędzie
3. Lista sąsiedztwa
4. Lista krawędzi
5. Reprezentacja obiektowa - różne rodzaje
* Macierz sąsiedztwa - obserwacje:
* suma w wierszu: stopień (wyjściowy dla skierowanych)
* suma w kolumnie: stopień (wejściowy, dla skierowanych)
* Macierz incydencji - obserwacje:
* dla grafów skierowanych: 1 dla wychodzących z wierzchołka, a -1 dla wchodzących do wierzchołka
* Graf jest rzadki jeśli jego liczba krawędzi jest mała, czyli jest liniową funkcją n, (m= O(n))

Przydatne wzory:

Liczba krawędzi w grafie pełnym = n*(n-1)/2

Liczba krawędzi w grafie pełnym dwudzielnym = n*m
## :small_blue_diamond: Wykład 2 - Drogi i cykle
* Droga(ścieżka) - naprzemięnny ciąg, wierzchołków i krawędzi (v0, e0, v1 ...), taki że krawędź e_k zawsze łączy wierzchołki v_k i v_k+1
* Droga(ścieżka) prosta - nie powtarza krawędzi
* Droga(ścieżka) elementarna - nie powtarza wierzchołków
* Droga długości 0 = pojedyńczy wierzchołek
* Cykl - droga, o długości conajmniej 3, taka że v_0 == v_l
* Cykl prosty i elementarny analogicznie
* Obwód grafu - długość najkrótszego cyklu elementarnego (Q_3 ma obwód 4)
* Graf jest spójny gdy każde dwa różne wierzchołki są połączone drogą
* Składowa spójna - maksymalny podraf grafu, który jest spójny, liczbę składowych oznaczamy przez c(G)
* Graf silnie spójny (dla grafów skierowanych) - dla każdej uporządkowanej pary wierzchołków isnieje droga skierowana z jednego do drugiego
* Składowa silnie spójna - maksymalny podgraf silnie spójny
* Składowa słabo spójna - maksymalny podgraf spójny
* Twierdzenie: Graf jest dwudzielny <=> nie zawiera cykli nieparzystych
* Liczba krawędzi w grafie prostym o n wierzchołkach i k składowych spełnia nierówność n-k <= m <= (n-k)(n-k+1)/2
* Zbiór rozspajający - taki zbiór krawędzi grafu, po usunięciu których graf ma więcej składowych spójnych
* Rozcięcie - minimalny zbiór rozspajający
* Most - jednokrawędziowe rozcięcie
* Spójność krawędziowa (lambda(G)) - liczba krawędzi najmniejszego rozcięcia
* Graf jest k-spójny krawędziowo <=> k <= lambda(G) np (C_4 jest 1-spójny krawędziowo i 2-spójny krawędziowo, ale nie 3-spójny krawędziowo)
* Zbiór rozdzielający - taki podzbiór wierzchołków, po usunięciu których (i incydentnych krawędzi) graf ma więcej składowych spójnych
* Wierzchołek rozdzielający (punkt artykulacji) - jednoelementowy zbiór rozdzielający
* Spójność (wierzchołkowa) (oznaczana k(G) - greckie Kappa) - to liczba elementów najmniejszego zbioru rozdzielającego
* Graf jest k-spójny (wierzchołkowo) <=> k <= K(G) (C_4 jest 1-spójny i 2-spójny, ale nie 3-spójny)
* Blok - maksymalny podgraf grafu, który nie ma punktów artykulacji dla tego podgrafu

Kilka faktów:
1. dwa różne bloki mogą mieć w części wspólnej najwyżej 1 wierzchołek
2. każda krawędź grafu należy dokładnie do jednego bloku
3. wierzchołek jest punktem artykulacyjnym <=> należy do różnych bloków

* Graf blokowy (BL(G)) - wierzchołki oznaczają bloki a krawędzie są wtedy kiedy dwa bloki mają wspólny punkt artykulacyjny (np poniżej by to BL(G) = K_2)

* Odległość w grafie - długość najkrótszej ścieżki łączącej 2 wierzchołki

Pojęcia oparte na odległości:
1. średnica grafu (diam(G)) - maksymalna odległość między wierzchołkami w tym grafie
2. ekscentryczność wierzchołka (ecc(v)) - maksymalna odległość od innego wierzchołka
3. promień grafu (rad(G)) - minimalna ekscentryczność jakiegoś wierzchołka
4. wierzchołek centralny - taki dla którego ecc(v) == rad(G)
5. centrum grafu (Z(G)) - graf indukowany na zbiorze wierzchołków centralnych grafu G - dla drzewa będzie to pojedyńczy wierzchołek albo 2 wierzchołki połączone krawędzią

* Cykl Eulera - taki cykl, który przechodzi dokładnie raz przez wszystkie krawędzie grafu
* Graf Eulera - graf, w którym istnieje cykl Eulera)
* Ścieżka Eulera - ścieżka, która nie powtarza krawędzi i zawiera wszystkie krawędzie grafu
* Graf pół-Eulerowski - taki w którym istnieje ścieżka eulera
* Lemat: jeśli każdy wierzchołek ma stopień przynajmniej 2 to graf zawiera cykl
* Twierdzenie Eulera: graf spójny jest eulerowski <=> każdy jego wierzchołek jest parzystego stopnia
* Graf jest pół-eulerowski <=> zawiera dokładnie 2 wierzchołki nieparzystego stopnia
* Algorytm Fleurego - znajdowanie cyklu Eulera - idz po krawędziach i przechodz przez mosty tylko jeżeli nie masz innej opcji

* Cykl Hamiltona - cykl przechodzący przez każdy wierzchołek dokładnie raz
* Graf Hamiltona - graf zawierający cykl hamiltona
* Graf pół-Hamiltonowski - nie musi się kończyć w tym samym wierzchołku - zawiera ścieżkę hamiltona
* Problem sprawdzenia jest NP-zupełny
* Warunek wystarczający - twierdzenie Ore'go - jeśli G jest grafem prostym o n >= 3 wierzchołki i deg(v) + deg(w) >= n dla każdej pary wierzchołków niesąsiednich v i w to G jest Hamiltonowski
* Twierdzenie Diraca (wniosek z Ore'go) - jeśli G jest prosty i ma n >= 3 wierzchołków i dla każdego v zachodzi deg(v) >= n/2 to graf jest Hamiltonowski
* Graf dwudzielny G = (V_1 U V_2, E) jest hamiltonowski jeśli V_1 i V_2 mają tyle samo elementów
* Graf dwudzielny jest pół-hamiltonowski - liczność V_1 i V_2 różnią się conajwyżej o 1

Liczba cykli Hamiltona:
1. Graf K_n zawiera dokładnie (n-1)!/2 różnych cykli Hamiltona
2. K_n dla n nieparzystego, zawiera dokładnie (n-1)/2 krawędziowo rozłącznych cykli Hamiltona
3. graf Petersena nie zawiera cyklu Hamiltona

## :small_blue_diamond: Wykład 3 - Drzewa
* Drzewo - graf spójny i bez cykli (acykliczny)
* Las - suma drzew lub inaczej graf bez cykli (niekoniecznie spójny)
* Liść - wierzchołek o stopniu 1
* Pozostałe wierzchołki - wewnętrzne

Warunki równoważne:
1. Graf T jest drzewem o n wierzchołkach
2. T ma n-1 krawędzi i jest acykliczny
3. T jest spójny i ma n-1 krawędzi
4. T jest spójny i każda krawędź jest mostem
5. każde dwa wierzhcołki T są połączone dokładnie jedną drogą elementarną
6. T jest acykliczny, ale po dodaniu jakiejkolwiek krawędzi powstaje dokładnie jeden nowy cykl

Inne własności:
1. Las o k składowych ma n-k krawędzi
2. W drzewie o conajmniej 3 wierzchołkach, jeśli v jest centralny to deg(v) >= 2
3. Centrum drzewa to albo 1 wierzchołek albo graf K_2 (P_2)

* Indeks Wienera (ds(G)) - suma wszystkich odległości między parami wierzchołków grafu
* Indeks Wienera osiąga wartość minimalną dla grafu będącego gwiazdą K_{1,n-1} = (n-1)^2, a wartośc maksymalną dla grafu ścieżkowego P_n

* Ciąg liczb dodatnich naturalny jest drzewowy jeśli pewna jego permutacja stanowi ciąg stopni pewnego drzewa
* Twierdzenie: Jeśli T jest drzewem o n wierzchołkach i G jest prostym grafem o minimalnym stopniu wierzchołka >= n-1 to T jest izomorficzne z pewnym podgrafem G

* Drzewo etykietowane - każdemu wierzchołkowi przypisujemy etykiety będące kolejnymi dodatnimi liczbami naturalnymi

* Kodowanie Prufera - pozwala w jednoznaczny sposób zakodować dowolne drzewo etykietowane o n wierzchołkach za pomocą (n-2) elementowego ciągu liczb z zakresu [1,n]
* Algorytm kodowania: Bierzemy liść b1 z najmniejszą liczba przypisaną jako etykieta i zapisujemy jego sąsiada (jedynego) jako a1, następnie usuwamy b1 z drzewa, potem bierzemy kolejny liść z najmniejszą etykietą b2 i zapisujemy jego sąsiada jako a2, usuwamy b2 i tak do końca

* Algorytm dekodowania: Mając ciąg (a1,...,a_n-2) znajdujemy najmniejszą liczbę b1 z przedziału [1,n] która nie występuję w ciągu i łączymy krawędzią wierzchołki a1 i b1. Usuwamy a1 z ciągu a b1 pomijamy w dalszych rozważaniach. Kontynuujemy analogicznie, aż do wyczerpania elementów ciągu. Na końcu łączymy dwa wierzchołki oznaczone etykietamy których nie użyliśmy do tej pory.

* Zliczanie drzew etykietowanych: Twierdzenie Cayleya: Istnieje n^(n-2) różnych n-wierzchołkowych drzew etykietowanych
* Wniosek: Graf pełny K_n ma dokładnie n^(n-2) drzew rozpinających

* Twierdzenie liczba nieizomorficznych n-wierzchołkowych drzew etykietowanych, takich że deg(v_i) = d_i dla i należącego do [1,n] wynosi:

* Drzewo ukorzenione - posiada wyróżniony wierzchołek - korzeń
* Głębokość (albo poziom) (depth(v)) wierzchołka - jego odległość od korzenia
* Wysokość drzewa - maksymalna głębokość

* Rodzic/dziecko - bezpośrednio nad/pod
* Przodek/potomek - w hierarchi nad/pod
* Bliźniak - wierzchołek mający tego samego rodzica

* Reprezentacja komputerowa drzewa ukorzenionego - tablica rodziców - n[i] zawiera etykietę rodzica wierzchołka o etykiecie i

* Drzewo d-arne - drzewo ukorzenione, gdzie każdy wierzchołek ma conajwyżej d dzieci
* Zupełne drzewo d-arne - o możliwie dużej liczbie wierzchołków, i wszystkie liście różnią się głębokością conajwyżej o 1
* Drzewo d-arne ma co najwyżej d^l wierzchołków na poziomie l
* Drzewo d-arne o wysokości h zawiera n wierzchołków, gdzie zachodzi:

* Drzewo uporządkowane - drzewo d-arne, gdzie dla każdego wierzchołka dzieci mają przypisany pewien porządek liniowy:
* Porządek standardowy drzewa uporządkowanego - uporządkowanie liniowe wszystkich jego wierzchołków rekurencyjnie leksykograficznie po poziomach a następnie zgodnie z porządkiem dzieci

* Drzewo binarne - 2-arne drzewo uporządkowane, w którym dodatkowo określone jest, które dziecko jest lewe, a które prawe

Rekurencyjne przeszukiwanie drzew binarnych:

* pre-order (bieżący, lewy, prawy) - C, D, E, F, G, H, I, J, K, L, M
* in-order (lewy, bieżący, prawy) - F, E, G, D, I, H C, L, K, M, J
* post-order (lewy, prawy, bieżący) - F, G, E, I, H, D, L, M, K, J, C

* Zliczanie drzew binarnych - Twierdzenie: Liczba b_n różnych drzew binarnych o n wierzchołkach wynosi  i jest nazywana liczbą Catalana

## :small_blue_diamond: Wykład 4 - Algorytmy przeszukiwania grafów

* Przeszukiwanie grafu - zaczynamy odwiedzanie z pewnego wierzchołka startowego, dozwolonym ruchem jest przejście po krawędzi (od wierzchołka odwiedzonego), każdy wierzchołek i krawędź grafu odwiedzone są dokładnie raz
* Pojedyńcze wykonanie całej procedury generuje tzw drzewo przeszukiwania (ukorzenione)
* Procedura może być wykonywana wielokrotnie, aż nie ma nieodwiedzonych wierzchołków w grafie, rezultatem całego przeszukiwania jest tzw las przeszukiwania

Klasyfikacja krawędzi w wyniku przeszukiwania:
1. drzewowa (T): v odwiedzony z u w wyniku przejścia (u,v)
2. w przód (F): nie drzewowa i v potomkiem u
3. w tył (B): nie drzewowa i v jest przodkiem u
4. poprzeczna (C): pozostałe przypadki (pomiędzy gałęziami lub drzewami)


### BFS

Używamy kolejki


Złożoność czasowa O(|V|+|E|)(liniowa)

### DFS

Używamy stosu. Są dwa czasy - czas odwiedzenia, czas opuszczenia


Złożoność czasowa O(|V|+|E|)

* Ścieżka DFS - fragment drzewa przeszukiwania DFS zbudowany do momentu, gdy jakiś wierzchołek staje się czarny
* Fakt: Jeśli P jest ścieżką DFS kończącą się w wierzchołku t, to wszyscy sąsiedzi t leżą na ścieżce P. Ponadto, jeśli deg(t)>1 to wszyscy sąsiedzi t leżą na pewnym cyklu
* Wniosek: Jeśli w grafie prostym G minimalny stopień wierzchołka gamma > 1, to graf zawiera cykl o długości conajmniej gamma + 1

* Znajdowanie mostów: krawędź jest mostem <=> nie leży na żadnym cyklu
* Kontrakcja podgrafu H: uczynienie z H pojedynczego wierzchołka

Algorytm znajdowania mostów:

* Punkt artykulacji: po jego usunięciu jest więcej składowych spójnych
* Fakt: Wierzchołek v jest punktem artykulacji <=> istnieją wierzchołki u,w (różne od v), takie że każda droga z u do w przechodzi przez v
* Twierdzenie: Jeśli T jest drzewem DFS dla pewnego grafu, to jego korzeń r jest punktem artykulacji <=> r ma więcej niż jednego syna w tym drzewie
* Twierdzenie A: Jeśtli T jest drzewem DFS, to jego wierzchołek v (nie korzeń) jest punktem artykulacji <=> v ma syna w, takiego że żaden potomek wierzchołka w ani on sam nie jest połączony krawędzią nie-drzewową z właściwym przodkiem wierzchołka v
* Twierdzenie B: Jeśli T jest drzewem DFS, to wierzchołek v (niekorzeń) jest punktem artykulacji <=> v ma syna w, dla którego low(w)>=v.d, gdzie low(w) - mniejsza z liczb w.d lub najmniejsza z liczb u.d pośród wierzchołków u połączonych nie-drzewową krawędzią z w lub pewnym jej potomkiem

Schemat znajdowania punktów artykulacji:


Sortowanie topologiczne - tylko dla grafów skierowanych

* Polega na takim ustawieniu wierzchołków grafu w ciąg, że jeśli w grafie jest krawędź (u,v), to u musi być przed v
* Graf da się posortować topologicznie <=> gdy nie zawiera cykli.
* Rozwiązanie:
1) zastosować DFS
2) ustawić wierzchołki od największego czasu zakończenia do najmniejszego

Znajdowanie składowych silnie spójnych:

## :small_blue_diamond: Wykład 5 - Drzewa rozpinajace

* Drzewo rozpinające - dla spójnego nieskierowanego grafu prostego to taki podgraf T, który jest drzewem i zawiera wszystkie wierzchołki tego grafu
* W grafie niespójnym istnieje las rozpinający będący sumą drzew rozpinających jego składowych spójnych
* Każde drzewo rozpinające danego grafu ma tyle samo krawędzi i wierzchołków
* Twierdzenie Kirchoffa: Liczba różnych drzew rozpinających spójnego grafu etykietowanego wynosi tyle co dopełnienie algebraiczne dowolnego elementu macierzy M(G) = D(G) - A(G), gdzie D(G) jest diagonalną macierzą zawierającą na przekątnej stopnie odpowiednich wierzchołków, a A(G) jest macierzą sąsiedztwa

* Liczba cyklomatyczna gamma(G) (lub rząd cykliczności) - liczba krawędzi dopełnienia dowolnego lasu rozpinającego grafu G
* Rząd rozcięcia Epsilon(G) - liczba krawędzi w dowolnym lesie rozpinającym
* Epsilon(G) + gamma(G) = |E(G)|

* Twierdzenie: Jeśli L jest lasem rozpinającym grafu G, to :
1) Każdy cykl w G ma wspólną krawędź z dopełnieniem L
2) Każde rozcięcie G ma wspólną krawędź z L

* Cykl fundamentalny grafu G związany z lasem rozpinającym L - cykl powstały przez dodanie jakiejkolwiek krawędzi z G nie należącej do L (utworzy się wówczas dokładnie jeden cykl)
* Zbiór cykli fundamentalnych związanych lasem L to zbiór wszystkich takich cykli

* Rozcięcie fundamentalne grafu G związane z lasem L - gdy z lasu L usuniemy dowolną krawędź, to powstają dwa rozłączne zbiory wierzchołków V_1 i V_2, zbiór wszystkich krawędzi grafu G, takich że jeden koniec jest w V_1 a drugi w V_2, tworzy rozcięcie fundamentalne
* Analogicznie zbiór wszystkich = zbiór rozcięć fundamentalnych związanych z lasem L

Fakty o cyklach i rozcięciach:
- zbiór krawędzi jest rozspajający <=> przecina się z każdym drzewem rozpinającym (ale nie musi być minimalny bo można wziąć wszystkie krawędzie np)
- zbiór krawędzi C grafu G zawiera cykl <=> dopełnienie każdego drzewa rozpinającego w G przecina się z C
- cykl i rozcięcie mają zawsze parzystą liczbę wspólnych krawędzi (0 też jest parzyste)

* Twierdzenie: T jest drzewem rozpinającym, C jest cyklem fundamentalnym otrzymanym z T poprzez dodanie krawędzi e. Wtedy C składa się z e i tych krawędzi T, które wyznaczają fundamentalne rozcięcia zawierające e
* Twierdzenie: Rozcięcie fundamentalne wyznaczone przez odjęcie krawędzi e z drzewa rozpinającego T składa sie z e i dokładnie tych krawędzi w dopełnieniu T, których cykle fundamentalne zawierają e

Przestrzeń krawędzi:
* W_e(G) - zbiór wszystkich podzbiorów E(G)
* operacja sumy prostej na elementach W_e(G):

* Fakt: W_e(G) z operacją sumy jest przestrzenią liniową nad ciałem Z_2. Bazę stanowi zbiór E(G) wszystkich krawędzi grafu G

Podprzestrzeń cykli W_c(G):
* elementy to zbiór pusty i zbiory krawędzi wszystkich cykli G i sum cykli krawędziowo rozłącznych (elementy W_c(G) można nazywać cyklami uogólnionymi)
^^ Zapomniałem o cyklu 1-2-4-5-3-1

* Twierdzenie: W_c(G) jest podprzestrzenią liniową przestrzeni W_e(G)
* Fakt: graf jest eulerowski <=> jego zbiór krawędzi jest cyklem uogólnionym

Podprzestrzeń rozcięć W_s(G):
* Elementy: zbiór pusty, zbiory krawędzi wszystkich rozcięć i sum krawędziowo rozłącznych rozcięć
* Twierdzenie: W_s(G) jest podprzestrzenią liniową przestrzeni W_e(G)

* Przypomnienie: Baza przestrzeni liniowej - to taki podzbiór elementów przestrzeni liniowej, że generuje całą przestrzeń i jest liniowo niezależny (inaczej żaden wektor w bazie nie może być wyrażony jako kombinacja liniowa innych wektorów z tego zbioru, a każdy wektor z przestrzeni można wyrazić jako kombinację liniową wektorów z bazy)
* Twierdzenie: Zbiór cykli fundamentalnych dowolnego drzewa rozpinającego stanowi bazę podprzestrzeni cykli W_c(G)
* Twierdzenie 2: Zbiór rozcięć fundamentalnych dowolnego drzewa rozpinającego stanowi bazę przestrzeni W_s(G)

* Wniosek: Wymiar przestrzeni W_c(G) wynosi gamma(G) (liczba cyklomatyczna), a wymiar przestrzeni W_s(G) wynosi Epsilon(G) - co w sumie się zgadza jak spojrzymy na poniższy rysunek ponownie

* W grafie G istnieje dokładnie 2^gamma(G) różnych cykli uogólnionych.
* W grafie G isnieje dokładnie 2^Epsilon(G) różnych podgrafów, z których każdy jest rozcięciem lub sumą rozcięć krawędziowo rozłącznych

Własności macierzy incydencji:
G - nieskierowany graf prosty (wszystkie operacje nad ciałem Z_2). Niech D oznacza pewien zbiór krawędzi G. Przez I_D oznaczymy zbiór kolumn macierzy incydencji odpowiadających zbiorowi D

Fakty:
* D stanowi cykl uogólniony <=> suma kolumn w I_D wynosi 0
* D reprezentuje graf acykliczny <=> kolumny w I_D są niezależne liniowo
* D reprezentuje podgraf spójny <=> kolumny w I_D rozpinają całą przestrzeń kolumn macierzy incydencji (inaczej jeżeli zXORujemy któreś kolumny z I_D to jesteśmy w stanie uzyskać inną kolumnę z MACIERZY INCYDENCJI (dla tych krawędzi które sąsiadują z krawędziami z I_D), dla przykładu powyżej, jak weźmiemy sobie podgraf spójny składający się z krawędzi 1, 3 i 4 to kolumnę 2 możemy wyrazić jako 1 XOR 3)
* D reprezentuje drzewo rozpinające <=> kolumny w I_D stanowią bazę przestrzeni kolumn całej macierzy incydencji (to samo co powyżej, tylko możemy za pomocą XORa tych krawędzi wyrazić całą macierz)

* Zastosowanie: sieci elektryczne
* Prawo Ohma : U = I*R
* Dwa prawa Kichoffa:
1) dla wezłów sieci: suma natężeń w węźle wynosi 0
2) dla oczek sieci: suma napięć w oczku sieci wynosi 0

Problem: Minimalne drzewo rozpinające (MST - minimum spanning tree) - znaleźć drzewo rozpinające o minimalnym łącznym koszcie krawędzi

Dwa podejścia:
* Algorytm Prima (modyfikacja BFS) - zaczynamy od wierzchołka startowego s i stopniowo powiększamy drzewo rozpinające. Początkowo S = {s}. Rozpoczynamy od utworzenia zbioru krawędzi, które mają jeden koniec w wierzchołku ze zbioru S, a drugi poza nim. Te krawędzie nazywamy rozspajającymi. Wybieramy najlżejszą krawędź ze zbioru rozspajającego i dodajemy drugi wierzchołek v (ten spoza S do S), następnie dodajemy nowe krawędzie incydentne z v do zbioru rozspajającego.

* n = |V|
m = |E|

* inicjalizacja: O(n)
pętla (d * delMin()) + (m * decreaseKey())

* Jeśli kolejka to kopiec binarny to pętla O(nlog(n)) + O(mlog(n)) = O((n+m)log(n))

* Jeżeli kopiec Fibonnacciego to O(nlog(n) + m)

* Algorytm Kruskala: początkowo T = {}, rozpatruj krawędzie w kolejności niemalejących wag i dodaj do T te, które nie tworzą cyklu, pozostałe odrzucaj dpóki nie uzyskasz drzewa rozpinającego

* Główny problem - sprawdzanie czy krawędź nie tworzy cyklu z dotychczasowo dodanymi. Można użyć pomocniczej struktury danych typu union-find. Każda nowa krawędź (u,v), która utworzyłaby cykl ma tę własność że oba jej końce u i v należą do tego samego drzewa w lesie T.


* O(mlog(m))

Problem Komiwojażera (TSP) - dany jest pełny graf G = (V, E), z nieujemnymi wagami wymiernymi. Znaleźć cykl Hamiltona H w G o minimalnym łącznym koszcie krawędzi - problem NP-trudny

* Ale można znaleźć w czasie wielomianowym rozwiązanie przybliżone o współczynnik co najwyżej 2, jeśli funkccja wag w w: E -> Q+ spełnia nierówność trójkąta (bezpośrednia droga między dwoma węzłami musi być krótsza lub równa drodze przez punkt pośredni d(A,C)≤d(A,B)+d(B,C))

* Algorytm -> znajdź dowolne drzewo rozpinające i zastąp każdą krawędź parą krawędzi przeciwnych, znajdź cykl Eulera w takim grafie i pominąć w tym cyklu wszystkie wierzchołki (stosując własność trójkąta), które występowałyby wielokrotnie

## :small_blue_diamond: Wykład 6 - Algorytmy najkrótszych ścieżek

Problem najkrótszych ścieżek:
* Wejście: skierowany graf G, z wagami na krawędziach danymi przez funkcję w: E->R, i wierzchołek startowy s
* Wyjście: dla każdego wierzchołka v należącego do V długość najkrótszej ścieżki z s do v oraz rodzic w drzewie najkrótszych ścieżek (jeśli istnieje) pozwalający zrekonstruować najkrótsze ścieżki z s

Najkrótsza ścieżka może nie istnieć z dwóch powodów:
* v może nie być osiągalny z s
* w grafie mogą istnieć ujemne cykle (wtedy może nie być dolnego ograniczenia na długość ścieżki)

Własności najkrótszych ścieżek:
* długość najkrótszej ścieżki będziemy oznaczali przez mi(s,v)
* 

Ogólny pomysł na algorytm:
podobny do BFS. Z każdym wierzchołkiem v związujemy 2 atrybuty:
* v.distance (najkrótsza obecnie znana odległość z s do v)
* v.parent (poprzednik/rodzic v na najkrótszej ścieżce obecnie znanej)

* Inicjalizacja:

s.distance = 0

s.parent = s

* A wszystkie inne wierzchołki

distance = +inf

parent = null

* A następnie uaktualnienia tych atrybutów poprzez relaksację krawędzi:

* Algorytm dokonuje kolejnych relaksacji dopóki najkrótsze ścieżki nie zostaną obliczone lub ujemny cykl wykryty

Szczególne warianty algorytmu znajdowania najkrótszych ścieżek
1. Skierowany graf acykliczny (DAG)
* Jeśli graf jest DAG, to stanowi to najprostszy przypadek
* Każdy DAG można posortować topologicznie w czasie O(m+n) i otrzymać ciąg (v_1, ..., v_n). Następnie zakładając że s =v_j dla pewnego 0<j<=n, można dokonać relaksacji wszystkich krawędzi wychodzących z v_j, a następnie wychodzących z v_j+1 i tak dalej do v_n
* W ten sposób każda krawędź poddana jest relaksacji co najwyżej raz a każda najkrótsza ścieżka jest odkryta jako podciąg ciągu dokonanych relaksacji.
* Złożoność czasowa O(m+n)
2. Algorytm Dijkstry (wagi nieujemne)
* Jeśli nie ma krawędzi o ujemnych wagach to nie ma ujemnych cykli
* Mogą istnieć zwykłe cykle więc nie możemy założyć wykonalności sortowania topologicznego
* Wykonujemy relaksacje w kolejności niemalejących najkrótszych odległości od źródła. Dzięki nieujemności wag, każda najkrótsza ścieżka zostanie w ten sposób odkryta
* Wykorzystujemy kolejke priorytetową - priorytet = wartość atrybutu distance
* Pesymistycznie:
* Inicjalizacja: O(n)
* Pętla: O(n*(delMin+insert) + m* decreaseKey)
* O((n+m)log(n))(dla kopca binarnego)
* Przypadek przeciętny:
* O(m+nlog(M/n)log(n))
* Z użyciem kopca Fibonacciego:
* O(m + nlog(n))
* Jeśli wagi są całkowite i ograniczone przez stałą C to można zredukować złożoność pesymistyczną do O(m+nC)

3. Algorytm Bellmana-Forda (dowolne wagi)
* W poprzednich przypadkach wystarczało conajwyżej m relaksacji
* W ogólnym przypadku wystarcza O(nm) relaksacji, aby odkryć każdą najkrótszą ścieżkę (podejście brute force)
* Dowolna najkrótsza ścieżka może zawierać conajwyżej n-1 krawędzi spośród m, więc wystarczy dokonać (n-1)-krotnej relaksacji wszystkich m krawędzi ustawionych w ustalony ciąg, aby ciąg krawędzi każdej najkrótszej ścieżki był w nim zawarty jako podciąg (i w ten sposób wykryć wszystkie dobrze określone najkrótsze ścieżki). Dla wierzchołków nieosiągalnych v.d = inf, a dla ujemnych cykli należy jeszcze raz dokonać m relaksacji (te, dla których atrybut d wciąż maleje, leżą naścieżkach zawierających ujemny cykl) i następnie w czasie liniowym przypisać wierzchołkom osiągalnym z tego cyklu wartość v.d = inf

Najkrótsze ścieżki z każdego wierzchołka do każdego
* Wejście: Graf skierowany z wagami na krawędziach
* Wyjście: najkrótsze ścieżki pomiędzy wszystkimi parami wierzchołków

* Rozwiązanie 1: Wykonać Bellmana-Forda ze wszystkich wierzchołków (O(n^2*m))
* Rozwiązanie 2 (szybsze): odpowiednio zamienić wagi na nieujemne (zachowując najkrótsze ścieżki) i wykonać algorytm Dijkstry ze wszystkich wierzchołków (O(n(m+nlog(n)))) - to roziązanie można wykonać tylko jeśli nie ma cykli ujemnych. Aby móc zastosować te algorym, wagi muszą być nieujemny - dla każdje krawędzi e = (v,w) o dotychczasowej wadze w(e) przypisywana jest nowa waga: w'(e) = w(e) + pot(v) - pot(w), gdzie pot() - potencjał wierzchołka, jest pewną funkcją spełniającą warunki:
* nowe wagi są nieujemne
* najkrótsze ścieżki przy nowych wagach są takie same jak przy starych sumy wag na cyklach nie ulegają zmianie
* Funkcję pot() wyznaczamy następująco
* dodajemy do grafu pewien sztuczny wierzchołek s oraz łączymy go krawędziami (skierowanymi) z wagami 0 do wszystkich wierzchołków grafu, obliczamy najkrótsze odległości mi(v) z s do każdego wierzchołka v grafu - to jest wartość naszego potencjału, w tym wypadku musimy raz wykonać Bellmana-Forda

Algorytm Johnsona:
* wykonaj Bellmana-Forda z wierzchołka s aby obliczyć wartość mi(v) dla każdego wierzchołka v (przy okazji pozwala on wykryć ewentualne ujemne cykle)
* Wykonaj Dijkstre z każdego wierzchołka
* Przywróć poprzednie wagi
* Złożoność: O(mn)(BF) + O(n(m+nlogn))(n razy dijkstra, przy użyciu kopca Fibonacciego)

Oszacowanie średnicy grafu (diam(G))

## :small_blue_diamond: Wykład 7 - Planarność

* Graf planarny - taki, który można narysować na płaszczyźnie bez przecięć krawędzi
* Rysunek nazywamy rysunkiem płaskim (grafem płaskim)
* Zastosowania:
* projektowanie bezkolizyjnych połączeń przy najmniejszej liczbie mostów, wiaduktów
* Projektowanie układów elektronicznych i sposobów ich wykonania

* Grafy K_5 i K_{3,3} (grafy Kuratowskiego) nie są planarne

* Proste obserwacje: każdy podgraf grafu planarnego jest planarny i graf zawierający jako podgraf graf nieplanarny sam jest nieplanarny

* Wniosek: Jeśli graf zawiera graf Kuratowskiego jako podgraf to jest nieplanarny (warunek wystarczający)

* Homeomorfizm - dwa grafy są homeomorficzne jeżeli oba można uzyskać z pewnego grafu poprzez wstawienie wierzchołków stopnia 2 wewnątrz ich krawędzi

* Twierdzenie Kuratowskiego: Graf jest planarny <=> nie zawiera grafu homeomorficznego z K_5 ani z K_{3,3}

* Ściągalność - graf G jest ściągalny do grafu H <=> H można otrzymać przez kolejne ściągnięcia krawędzi grafu G

* Twierdzenie (druga charakteryzacja planarności): Graf jest planarny <=> nie zawiera podgrafu ściągalnego do K_5 ani do K_{3,3}
* Liczba przecięć cr(G) grafu G, to najmniejsza możliwa liczba przecięć krawędzi w dowolnym kierunku grafu G na płaszczyźnie
* cr(K_5) = cr(K_{3,3}) = 1
* cr(Graf petersena) = cr(K_{4,3}) = 2

* Graf zewnętrznie planarny <=> można go tak narysować na płaszczyźnie bez przecięć krawędzi, że wszystkie wierzchołki leżą na zewnętrznym obrzeżu. Poniższy nie jest zewnętrznie planarny

* Twierdzenie: Graf jest zewnętrznie planarny <=> gdy nie zawiera grafu homeomorficznego z K_4 ani K_{2,3} ani ściągalnego do żadnego z nich

* Ściana grafu płaskiego - obszar spójny nie będący częścią grafu (krawędzią ani wierzchołkiem)
* Poniższy graf ma 3 ściany:

* Jedyna ściana nieograniczona nazywana jest ściana nieskończona

Rzut stereograficzny:
1. kładziemy sferę na płaszczyźnie
2. rysujemy dowolny obiekt na sferze (poza wierzchołkiem sfery)
3. rzut stereograficzny stanowi cień jaki rzucałby rysunek gdyby umieścić punktowe źródło światła w wierzchołku sfery

Jeżeli przesuniemy na sferze rysunek grafu tak, żeby jedna ze ścian zawierała wierzchołek sfery to uczynimy ją ścianą nieskończoną.

* Twierdzenie Eulera: Jeśli G jest dowolnym rysunkiem płaskim spójnego grafu planarnego to zachodzi następujący wzór: n - m + f = 2, gdzie f - liczba ścian, m - liczba krawędzi, n - liczba wierzchołków
* Uwaga twierdzenie powyższe można zastosować do grafów które nie są proste wówczas n - m + f = k + 1, gdzie k jest liczbą składowych

* Wniosek z tw. Eulera: Jeśli G jest spójnym, prostym grafem planarnym mającym n >= 3 wierzchołków t:
* jego liczba krawędzi m spełnia m <= 3n - 6
* jeśli ponadto G nie zawiera trójkątów C_3, to zachodzi m <= 2n - 4

* Twierdzenie: Każdy graf planarny prosty zawiera conajmniej jeden wierzchołek stopnia niewiększego niż 5

* Grubość grafu t(G) - najmniejsza liczba warstw zawierających rysunki płaskie podgrafów G, które po złożeniu utworzyłyby gra G. (inna miara "nieplanarności")
* K_5, K_{3,3} i K_6 mają grubość 2
* Zastosowanie w elektronice - przy drukowaniu układów scalonych, tak aby przewody się nie przecinały

* Twierdzenie: Jeśli G jest prosty i ma n >= 3 wierzchołków to grubość:

* Genus powierzchni - powierzchnia ma genus wynoszący g jeśli jest homeomorficzna ze sferą z "doklejonymi" g "uchwytami", poniżej genus-2

* Genus grafu to najniższy możliwy genus powierzchni, na której można dany graf narysować bez przecięć krawędzi ( grafy kuratowskiego mają genus 1)
* Twierdzenie: Genus grafu G jest niewiększy od jego liczby przecięć cr(G)

* Uogólnione twierdzenie Eulera: Jeśli G jest spójnym grafem o genusie g to zachodzi n - m + f = 2 - 2g

* Graf (geometrycznie) dualny G* do grafu płaskiego G:
* zastępujemy każdą ścianę g wierzchołkiem w G*
* każde 2 wierzchołki w G* łączymy krawędzią w G* <=> istnieje odpowiadająca im krawędź w G, która rozgranicza odpowiednie ściany

* Twierdzenie: Jeśli G jest spójnym grafem płaskim to G** (dualny do dualnego do G), jest izomorficzny z G.

* Twierdzenie: Jeśli G jest planarny a G* jest geometrycznie dualny do G, to dowolny zbiór krawędzi w G tworzy cykl w G <=> odpowiadający mu zbiór krawędzi w G* stanowi rozcięcie w G*

* Każde rozcięcie w G odpowiada cyklowi w G*

* Graf G* jest abstrakcyjnie dualny do G <=> istnieje taka wzajemna jednoznaczna relacja międyz zbiorami krawędzi G i G*, że cykle w G odpowiadają krawędziom w G*
* Twierdzenie: G* jest abstrakcyjnie dualny do G <=> G jest abstrakcyjnie dualny do G*
* Twierdzenie: G jest planarny <=> istnieje graf abstrakcyjnie dualny do G

## :small_blue_diamond: Wykład 8 - Kolorowanie

* Przez kolorowanie wierzchołków grafu G, nazywamy takie przypisanie każdemu z jego wierzchołków pewnego kolur, że dwa sąsiednie wierzchołki nie mają tego samego koloru
* Graf nazywamy k-kolorowalnym <=> wystarczy k kolorów, żeby go pokolorować
* Jeśli graf jest k-kolorowalny to jest (k+1)-kolorowalny (obvious)
* Liczba chromatyczna chi(G) - najmniejsza liczba k, taka że G jest k-kolorowalny
* Graf G jest k-chromatyczny <=> 

* Własności:
1. chi(Z) = 0 (graf zerowy)
2. chi(N_n) = 1
3. chi(K_n) = n
4. Jeśli G zawiera K_n jako podgraf to chi(G) >= n
5. Graf jest dwudzielny (i niepusty) <=> jest 2-chromatyczny
6. każde drzewo chi(T)=2
7. Każdy cykl C_n parzysty jest 2-chromatyczny, a nieparzysty 3-chromatyczny
8. Graf Petersena jest 3-chromatyczny
9. Każde koło W(n) jest albo 3-chromatyczne albo 4-chromatyczny (w zalezności od parzystości n)

* Twierdzenie: Jeśli G jest prostym grafem, w którym największy stopień wierzchołka wynosi Delta, to G jest (Delta+1) - kolorowalny

* Twierdzenie Brooksa: Jeśli G jest spójny, prosty, niepełny i jego największy stopień wierzchołka wynosi Delta >= 3 to jest Delta-kolorowalny

* Twierdzenie: Każdy graf planarny prosty jest 4-kolorowalny

Kolorowanie map:
* Mapa opisana jest przez graf G planarny 3-spójny (bez mostów). Wtedy ściany G odpowiadają obszarom mapy, krawędzie granicom między obszarami, a wierzchołki punktom, w których spotykają się granice
* Mapa jest k-kolorowalna(f) <=> jej ściany (włączając ścianę nieograniczona) można tak pokolorować, że po obu stronach każdej krawędzi są różne kolory
* Mapa jest k-kolorowalna(v) <=> odpowiadający jej graf jest k-kolorowalny (wierzchołkowo)
* Twierdzenie: Jeśli G jest planarnym grafem bez pętli a G* jest grafem geometrycznie dualnym, to G jest k-kolorowalny(v) <=> G* jest k-kolorowalny(f)
* Wniosek: Każda mapa jest 4-kolorowalna
* Twierdzenie: Mapa jest 2-kolorowalna(f) <=> odpowiadający jej graf jest eulerowski
* Twierdzenie: Mapa kubiczna (której graf jest kubiczny, czyli 3-regularny) jest 3-kolorowalna(f) <=> każda jej ściana jest ograniczona parzystą liczbą krawędzi

Kolorowanie krawędzi:
* Graf jest k-kolorowalny(e) gdy jego krawędzie można pokolorować k kolorami tak, że żadne dwie krawędzie incydentne z tym samym wierzchołkiem nie mają tego samego koloru
* Indeks chromatyczny chi'(G) grafu G to najmniejsza liczba k, że graf G jest k-kolorowalny(e)

* Twierdzenie Vizinga: W grafie prostym G, w którym najwyższy stopień wierzchołka wyniosi Delta zachodzi Delta <= chi'(G) <= Delta + 1
* Przykład: chi'(C_n) = 2 dla n parzystych i 3 dla nieparzystych
* chi'(K_n) = n - 1 dla n parzystych, a n dla nieparzystych

* Twierdzenie Koniga: Dla grafu G dwudzielnego o największym stopniu wierzchołka Delta zachodzi chi'(G) = Delta

Liczba sposobów pokolorowania wierzchołków grafu
* Funkcja chromatyczna P_G(k) grafu G to funkcja, której watośc wyznacza liczbę sposobów pokolorowania wierzchołków grafu G (tak aby sąsiednie wierzchołki nie miały tego samego koloru)

* Twierdzenie: Jeśli G jest prosty i G - e oraz G \ e oznaczają odpowiednio graf powstały przez usunięcie oraz ściągnięcie krawędzi e tego grafu, to zachodzi następujący wzór rekurencyjny: 

* Funkcja chromatyczna dowolnego grafu jest wielomianem (inaczej nazywamy ją wielomianem chromatycznym)

## :small_blue_diamond: Wykład 9 - Digrafy (grafy skierowane)

* Digraf - graf skierowany
* Krawędzie - uporządkowane pary wierzchołków, nazywane łukami
* Digraf prosty - nie zawiera pętli i łuków wielokrotnych
* Szkielet digrafu to graf nieskierowany przez zastąpienie każdego łuku krawędzią nieskierowaną. Szkielet digrafu prostego nie musi być grafem prostym
* W macierzy sąsiedztwa digrafu a_{i,j} oznacza liczbę łuków z wierzchołka i do j
* Digraf przeciwny do digrafu D - D^T, każda krawędź zas†apiona jest krawędzią przeciwną
* Macierz sąsiedztwa A(D^T) = A^T(D)
* Macierz incydencji digrafu D: d_{i,j} = 1 gdy i jest początkiem krawędzi, -1 gdy końcem, 0 w pozostałych przypadkach

* Graf nieskierowany G jest orientowalny <=> każdą jego krawędź da się zastąpić łukiem, tak że otrzymany graf skierowany jest silnie spójny
* Twierdzenie: Graf jest orientowalny <=> każda jego krawędź jest zawarta w pewnym cyklu (elementarnym)
* Wniosek: Spójny graf nieskierowany G jest orientowalny <=> nie ma mostów

* Algorytm znajdowania orientacji:
* wykonać DFS,
* każdą krawędź drzewową skierować od ojca do syna, a każdą wsteczną od potomka do

* Przechodniość grafu:
* Digraf przechodni <=> dla dowolnych wierzchołków u, v, w jeśli istnieją krawędzie (u,v) i (v,w) to istnieje krawędź (u,w)
* Domknięcie przechodnie digrafu D to najmniejszy digraf D^c przechodni, którego D jest podgrafem

* Porządek częściowy: P = (V,<=) to para składająca się ze zbioru elementów V i relacji binarnej na zbiorze V, która jest:
* zwrotna (każdy element jest w relacji z samym sobą) - przykładowo jeśli V to zbiór liczb {1,2,3}, to relacja R na D jest zwrotna jeśli zawiera pary (1,1), (2,2) i (3,3)
* antysymetryczna - jeśli (a,b) jest w relacji i (b,a) to musi zachodzić a = b
* przechodnia - jeśli (a,b) i (b,c) to (a,c)
* Uwaga "<=" jest tylko sposobem reprezentacji tej relacji
* Przykład: relacja podzielności na zbiorze liczb naturalnych dodatnich niewiększych niż 18
* Podstawowe pojęcia, niech P=(V,<=) będzie porządkiem częściowym i u,v,w należą do V:
* u, v są porównywalne <=> u <= v lub v <= u
* porządek liniowy - wszystkie elementy są porównywalne
* u jest maksymalny <=> gdy nie ma takiego v != u że u <= v
* u jest minimalny <=> nie ma takiego v != u, że v <= u
* v to następnik u <=> v jest elementem minimalnym pośród wszyskich elementów w != u takich że u <= w
* v to poprzednik u <=> element maksymalny pośród wszystkich elementów w != u takich że v <= u
* Element największy to jedyny element maksymalny
* Element najmniejszy to jedyny element minimalny

* Diagram Hassego danego porządku częściowego P to rysunek grafu  (to oznacza poprzednika) taki, że elementy maksymalne są na górze, i dla dowolnej pary wierzchołków, takich że u jest poprzednikiem v wierzchołek u umieszczamy poniżej v

* Łańcuchy i antyłańcuchy
* podzbiór W zbioru V nazywamy łańcuchem <=> wszystkie pary różnych elementów W są porównywalne
* ^^^^ antyłańcuchem <=> ^^^^ nieporównywalne
* Poniższe stwierdzenia zachodzą gdy V jest zbiorem skończonym:
* Twierdzenie Dilworth'a: Minimalna liczba łańcuchów niezbędnych do pokrycia całego zbioru V równa jest maksymalnej liczności antyłańcucha w P
* Dualne twierdzenie Dilworth'a: Minimalna liczba antyłańcuchów niezbędnych do pokrycia zbioru V równa jest maksymalnej liczności łańcucha w P

* Digrafy eulerowskie: digraf jest eulerowski <=> istnieje prosty cykl skierowany zawierający wszystkie krawędzie
* Fakty:
* Digraf jest eulerowski gdy dla każdego wierzchołka zachodzi indeg(v) = outdeg(v)
* każdy digraf eulerowski jest silnie spójny

* Digrafy pół-eulerowskie: Digraf nie będący eulerowskim jest pół-eulerowski <=> dla każdego wierzchołka v poza dwoma u,w, indeg(v) = outdeg(v), a u i w mają stopnie nieparzyste oraz indeg(u) = outdeg(u) + 1 i indeg(w) = outdeg(w) - 1

* Digrafy hamiltonowskie - nie ma prostej charakteryzacji, znane są tylko pewne warunki konieczne:
* Tw. Silnie spójny graf o n wierzchołkach, w którym dla każdego wierzchołka v zachodzi: outdeg(v) >= n/2 i indeg(v) >= n/2 jest hamiltonowski

* W dowolnym digrafie wierzchołek v nazywamy:
* źródłem <=> indeg(v) = 0
* ujściem <=> outdeg(v) = 0
* Fakt: Każdy digraf acykliczny ma przynajmniej 1 źródło i 1 ujście. Dla grafu poniżej źródłami są 3, 5 i 7, a ujściami 2, 9 i 10

* Kondensacja digrafu D (cond(D)) to taki digraf, który powstaje poprzez zamianę składowych silnie spójnych grafu D na wierzchołki, i poprowadzenie łuków ze składowej C do składowej C' <=> gdy istnieje krawędź łącząca te składowe
* Kondensacja każdego digrafu jest acykliczna

* Turniej to digraf, którego szkielet jest grafem pełnym

* Fakt: Turniej może mieć conajwyżej 1 źródło i conajwyżej 1 ujście (dlaczego? bo może być tylko jedna osoba, która wygra wszystko w turnieju, i 1 osoba która przegra wszystko)
* Jest 2^(n(n-1)/2) różnych turniejów etykietowanych o n wierzchołkach. (dlaczego? bo graf pełny ma n*(n-1)/2 krawędzi, a każdą z nich możemy skierować na 2 sposoby)
* Twierdzenie:
* Każdy turniej silnie spójny jest hamiltonowski
* Turniej nie będący digrafem hamiltonowskim jest pół-hamiltonowski
* Wniosek: W każdym turnieju da się uporządkować zawodników w ciąg taki, że poprzedni pokonał następnego w tym ciągu (odpowiada to ścieżce hamiltona)
* Turniej jest nierozkładalny wtedy gdy nie można podzielić jego zbioru wierzchołków na 2 rozłączne podzbiory V1 i V2 takie, że każdy łuk pomiędzy tymi podzbiorami prowadzi z V1 do V2
* Turniej jest silnie spójny <=> jest nierozkładalny
* Wynik wierzchołka v w turnieju to jego stopień wyjściowy (z iloma graczami wygrał)
* Ranking to ciąg nierosnący wyników turnieju odpowiadający wszystkim wierzchołkom tego turnieju
* Twierdzenie: 
* Następujące warunki są równoważne:
* turniej jest acykliczny
* turniej jest przechodni
* ranking turnieju jest ciągiem ściśle malejącym (nie ma wyników ex aequo)
* Wniosek: kondensacja dowolnego turnieju ma ściśle malejący ranking
* Dominacja stopnia k zachodzi pomiędzy wierzchołkiem v i w digrafu <=> istnieje skierowana ścieżka z v do w o długości k
* Król turnieju to taki wierzchołek, który ma dominację stopnia 1 lub 2 do każdego innego wierzchołka (jest osiągalny z v drogą o długości conajwyżej 2)
* Twierdzenie: Każdy turniej ma króla
* Paradoks Condorcet'a: Jeśli turnieje są acykliczne w głosowaniu większościowym (każdy z k głosujących wybiera n obiektów preferencji - tworzone jest n turniejów, a następnie wyniki te są agregowane w jeden turniej), to zagregowany turniej może zawierać cykle, a więc nie da się utworzyć (ściśle malejącego) rankingu preferencji głosujących

## :small_blue_diamond: Wykład 10 - Algorytm PageRank

* Łańcuchy Markowa - zbiór stanów V. W każdym dyskretnym momencie czasowym t należącym do liczb naturalnych, proces ten jest w pewnym stanie v należącym do V, w szczególności, w chwili początkowej t = 0, system jest w pewnym stanie początkowym v(0). W następnym momencie t+1 system, zgodnie z tzw funkcją przejścia, losowo przechodzi ze stanu v(t) do stanu v(t+1)

* Macierz przejść P - macierz kwadratowa, indeksowana stanami i P_{i,j} jest prawdopodobieństwem przejścia ze stanu i do stanu j w dowolnym kroku
* Macierz ta ma następującą własność: suma elementów dowolnego wiersza wynosi 1 - wierszowa stochastyczność
* Digraf łańcucha Markowa - zauważmy, że łańcuch Markowa o zbiorze stanów V, i macierzy przejścia P można naturalnie reprezentować jako digraf D = (V,E), gdzie zbiór wierzchołków to zbiór stanów a łuk (i,j) należy do E <=> p_{i,j} > 0
* Macierz P przejść łańcucha Markowa stanowi macierz sąsiedztwa odpowiadającego mu digrafu D

* Twierdzenie: Jeśli rozkład prawdopodobieństwa bycia łańcucha Markowa o macierzy przejść P w poszczególnych stanach w momencie t jest dany wektorem X_t, to rozkład prawdopodobieństwa X_{T+1} w momencie t+1 dany jest wzorem:

* Wniosek: po k krokach dany jest wzorem:

Klasyfikacja stanów:
* powracający <=> będąc w nim w momencie t prawdopodobieństwo bycia w nim po pewnym czasie t' > t wynosi 1
* chwilowy <=> nie powracający
* pochłaniający <=> prawdopodobieństwo przejścia z niego do innego stanu = 0
* okresowy o okresie 1 < T należącym do N <=> powrócić do stanu v można tylko po liczbie kroków będącej wielokrotnością T
* ergodyczny <=> powracający i nie okresowy

Ergodyczny łańcuch Markowa - wtedy gdy każdy jego stan jest ergodyczny
* Twierdzenie: Ergodyczny łańcuch Markowa ma rozkład stacjonarny, czyli istnieje graniczny rozkład prawdopodobieństwa bycia w poszczególnych stanach gdy czas dąży do nieskończoności. Nie zależy to od stanu początkowego.
* Twierdzenie: Łańcuch jest ergodyczny <=> odpowiadający mu digraf jest silnie spójny i największy wspólny dzielnik długości cykli w grafie wynosi 1

Algorytm PageRank:
* Przeciętne zapytanie: tysiące zwróconych dokumentów
* Możliwości użytkownika: kilkanaście obejrzanych dokumentów
* Cel: wybrać na początek listy te kilkanaście najlepszych
* Rozwiązanie: System Rankingowy
* Ranking: dokumentowi przyporządkowywana jest wartość i wyniki są posortowane po tej wielkości. Ranking ma wiele składowych:
* analiza tekstu (zawartość, url, meta, ...)
* analiza tekstu odnośników
* analiza struktury linków
* analiza logów, ruchu internetowego
* Problemy z tekstem:
* problem braku samo-opisu
* problem różnorodności
* problem nierównej jakości
* zaszumianie, błędy, spamowanie
* Rozwiązanie: WWW z jednej strony stwarza problemy dla klasycznego Systemu Rankingowego, a z drugiej stwarza możliwości ich obejścia dzieki istnieniu dodatkowych źródeł informacji:
* społeczny aspekt publikowania w WWW (linki)
* tekst odnośników (anchor text)
* Struktura linków w grafie WWW może zostać wykorzystana do automatycznego obliczania "ważności", niezależnie od kontekstu zapytania - taki składnik rankingu (niezależny od zapytania) nazywamy statycznym
* Problem: nepotyzm linków - tworzenie linków wskazujących dokumenty będące pod kontrolą tego samego podmiotu, który tworzy link
* Reakcja:
* ważenie linków w taki sposób, że z każdym hostem związana jest ograniczona wielkość, która jest rozdzielana pomiędzy wszystkie wychodzące z niego linki
* ignorowanie linków wewnątrz hosta (poddomeny) przy obliczaniu rankingu

* Pomysł na ocenianie ważności - zliczanie linków wchodzących, ma poważną wadę jest podatne na celowe manipulacje (Search Engine Spam)
* Lepszy pomysł - nie ilość tylko jakość - uwzględniamy "reputację" głosujących, stąd pomysł algorytmu PageRank
* Idea PageRank:
* każda strona ma pewną wartość
* każda strona "głosuje" poprzez linki na inne strony
* o wartości strony decyduje wartość stron na nią głosujących
* 
* Interesuje nas przepływ przez graf WWW taki, że:
1. wartość przepływu sumuje się do 1
2. to co wpływa = temu co wypływa
3. przepły rozdziela się po równo
* 
* PageRank to wartość przepływu R(d) dla każdego dokumentu d
* Przykład: 
* Inna perspektywa - w języku macierzy:
* G(V,E) - rozważany graf
* P - macierz sąsiedztwa G, zmodyfikowana w ten sposób, że każdy wiersz i jest podzielony przez outDeg(d_i)
* Definicja: PageRank to wektor R będący punktem stałym przekształcenia liniowego P^T: 
* Przykład: 
* Problemy z uproszczonym PageRankiem:
* Każdy maksymalny podgraf właściwy nie posiadający linków wychodzących pochłania cały PageRank w grafie
* dokumenty nielinkowane otrzymają zerową wartość
* Rozwiązanie?
* łączymy każdy dokument który nie ma wychodzących linków z każdym innym dokumentem
* dodajemy sztuczne linki ważone ułamkowym współczynnikiem (decay factor)
* prawdziwe linki ważymy wartością (1-d)
* teraz w macierzy przejść każdy wiersz będzie się sumował do 1, macierz taką nazwiemy stochastyczną i istnieje dla niej jednoznaczne rozwiązanie równania  Rozwiązanie to jest głównym wektorem własnym tej macierzy.
* Przykład na macierzach (decay factor : 0.1)
* Dobra są tam jeszcze wzory, ale jebać to nie chce mi się tego przepisywać, nie ma chuja że da PageRanka na obliczeniowym (bo liczenie tego gówna ręcznie zajęłoby za dużo czasu)
* Rozszerzenia PageRank:
* Topic-Sensitive PageRank - klasyczny PageRank jest statyczny, Topic-Sensitive - jest kontekstowy, czyli wrażliwy na temat zapytania, ranking zależy wówczas nie tylko od struktury linków ale i od tematu zapytania
* Trust-Rank i Anti-TrustRank (zastosowanie w zwalczaniu spamu)
* wersje personalizowane

* Topic-Sensitive - zamiast 1 wektora jest wiele wektorów (oryginalnie 16) - każdy związany z inną grupą tematyczną

## :small_blue_diamond: Wykład 11 - Twierdzenia Minimaksowe

* Skojarzenie w grafie - podzbiór M krawędzi grafu, taki że żadne dwie różne krawędzie z M nie są incydentne (równoważne z pojęciem zbioru niezależnego krawędzi)
* Skojarzenie doskonałe - to takie skojarzenie, że każdy wierzchołek z V jest incydentny z jakąś krawędzią z M
* Skojarzenie całkowite - ze zbioru V_1 w zbiór V_2 w grafie dwudzielnym, to takie skojarzenie, że każdy wierzchołek z V_1 jest incydentny z pewną krawędzią z M

* Twierdzenie Halla - Warunek konieczny i wystarczający rozwiązania problemu kojarzenia małżeństw to by dla każdego zbioru k dziewcząt ze zbioru V_1 wszystkie one znały conajmniej k chłopców ze zbioru V_2
* Twierdzenie Halla inaczej sformułowane:
* Twierdzenie: Niepusty graf dwudzielny regularny ma skojarzenie doskonałe

Transwersala:
* Rozważamy rodzinę F = (S_1, ..., S_m) niepustych podzbiorów pewnego zbioru X. Transwersalą rodziny F nazywamy zbiór różnych m elementów zbioru X wybranych po jednym z każdego podzbioru S_i (inaczej nazywamy ją systemem reprezentatów rodziny F)
* Twierdzenie: Rodzina F = (S_1, ..., S_m) ma transwersalę <=> suma dowolnych k podzbiorów F ma conajmniej k elementów - jeszcze inne sformułowanie twierdzenia Hall'a

* Transwersala częściowa rodziny F - transwersala dowolnej podrodziny rodziny F
* Twierdzenie: Rodzina F = (S_1, ..., S_m) ma t-elementową transwersalę częściową <=> suma dowolnych k podzbiorów F ma conajmniej k - (m - t) elementów

Zjawisko dualności i twierdzenia minimaksowe
* W skrócie są takie zagadnienia otymalizacyjne posiadające cechę "dualności", czyli zadanie maksymalizacji pewnej funkcji jest równoważne zagadnieniu minimalizacji innej funkcji
* Do zagadnień takich należą:
* maksymalny niezależny zbiór wierzchołków/krawędzi vs minimalne pokrycie wierzchołkowe/krawędziowe (twierdzenia Gallai)
* skojarzenie maksymalne vs pokrycie wierzchołkowe (w grafie dwudzielnym) (twierdzenie Koniga)
* maksymalna liczba jedynek niezależnych w macierzy binarnej vs minimalne pokrycie tej macierzy (twierdzneie Koniga-Egervary'ego)
* maksymalna liczba ścieżek wierzchołkowo/krawędziowo rozłącznych vs minimalny zbiór rozdzielający/rozspajający (twierdzenie Mengera)
* maksymalny przepływ w sieci vs minimalny przekrój (twierdzenie Forda-Fulkersona)
* W zagadnienach tego typu istnieje zazwyczaj proste ograniczenie od góry maksymalizowanej wielkości przez minimalizowaną (słaba dualność)
* Gdy znajdzie się parę rozwiązań dla których zachodzi równość, oznacza to optymalność obu wielkości równocześnie (certyfikat optymalności)
* Typowe dla tych zagadnień są "twierdzenia minimaksowe" które orzekają o równości rozwiązania maksymalizującego jedną wielkość i minimalizującego drugą (silna dualność)

Zbiór niezależny (i skojarzenie):
* W grafie nieskierowanym G zbiorem niezależnym wierzchołków nazywamy taki podzbiór X wierzchołków, że żadne dwa wierzchołki nie są sąsiednie
* Podobnie z krawędziami - jeżeli nie są incydentne z tym samym wierzchołkiem. Inna nazwa tego pojęcia to skojarzenie w grafie
* Łatwo jest znaleźć dowolne skojarzenie, istotne jest zagadnienie znajdowania zbioru niezaleznego o maksymalnej liczności
* Zastosowania:
* umieszczanie nadajników radiowych bez kolidacji
* lokowanie dużych sklepów lub usług o podobnym profilu sprzedaży
* umieszczanie niebezpiecznych substancji w sąsiadujących kontenerach

Pokrycie wierzchołkowe/krawędziowe:
* Pokryciem wierzchołkowym w grafie G nazywamy taki podzbiór X wierzchołków, że każda krawędź z E jest incydenta z conajmniej jednym wierzchołkiem z X
* Pokryciem krawędziowym w grafie G nazywamy taki podzbiór Y krawędzi, że każdy wierzchołek z V jest incydentny z conajmniej jedną krawędzią z Y
* Istotny problem - znalezienie pokrycia o minimalnej liczności

Niezależność i pokrycia - oznaczenia:
* Słaba dualność niezależności i pokryć:
* Fakty:
* 
* Twierdzenie Gallai: Zbiór wierzchołków jest pokryciem o maksymalnej liczności <=> jego dopełnienie jest zbiorem niezależnym o minimalnej liczności. Wynika z tego, że:
* Zachodzi też druga dualność:
* 

Skojarzenia w grafach dwudzielnych:
* Twierdzenie Koniga: W grafie dwudzielnym zachodzi , czyli maksymalna liczba krawędzi niezależnych (maksymalna liczność skojarzenia) jest równa minimalnej liczbie wierzchołków w pokryciu:

Skojarzenia w dowolnych grafach:
* Droga przemienna względem skojarzenia M to taka droga prosta, której krawędzie na przemian należą i nie należą do skojarzenia M. (przyjmujemy, że pojedyncza krawędź jest zawsze drogą przemienną)
* Droga powiększająca względem skojarzenia M to dowolna droga przemienna, która nie jest cyklem, taka, że jej końce nie są końcami krawędzi z M
* Twierdzenie Berge: skojarzenie jest skojarzeniem o maksymalnej liczności <=> istnieje ścieżka powiększająca względem tego skojarzenia
* Skojarzenie doskonałe (twierdzenie Tuttego):

* Twierdzenie Koniga-Egervaryego: Rozważamy macierz binarną (zawierającą tylko 0 i 1). Linią nazwiemy dowolną kolumnę lub wiesz tej macierzy.
* Twierdzenie: Maksymalna liczba jedynek nieleżących w tej samej linii równa jest minimalnej liczbie linii zawierających wszystkie jedynki.
* Twierdzenie to jest równoważne twierdzeniu o skojarzeniu maksymalnym w grafie dwudzielnym: macierz to macierz incydencji rozważanego grafu dwudzielnego

Rozłączne drogi a spójność:
* Twierdzenie Mengera (wersja krawędziowa i wierzchołkowa): W dowolnym grafie spójnym, dla dowolnych niesąsiednich wierzchołków u, v, maksymalna liczba dróg rozłącznych krawędziowo (wierzchołkowo) łączących u i v równa jest minimalnej liczności zbioru rozspajającego (rodzielającego), który oddziela wierzchołki u i v

## :small_blue_diamond: Wykład 12 - Przepływy w sieciach

* Sieć przepływowa ze źródłem s i ujściem t to graf skierowany z wymiernymi nieujemnymi wagami na krawędziach, przy czym indeg(s) = 0 i outdeg(t) = 0. Wagę c(e) krawędzi e nazywamy jej przepustowością

* Czasami rozpatruje się przepustowość wierzchołków - zastępuje się wierzchołek parą wierzchołków połączonych jedną krawędzią o odpowiedniej przepustowosci
* Przepływ w sieci G z funkcją przepustowości c to taka funkcja, która spełnia warunki:
* 
* Krawędz e, dla której f(e) = c(e) nazywamy nasyconą

Maksymalny przepływ:
* Wartość przepływu f, oznaczana jako |f| to suma wartości przypływu na wszystkich krawędziach mających źródło jako początek (lub ujście jako koniec, daje to tę samą liczę)
* Przepływ maksymalny dla danej sieci to dowolny przepływ mający maksymalną możliwą wartość
* Przekrój - rozcięcie w grafie reprezentującym sieć, które oddziela źródło od ujścia

* Przepustowość przekroju - suma przepustowości wszystkich krawędzi skierowanych od składowej zawierającej źródło do składowej zawierającej ujście
* Zachodzą następujące zależności:
* wartość przepływu nie może być wyższa niż przepustowość jakiegokolwiek przekroju (słaba dualność)
* jeśli znajdziemy taki przepływ f i taki przekró, że wartość przepływu równa jest przepustowości tego przekroju, to mamy pewność, że przepływ jest maksymalny (certyfikat optymalności)
* Twierdzenie Forda-Fulkersona: Wartość maksymalnego przepływu w każdej sieci zawsze równa jest minimalnej wartości przekroju w tej sieci.

* Powyższe twierdzenie minimaksowe nie jest najwygodniejszą metodą algorytmicznego znajdowania maksymalnego przepływu
* Większość znanych algorytmów opartych jest na pojęciu ścieżki powiększającej przepływ
* Ścieżka powiększająca dany przepływ f to taka ścieżka nieskierowana (krawędzie mogą być skierowane dowolnie) i prosta od źródła do ujścia, że zachodzą następujące warunki:
* każda krawędź e skierowana od źródła do ujścia jest nienasycona
* dla każdej krawędzi skierowanej przeciwnie (od ujścia do źródła) f(e) > 0
* Interpretacja: w takim wypadku na każdej krawędzi e pierwszego typu można potencjalnie powiększyć przepływ o wartość c(e) - f(e), a na pozostałych zmniejszyć "cofanie" przepływu o wartość f(e). Cały przepływ można więc powiększyć o minimum z tych wartości na całej ścieżce.
* Twierdzenie: Przepływ w danej sieci jest maksymalny <=> nie istnieje żadna ścieżka powiększająca ten przepływ.
* Idea algorytmu: rozpocząć od przepływu zerowego i następnie w każdej iteracji znajdować pewną ścieżkę powiększającą przepływ. Algorytm kończy działanie gdy nie istnieje już żadna ścieżka powiększająca
* Złożoność O(E)
* Przykład: 
Na początku bierzemy przepływ zerowy. Konstruujemy drogi powiększające przepływ v -> s -> t -> w (zwiększamy przepływ o 2), v -> x -> z -> w (znowu o 2) i wreszcie v -> u -> z -> x -> y -> w, wzdłuż której możemy zwięksyć przepływ o 1. Otrzymamy przepływ o wartości 5, a ponieważ sieć ma przekrój o przepustowości 5 ((vs), (vx), (uz)) to znaleziony przepływ jest maksymalny, a ten przekrój jest przekrojem minimalnym.

* Powyższy algorytm ma małe problemy - duża złożoność w pesymistycznym przypadku, liczby mogą być niewymierne, i algorytm nigdy się nie skończy.
* Algorytm Edmonda-Karpa: Aby zaradzić temu problemowi, można znajdować kolejne ścieżki powiększające używając algorytmu BFS. Tzn. w każdej iteracji starać się znaleźć najkrótszą ścieżkę powiększającą od źródła do ujścia.
* Złożoność: O(n*m^2)