Spis podstawowych wymagan z wykladow przedmiotu GIZ
***************************************************

Ponizej posluguje sie numeracja z ksiazeczki Wilsona "Wprowadzenie do teorii grafow", wydanie drugie PWN 1998

R - rozdzial
p - paragraf
T - twierdzenie
L - lemat (prostsze twierdzenie)
W - wniosek
D - dowod twierdzenia, lematu lub wniosku

twierdzenia i zagadnienia w nawiasach kwadratowych ("[", "]") sa opcjonalne (na wyzsze oceny)

Kazde wymienione twierdzenie nalezy znac i rozumiec (w tym na wyzsze oceny rowniez te opcjonalne)

Jesli dodatkowo jest napisane "+ D" to dowód tego twierdzenia wchodzi w sklad opcjonalnego zakresu wiedzy na najwyzsze oceny

***
Material:

R 1 i R 2 ("Wprowadzenie" i "Definicje i przyklady")

p1 i p2 ("Co to jest graf?", "Definicje")
definicja grafu i grafu skierowanego, wierzcholki, krawedzie, luki, petle, grafy proste, izomorfizm, spojnosc, skladowe spojne, sasiedztwo, incydentnosc, stopnie, ciag stopni, lemat o usciskach dloni, podgraf,  macierze sasiedztwa, macierz incydencji, listy sasiedztwa

c: c: 1.1 - 1.7, 2.1 - 2.14

p3 ("Przyklady")
grafy puste, pelne, cykliczne, liniowe (sciezkowe), kola, regularne, kubiczne, Petersena, platonskie, dwudzielne, (hiper-)kostki, dopelnienie grafu

c: 3.1 - 3.6

R 3 ("Drogi i cykle")
p 5 ("Spojnosc")
spojnosc, dlugosc sciezki, droga, cykl, 
T5.1 + D ("charakteryzacja dwudzielnych przez cykle")
zbior rozspajajacy, rozciecie, spojnosc krawedziowa, zbior rozdzielajacy, wierzcholek rozcinajacy, punkt artykulacji (wierzcholek rozdzielajacy), podzial grafu na bloki 

c: 5.1 - 5.7

p 6 ("Grafy eulerowskie")
cykl Eulera, graf eulerowski, pol-eulerowski, 
L6.1 + D
T6.2 (Tw. Eulera "charakteryzacja grafow eulerowskich przez stopnie wierzcholkow")
W6.3 (rozbior eulerowskiego na rozlaczne cykle)
W6.4 (charakteryzacja pol-eulerowskiego)
[T6.5 (algorytm Fleuryego)]

c: 6.1 - 6.3

p 7 ("Grafy hamiltonowskie")
cykl hamiltona, graf hamiltonowski, pol-hamiltonowski, 
T7.1 (tw Ore'go)

c: 7.1 - 7.3


R 4 ("Drzewa")

p9
drzewo, las
T9.1 + D (wielokrotna charakteryzacja drzew)
W9.2 (liczba krawedzi lasu)
drzewo spinajace(rozpinajace), rzad cyklicznosci, rzad rozciecia, dopelnienie
[T9.3 (przeciecia cykli i rozciec)]
zbior cykli fundamentalnych i rozciec fundamentalnych
c: 9.1 - 9.8

p 10 ("Zliczanie drzew")
T10.1 + D (Tw. Cayleya)
W10.2 (liczba drzew rozpinajacych grafu pelnego)
c: 10.1 - 10.2 [10.4]

p 11 ("Dalsze zastosowania")
Znajdowanie minimalnego drzewa rozpinajacego, przeszukiwanie w glab i wszerz, [obwody elektryczne], [czastki chemiczne]

c: 11.1 - 11.2, 11.4, [11.7], 11.8-11.9, [11.10]


R 5 ("Planarnosc")

p12 ("Grafy planarne")
graf planarny, rysunek plaski
T12.1 (nieplanarnosc K3,3 i K5)
T12.2 (Tw. Kuratowskiego)
T12.3 (inne sformulowanie Kuratowskiego - przez sciagalne)
liczba przeciec, grubosc grafu

c: 12.1 - 12.4, [12.5 - 12.6]

p 13 ("Twierdzenie Eulera")
sciana, sciana nieskonczona, rzut stereograficzny, 
T13.1 + D ("Formula Eulera" dla plaszczyzny)
graf wieloscianu
W13.2 + D
W13.3 + D ("Formula Eulera" na plaszczyznie dla niespojnych)
W13.4 + D ("m <= 3n - 6" a jak bez trojkatow to "m <= 2n - 4")
W13.5 + D (nieplanarnosc K3,3 i K5)
T13.6 + D (istnienie wierzcholka stopnia conajwyzej 5 w planarnym)
grubosc grafu

c: 13.1 - 13.2, [13.8]

p 15 ("Grafy dualne")
graf geometrycznie dualny
L15.1 (zachowanie formuly Eulera przy geometrycznej dualnosci)
T15.2 (idempotentnosc operacji dualnosci)
T15.3 (zaleznosc rozciec i cykli przy dualnosci)
W15.4 (j.w)
[graf abstrakcyjne dualny]
[T15.5] (symetrycznosc abstrakcyjnej dualnosci)
[T15.6]

c: 15.1 - 15.4, [15.5-15.9]


R 6 ("Kolorowanie grafow")

p 17 ("Kolorowanie wierzcholkow")
k-kolorowanie, k-chromatyczny, liczba chromatyczna + przyklady
T17.1 + D ( (d+1)-kolorowalnosc, gdzie d max stopien)
T17.2 (Tw. Brooksa)
T17.3 + D (6-kolorowalnosc planarnych prostych)
T17.4 + D (5-kolorowalnosc planarnych prostych)
T17.5 (4-kolorowalnosc planarnych prostych)

c: 17.1 - 17.2, [17.3-17.6], [17.8]

p 19 ("Kolorowanie map")
[T19.1 (2-kolorowalnosc map eulerowskich)]
[T19.2 (kolorowalnosc przy dualnosci)]
W19.3 (4-kolorowalnosc map)

c: 19.1 - 19.2

p 20 ("Kolorowanie krawedzi")
k-kolorowalnosc krawedzi, indeks chromatyczny, 
T20.1 (Tw. Vizinga)
[T20.2 + D] (indeks chromatyczny dla pelnych parzystych i nieparzystych)

c: 20.1 - 20.2, [20.3 - 20.5]

p 21 ("Wielomiany chromatyczne")
funkcja chromatyczna, 
T21.1 + D (rekurencyjna formula na wielomian chromatyczny)
[W21.2 + D] (funkcja chromatyczna prostego jest wielomianem)

c: 21.1, 21.3

R 7 ("Digrafy")

p 22 ("Definicje")
digraf, luki, szkielet, silna i slaba spojnosc, orientowalnosc
T22.1 + D (charakteryzacja orientowalnosci digrafu)
c: 22.1 - 22.4

p 23 ("Digrafy eulerowskie i turnieje")
digrafy eulerowskie, stopien wyjsciowy i wejsciowy, zrodlo, ujscie
T23.1 + D (charakteryzacja eulerowskich digrafow przez stopnie)
digrafy pol-eulerowskie i ich charakteryzacja, digrafy hamiltonowskie i pol-hamiltonowskie
turnieje
T23.3 (turnieje a hamiltonowskosc)
c: 23.1 - 23.3
[turniej przechodni i nierozkladalny, c: 23.6 - 23.7]


***
Oprocz tego do zakresu przedmiotu wchodza (spoza ksiazki Wilsona):

operacja iloczynu kartezjanskiego grafow

pojecia z sieci spolecznych: promien, srednica, ekscentrycznosc, etc.

rankingi w turniejach, agregacja turniejow i paradoks Condorcet'a

twierdzenia minimaksowe (część z nich jest w ksiazce Wilsona w r. 8) (tw. o kojarzeniu małżeństw, tw. Mengera, przykład dualności słabej i silnej, pokrycia a zbiory niezależne, Tw. Gallai)

przeplywy w sieciach (co to jest sieć przepływowa, co to jest przepływ, Tw. Forda Fulkersona, ścieżka powiększająca)

rankingi na grafach skierowanych: algorytm PageRank (3 sformułowania, warunki itstnienia i jednoznaczności, zastosowania)

p 24 (lancuchy markowa) (definicja, wzór na rozkład za k kroków, klasyfikacja stanów, tw. ergodyczne)


***

Oprocz tego do materialu naleza 3 tematy z algorytmow grafowych opracowane m.in. na cwiczeniach:

BFS, DFS i sortowanie topologiczne i zastosowania 
znajdowanie minimalnego drzewa rozpinajacego (alg. Kruskala i Prima)
znajdowanie najkrotszych sciezek (3 warianty: bez cykli, bez wag ujemnych, dowolne wagi)

Nalezy wiedziec dla kazdego algorytmu: jaka dokladnie ma specyfikacje (co dokladnie zaklada na wejsciu, co jest na wyjsciu), jaka ma zlozonosc czasowa, jak dziala na konkretnym grafie

(Material algorytmow grafowych mozna znalezc np. w podreczniku 
Cormen, Leiserson, Rivest "Wprowadzenie do algorytmow" w rozdzialach dotyczacych algorytmow grafowych. (lub dowolnym innym podreczniku do algorytmow) )

***