Teoria

Definicja matematyczna grafu skierowanego

to uporzadkowana para zbiorow G = (V, E) gdzie, V to zbiór wierzchołkow grafu, E to zbiór skierowanych krawędzi grafy G. Każda skierowana krawędź e (v,w) ze zbioru W to uporzadkowana para wierzchołków ze zbioru V, zwanych początkiem i końcem krawedzi e.

Czym jest stopień wierzchołka

to liczba krawędzi grafu incydentna do wierzchołka. Jest ob równy sumie liczb wszystkich łuków wchodzących, wychodzących, krawędzi i pętli

Lemat o uściskach dłoni

został wykazany przez Leandra Eulera w roku 1736. Fakt ten mówi, że w każdym grafie suma stopni wszystkich wierzchołków jest liczbą parzystą - dokładnie jest równa podwojonej liczbie krawędzi, gdyż każda krawędź zwiększa tę sumę o 2

Graf spójny

to taki graf, gdzie każda para wierzchołków jest połączona drogą

Graf dwudzielny

to taki graf gdzie zbior wierzcholkow grafu G moze byc podzielony na dwa zbiory rozlaczne A i B w taki sposob, by kazda krawedz G laczyla wierzcholek zbioru A z wierzcholkiem zbioru B.

Grafy platońskie

to grafy utworzone z wierzchołków i krawędzi pięciu wielomianów foremnych (platońskich) - czworościan, sześcian, ośmiościan, dwunastościan i dwudziestościan

Jaka jest liczba chrmatyczna dwudziestościanu i dlaczego?

Zgodnie z twierdzeniem o czterech barwach, graf ten (jest planarny) daje się zawsze pokolorować przy użyciu co najwyżej czterech kolorów.

Czym jest rozcięcie grafu

jest to zbiór rozspajający, którego żaden podzbiór właściwy nie jest już zbiorem rozspajającym.

Graf Hamiltonowski

to taki graf G, ktory zawiera sciezke przechodzaca przez kazdy wierzchołek dokladnie jeden raz

Średnica grafu

to inaczej diag(G) czyli maksymalna odleglosc miedzy wierzcholkami w tym grafie

Tw. charakteryzacja grafu Eulera

Jesli w grafie G kazdy wierzcholek ma stopien rowny co najmmuej 2, to graf G zawiera cykl. Graf spojny G jest grafem eulerowskim wtedy i tylko wtedy gdy stopien kazdego wierzcholka grafu G jest liczba parzysta

Drzewo i własności

to graf nieskierowany, ktory nie zawiera cykli i jest spojny. Wlasnosci to chociazby wysokosc i glebokosc.

Co to są cykle fundamentalne

Niech L oznacza pewien las rozpinający grafu G, Zauważmy, że dodanie jakiejkolwiek krawędzi z G nie należącej do L utworzy dokładnie jeden cykl. Taki cykl nazywamy cyklem fundamentalnym grafu G związanym z lasem rozpinającym L.

Twierdzenie Kuratowskiego

dany graf jest planarny wtedy i tylko wtedy, gdy nie zawiera podgrafu homeomorficznego z grafem K5 lub z grafem K3,3

Formuła Eulera

niech G bedzie rysunkiem plaskiego spojnego grafu i niech n, m i f oznaczaja liczbe wierzcholkow, krawiedzi i scian grafu G to: n - m + f = 2

Indeks chromatyczny

x’ (G) grafu G to najmniejsza taka liczba, że graf G jest k-kolorowalny (e)

Twierdzenie o kolorowaniu mapy

dla każdego skończonego grafu planarnego (V,E) możliwe jest przypisanie każdemu z jego wierzchołków jednej z czterech liczb 1, 2, 3 i 4 w taki sposób, aby żadne sąsiednie wierzchołki nie miały przyporządkowanej tej samej liczby.

Warunek istnienia cyklu Eulera w grafie skierowanym

graf musi być spójny (z pominięciem wierzchołków o stopniu 0 ) oraz każdy jego wierzchołek musi posiadać stopień parzysty.

Co to jest prawidłowy przepływ w sieci przepływowej?

wartosc przepływu nie moze byc wyzsza niz przepustowosc jakiegokolwiek przekroju. Jesli znajdziemy taki przepływ f i taki przekrój, ze wartosc przepływu równa jest przepustowosci tego przekroju, to mamy pewnosc, ze przepływ jest maksymalny

Tw Ford-Fulkerson

Wartosc maksymalnego przepływu w kazdej sieci zawsze równa jest minimalnej wartosci przekroju w tej sieci.

Wzor rekurencyjny na wieloman chromatyczny

P G(k) = P G−e (k) − P G\e (k)

Graf nieskierowany

to uporzadkowana para zbiorow G = (V, E) gdzie, V to zbiór wierzchołkow grafu, E to zbiór krawędzi grafy G. Każda krawędź e (v,w) ze zbioru E to uporzadkowana para wierzchołków ze zbioru V, zwanych początkiem i końcem krawedzi e.

Graf zerowy

to graf w ktorym zbiory V i E są puste

Graf prosty

to graf bez krawedzi wielokrotnych i pętli

Graf ogólny

to graf, w ktorym moga wystepowac krawedzie wielokrotne i petle

Izomorfizm grafu

istnieje wtedy gdy graf G jest izomorficzny z grafem H. Izomorfizm jest wtedy, gdy istnieje bijekcja wierzcholkow grafu H wierzcholkom grafu G, jesli dwa wierzcholki w jednym grafie sa polsczone to odpowiadajace im wierzcholki drugiego są tez połączone

Sąsiedztwo grafu

jest wtedy, gdy dwa wierzcholki V i W grafu G sa sasiednie, czyli istnieje krawedz VW ktora je laczy. Mowimy tez wtedy, ze wierzcholki VW sa incydentne

Stopien wierzcholka V grafu G

oznaczany symbolem deg(V). Jest loczba krawedzi incydentnych z V. Przy obliczeniu stopnia wierzcholka V przyjmujemy zwykle, że peyla W wierzcholka V podnosi stopien tego wierzcholka o 2

Woerzchołek izolowany

to wierzchołek stopnia 0

Wierzchołek koncowy

to wierzcholek stopnia 1

Ciag stopni grafu

sklada sie ze stopni wierzcholkow w kolejnosci wzrastajacej przy czym wzglednione sa w nim powtorzenia. Np ciag (1,1,2,2,3)

Podgrafem grafu G

nazwiemy graf, ktorego wszystkie wierzcholki naleza do V(G), a krawedzie do zbioru E(G)

Symbol G\e

oznacza graf otrzymany przez sciagniecie krawedzi e, czyli usuniecie jej i zidentyfikowanie jej koncow

Macierz sasiedztwa A

jest macierza wymiaru nxn, ktorej wyraz o indeksie i, j jest rowny liczbie krawedzi laczacych wierzcholek i z wierzcholkiem j

Macierz incydentna M

to macierz wymiaru nxm ktorej wyraz o indeksoe i, j jest rowny 1 jesli wierzcholek i jest incydentny z krawedzia j i rowny 0 w przeciwnym razie

Graf pusty

to graf, ktorego zbior krawedzi jest zbiorem pustym. Oznaczany jako N

Graf pełny

to graf prosty, w ktorym kazda para roznych wierzcholkow jest polaczona krawedzia. Graf pelny majacy n wierzcholkow oznaczymy symbolem Kn

Graf cykliczny

to graf spojny, regularny stopnia 2. Graf taki majacy n wierzcholkow oznaczamy symbolem Cn

Graf liniowy

to graf otrzymany z grafu cyklicznego przez usuniecie jednej krawedzi. Graf taki majacy n wierzcholkkw nazwiemy symbolem Pn

Kolo

to graf powstajacy z grafu Cn-1 poprzez polaczenie kazdego wierzcholka z nowym wierzcholkiem V. Oznaczany jest symbolem Wn

Graf regularny

to graf, w ktorym kazdy wierzcholek ma ten sam stopien. Jesli kazdy wierzcholek ma stopien r, to ten graf nazwiemy grafem reguralnym stopnia r lub grafem r-reguralnym

Graf kubiczny

to graf reguralny stopnia 3. Przykladem jest graf Petersona

Graf pelny dwudzielny

to graf dwudzielny, w ktorym kazdy wierzcholek zbioru A jest polaczony dokladnie jedna krawedzia z kazdym wierzcholkiem zbioru B. Graf pelny dwudzielny majacy r czarnych i s bialych wierzcholkow oznaczonym symbolem Krs

Kostka

graf reguralny dwudzielny K-kostka Qk nazywamy graf ktorego wierzcholki odpowiadaja ciagom (a1, a2,... ak) takim, ze kazdy wyrwz ai jest rowny 0 lub 1 i ktorego krawedzie lacza ciagi rozniace sie dokladnie jednym wyrazem. Ma 2^k wierz i k*2^k-1 kraw

Dopelnienie grafu G

graf G_ zawierajacy te same wierzcholki co graf G natomiast pomiedzy wierzcholkami grafu G_ istnieje krawedz wtrdy i tylko wtedy gdy pomoedzy tymi wierzcholkami nie istnieje krawedz w grafie G

Trasa (marszruta)

w danym grafie G nazywamy ciag krawedzi postaci v0v1, v1v2... vm-1vm w ktorym kazdy dwie kolejne krawedzie sa albo sasiednie albo incydentne. Wierzch v0 nazywamy poczatkiem a wierzch vm koncem trasy

Dlugosc trasy

nazwiemy liczbe krawedzi na trasie

Sciezka

to trasa, w ktorej wszystkie krawedzie sa rozne

Droga

to sciezka, w ktorej wierzcholki v0, v1, ..., vm sa rozne (z wyjatkiem rownosci v0=vm). Wtedy droga jest zamknieta

Cykl

to zamknieta sciezka zawierajaca co najmniej jedna krawedz

Zbior rozspajajacy grafu spojnego G

nazwiemy zbior krawedzi, ktorego usuniecie spowoduje, ze graf G przestanie byc spojny

Most

to rozciecie skladajace sie z jednej krawedzi

Spojnosc krawedziowa

nazywamy liczbe krawedzi nalezacych do najmniej licznego grafu G. Zatrm spojnosc jest najmniejsza liczba krawedzi, ktora nalezy usunac by graf przestal byc spojny

Zbiorem rozdzielajacym grafu spojnego G

nazwiemy zbior wierzcholkow ktorych usuniecie powoduje, że ten graf przestaje byc spojny

Spojnosc wierzcholkowa k(G)

jest to liczba elementow najmniej liczbego zbioru rozdzielajacego. Zatem k(G) jest najmniejsza liczba wierzcholkow, ktore nalezy usunac by graf powstaly w ten sposob z grafu G nie byl spojny

Graf eulerowski

to graf spojny G, jesli istnieje zamknieta sciezka zawierajaca kazda krawedz G

Cykl Eulera

to sciezka w grafie G zawierajaca kazda krawedz G

Graf poleulerowski

to taki graf, ktory nie jest grafem eulerowskim. Jesli istnieje sciezka zawierajaca kazda krawedz grafy G

Algorytm Fleuriego

to algorytm sluzacy do konstrukcji cyklu Eulera w danym grafie eulerowskim. Zaczynamy w dowolnym momencie i usuwamy z grafu przechodzone krawedzie i wierzcholki izolowane powstale w momencie usunicieca kraw. Do tego przechodzimy przez most tylko gdy trzeb

Sciezka Hamiltona

to sciezka w grafie przebiegajaca przez wszystkoe jego wierzcholki dokladnie jeden raz

Graf polhamiltonowski

to taki graf, jesli istnieje droga przechodzaca dokladnie jeden raz przez kazdy wierzcholek

Twierdzenie Diraca

jesli w grafie prostym G ktory ma n wierzcholkow gdzie n jest wieksze lub rowne 3, deg wieksze rowne n/2 dla kazdego wierzcholka V, to graf G jest hamiltonowski

Las

nazwiemy graf nie zawierajacy cykli

Twierdzenie wlasnosci drzew

Niech T bedzie grafem majacym n wierzcholkwo. Wtedy T jest drzewem. T nie zawoera cykli i ma n-1 krawedzi. Jest grafem spojnyn i kazda krawedz jest mostem. T jest grafem spojnym i ma n-1 kraw. Kazde 2 wierzcholki sa polaczone jedna droga

Drzewo spinajace

to drzewo, ktore zawiera wszystkie wierzcholki grafu G. Konstrukcja drzewa spinajacego polega na usunieciu z grafu tych krawedzi, ktore naleza do cykli

Las spinajacy

jesli G jest dowolnym gtafem, ktory ma n wierzcholkow, m ktawedzi i k skladowych, to mozemy zastosoeac te procedure do kazdej skladowej G. Tak otrzymany gtaf nazwiemy lasem spinajacym

Rzad cyklicznosci (liczba cyklimeryczna)

to laczna liczba krawedzi usunietych w czasie tego procesu

Rzad rozciecia (rzad spojnosci)

grafu G to liczba krawedzi w lesie spinajacym. Oznaczamy go symbolem E(G)

Dopelnieniem lasu spinajacego T grafu

nazwiemy graf otrzymany z grafu G przez usuniecie krawedzi nalezacacych do T

Twierdzenie Cayleya

istnieje n^n-2 roznych drzew oznaczonych majacych n wierzcholkow

Powiazanie

para drzew (A, B) gdzie drzewo B powstaje z drzewa A

Graf planarny

to graf, ktory mozna narysowac na plaszczyznie bez przecirc tzn tak, by zadne dwie krawedzie nie przecinaly sie na rysunku poza wierzcholkiem, z ktorym obie sa icydentne

Graf płaski

to rysunek grafy planarnego na plaszczyznie

Twierdzenie dotyczace grafow planarnych

grafy K3,3 i K5 nie sa planarne

Homeomorfizm grafow

to relacje rownosci w zbiorze grafow wiazace grafy jednoksztaltne. Dwa grafy G1 i H1 sa homeomorficzne jesli mozna je otrzymac z oewnego grafu G poprzez skonczona sekwensje operacji elementarnego podpodzialu

Liczba przeciec cv(G) grafu G

nazywamy najmniejsza liczbe przeciec, ktora musi wystapic gdy rysujemy graf G na plaszczyznie

Sciana grafu plaskiego

to czesc olaszczyzny wyznaczona przez krawedzie tego gradu. Kazdy graf plaski posiada jedna nieograniczona sciane zwana zewnetrzna oraz skonczona liczbe scian zamknietych

Graf nieskonczony G

sklada sie z nieskonczonego zbioru V(G) ktorego elementy nazywamy wierzchoklami i z nieskonczonej rodziny E(G) par nieuporzadkowanych elementow zbioru V(G) nazywanych krawedziami

Graf przeliczalny

to taki gdzie oba zbiory V(G) i E(G) sa przeliczalne

Lemat Königa

niech G bedzie spojnym lokalnie skonczonym grafem nieskonczonym. Wtedy dla kazdego wierzcholka V grafu G istnieje droga jednostajnie nieskonczona o poczatku v

Kolorowanie grafu

polega na przypisaniu okreslonym elementom skladowym grafu wybranych kolorow wedlug regul. Kolorowanie grafu jest zwiazane z przypisaniem wszystkim wierzcholkom w grafie jednej z wybranych barw w ten sposob by zadne dwa sasiednie wierz mialy inny kolor

Twierdzenie kolorowani grafu

jesli G jest grafem prostym w ktorym najwiekszym stopniem wierzcholka jest delta to graf g jest delta + 1 kolorowalng. Kazdy planarny graf jest 6-kolorowalny. Kazdy planarny graf prosty jest 4 kolorowany

Twierdzenie Brooksa

jesli G jest grafem prostym w ktorym najwiekszy stopien wierzcholka grafu G wynosi Delta (gdzie delta jest wieksze rowne 3) to graf G jest detla kolorowalng

Twierdzenie Vizinga

Jesli G jest grafem prostym, w ktorym najwiekszy stopien wierzcholka wynosi delta to delta jest mniejsze rowne X’(G) mniejsze delta + 1

Sciezka Eulerowska

to digraf spojny D nazywa eulerowskim jesli istnieje zamknieta sciezka zawoerajaca kazdy luk Digrafu D

Stopien wyjsciowy wierzcholka v digrafu D

nazwiemy liczbe lukow postaci vw i oznaczamy ja symbolem outdeg(v)

Stopien wejsciowy wierzcholka V

nazwiemy liczbe lukow digrafu D postaci wv. Oznaczymy ja symbolem indeg(v)

Twierdzenie o digrafach eulerowskich

digraf spojny jest digrafem eulerowskim wtedy i tylko wtedy, gfy dla kazdego wierzcholka v digrafu D zachodzi rownosc outdeg(v) = indeg(v)

Twierdzenie Ghouila-Houriego

niech D bedzie digrafem silnie spojnym majacym n wierzcholkow. Jesli outdeg(v) >= n/2 i indeg(v) >= n/2 dla kazdego wierzcholka v, to digraf D jest hamiltonowski

Turniej

digraf, w ktorym kazde dwa wierzcholki sa polaczone dokladnie jednym lukiem. Takich digrafow mozna utworzyc do przedstawiania wynikow turniejow tenisowych czy innych, w ktorych nie ma remisow

Twierdzenie Redeia-Camiona

kazdy turniej nie bedacy digrafem hamiltonowskim jest polhamiltonowski. Kazdy turniej silnie spojny jest hamiltonowski

Multigraf

graf w ktorym moga wystepowac krawedzie wielokrotne oraz petle

Hipergraf

rozszerzenie pojecia grafu. Jego krawedzie nazywane hiperkrawedziami moga byc incydentne do dowolnej liczby wierzcholkow

Silnie spojna skladowa

jest maksymalnym podgrafem, w ktorym istnieje sciezka pomiedzy kazdymi dwoma wierzcholkami. Jesli podgraf ten obejmuje wszystkie wierzcholki grafu to mowimy, ze dany graf skierowany jest silnie spojny

Silnie spojny skierowang graf G

jest wtedy, jesli istnieje sciezka pomiedzy kazda para wierzcholkow z V

Slabo spojny skierowany graf G = (V,E)

jest wtedy, jesli jego graf podstawowy taki sam graf ale bez kierunkow na krawedziach jest silnie spojny

Graf blokowy grafu G (BL(G))

wierzcholek BL(G) odpowiadajacy blokom G, krawedz laczy 2 wierzcholki w BL(G) wtedy i tylko wtedy gdy odpowiadajace im bloki maja wspolny wierzcholek w G

Odleglosc miedzy dwoma wierzcholkami v i W w grafie G

to odleglosc najlrotszej sciezki laczacej v i w

Ekscentrycznosc wierzcholka (ecc(V))

to makaymalna odleglosc od innego wierzcholka

Promien grafu (rad(G))

to minimalna ekscentrycznosc w tym grafie

Wierzcholek centralny

o minimalnej ekscentrycznosci ecc(v) = rad(G)

Centrum grafu (Z(G))

to graf indukowany na zbiorze wierzcholkiw centralnych grafu G

Kodowanie Prufera

pozwala w jednoznaczny sposob zakodowac dowolne drzewo etykietowane o n wierzcholkach za pomoca (n-2)elementowego ciagu liczb z zakresu [1, n]

Algorytm Prufera

majqc dane drzewo etykietoeane nkech b1 bedzie najmniejsza liczba przypisana lisciowi i niech a1 bedzie jedynym sasiadem tego liscia. Usuwamy ten lisc z drzewa z krawedzia i zapisujemy a1 jako piereszy element ciagu. Szukamy najmniejszej etykiety itd

Dekodowanie Prufera

kazdy (n-2)elementowy ciag liczb z zakresu [1, n] moze odkodowac otrzymujac n-wierzcholkowe drzewo etykietowane, przy czym dekodowanie jest roznowartosciowe

Algorytm dekodowania Prufera

Majac dany cisg (a1, an-2) znajdujemy najmniejsza liczbe b1 nalezaca do [1, n] ktore nie wystepuje w ciagu i laczymy kraweszie wierzcholka a1 i b1. Usuwamy a1 z ciagu a b1 pomijamy w dalszym rozwazaniu. Kontynuujemy analogicznie dodajac kolejne w i k do G

Indeks Wienera ds(G) dla grafu G

to suma wszystkich odleglosfi miedzy parami wierzcholkiw grafu

Ciag drzewowy

to ciagnliczb dodatnich naturalbych, gdy pewna jego permutacja stanowi ciag stopni pewnego drzewa

Drzewo etykietowane

to drzewa, ktorych wierzcholki maja etykiety bedace kolejnymi dodatnimi liczbami naturalnymi

Drzewo ukorzenione

to drzewo z pewnym wyroznionym wierzcholkiem nazywanym korzeniem drzewa

Glebokosc (poziom) depth(V) wierzcholka w drzewie ukorzenionym

to jego odleglosc od korzenia

Przodkiem wierzcholka V

nazywamy wierzcholek w lezacy na drodze od korzenia do v. V nazywamy wredy potomkiem wierzcholka w. Korzen nie ma przodka, lisc nie maja potomka). Przodek to rodzic(ojciec), potomek to dziecko(syn)

Blizniakiem

nazwiemy wierzcholek U majacy tego samego rodzica co V

Lisc w drzewie ukorzenionym

to wierzcholek bez dzieci

Poddrzewo wierzcholka V drzewa ukorzenionego T

to podgraf T bedacy drzewem ukorzenionym ktorego korzeniem jest V (jest tyle poddrzew v ile dzieci ma v)

Drzewo d-arne

to drzewo ukorzenione gdzie kazdy wierzcholek ma co najwyzej d dzieci, dla pewnej ustalonej liczby d nalezy do N+

Zupelne drzewo d-arne

to drzewo d-arne o mozliwie duzej liczbie wierzcholkow i wszystkie liscie roznia sie glebokosfia co najwyzej o 1

Drzewo uporzadkowane

to drzewo d-arne gdzie dla kazdego wierzcholka wszystkie dzieci maja przypiwany pewien porzadek liniowy

Porzadek standardowy drzewa uporzadkowanego

to uporzadkowanie liniowe wszystkich jego wierzcholkow rekurencyjnie po poziomach, a nastepnie zgodnie z porzadkiem dzieci

Drzewo binarne

to 2-arne drzewo uporzadkowane, w ktorym dodatkowo jest okreslane, ktore dziecko jest lewe. a ktore prawe (nie moga byc oba lewe ani oba prawe)

Pre-order

wypisz wierzcholki pierwszy raz po napotkaniu

Post-order

wypisz wierzcholki ostatni raz po napotkaniu

In-order

wypisz wierzcholki posiadajace lewego syna drugi raz go napotykajac, a kazdy inny poerwszy raz go napotykajac

Liczba Catalana

to licxba bn roznych drzew binarnych o n wierzcholkach bn = 1/n+1 (2n n)

Sciezka DFS

to fragment drzewa przeszukiwania DFS zbudowany do momentu, gdy jakis wierzcholek staje sie czarny

Zbior cykli fundamentalnych

to zbior cykli fundamentalnych zwiekszonych z lasem L

Algorytm Prima

zaczyna od wierzcholka startowego s i stopniowo powieksza drzewo rozpinajace. Niech S oznacza zbior wierzcholkow rosnacego drzewa. Poczatkowo S={s}. W kazdym kolejnym kroku dodawany jest wierzcholek bedacy drugim koncem najlzszejszej krawedzi ze zbioru

Graf zewnetrznie planarny

to graf ktory mozna narysowac na plaszczyznie bez przeciec krawedzi, ze wszystkie wierzcholki leza na zewnetrznym obrzezu

Grubosc t(G) grafu G

to najmniejsza liczba przezroczystych warstw zawierajacych rysunki plaskie podgrafu G ktore zlozone dalyby graf G. Jest to inna miara nieplanarnosci grafu

Genus grafu

to najnizszy mozliwy genus powierzchni na ktorej mozna dany graf narysowac bez przeciec krawedzi

Mapa

opisana jest przez graf G planarny 3-spojny. Wtedy sciany G odpowiadaja obszarom mapy krawedzi G granicom miedzy obszarami a wierzcholki G odpowiadaja punktom, w ktorym stykaja sie granice

Funkcja chromatyczna Pg(K) grafu G

nazywamy funkcje ktorej wartosc to liczba sposobow pokolorowania wierzcholkow grafu G (tak aby zadne sasiednie wierzcholki nie mialy tego samego koloru)

Szkielet digrafu

to graf nieskierowany powstaly z zastapienia kazdego luku (u,v) krawedzi nieskierowanych u,v. Szkielet dografy prostego nie musi byc grafem prostym

Digraf przeciwny do digrafu D

nazywamy digraf D^T w ktorym kazda krawedz zastepowana jest krawedzia przeciwna

Orientowalny graf nieskonczony G

to taki graf, ktory kazdy jego krawedz da sie zastaoic lukiem yak, że otrzymany digraf jest silnie spojny

Przechodzenie digrafu

to digraf, ktory dla dowolnych wierzcholkow u, v, w istnieje krawedz (u,w) i (v,w) implikuje istnienie krawedzi (u,w)

Domkniecie przechodnie digrafu D

to najmniejszy dograf D przechodni ktorego D jest podgrafem

Porzadek czesciwoy P= (V<=)

to para skladajaca sie ze zbioru elementow., relacji binaenej na zbiorze V, ktora jest zwrotna, asymetryczna i przechodnia

Digram Hassego danego porzadku czesciowego P=(V<=)

to rysunek grafu G = (V, <) taki ze elementy maksymalne sa na gorze, dla dowolnej pary wierzcholkow takich ze U < V wierzcholek U umieszczony ponizej V

Twierdzenie Dilwortha

minimalna liczba lancuchow niezbednych do pokrycia calego zbioru V rowna jest maksymalnej liczebnosci antylancuchow w P

Dualne twierdzenie Dilwortha

minimalna liczba antylancuchow niezbednych do pokrycia zbiorow V rowna jest licznosci lancucha w P

Kondensacja digrafu D (cond(D))

to taki graf, ktorego wierzcholki stanowia skladowe silnie spojne grafu D a luk ze skladowej C do skladowej C^T istnieje wtedy i tylko wtedy gdy istnieje krawedz (v,w) dla pewnych wierzcholkow v i w nalezacych do C^T

Nierozkladalnym turniejem

nazywamy turniej, w ktorym nie mozna podzielic jego zbioru wierzcholkow na 2 rozlaczne podzbiory V1 i V2 takie, ze luk pomiedzy tymi podzbiorani prowadsi z v1 do v2

Wynik wierzcholka V z turnieju

to jego stopien wyjsciowy (z iloma graczami wygral)

Ranking turnieju

to ciag nierosnacy wynikow turnieju odpowiadajacych wszystkim wierzchokkim tego turnieju

Dominacja stopnia k

zachodzi pomiedzy wierzcholkami V i W digrafy jesli iatnieje skierowana sciezka z V do W dlugosci K. K nalezy do N

Krol turnieju

to wierzcholek R taki, ze kazdy inny wierzcholek jest zdominowany stopania 1 lub 2 przez V

Glosowanie wiekszosciowe

polega na agregacji k turniejow w jeden zagregowany turniej T, taki ze obiekt V jest preferowany niz W (tzn jest krawedz v, w jesli V jest preferowany orzez wiekszosc glosujacych)

Page rank

jest to rozklad stacjonarny nieredukowalnego i acyklicznego lancucha Markowa

Skojarzenie w grafie G = VE

nazywamy podzbior M krawedzi grafu taki ze zadne dwa rozne krawedzie z M nie sa incydentne z tym samym wierzcholkiem

Paradoks Concorcet

polega na tym, ze nie jest tak, ze mimo, ze wszystkie preferencje sa racjonalne (czyli turnieje sa acykliczne) zagregowany turniej moze zawierac chkle a wiec nie da sie utrzymac rankingu preferencji glosujacych

Skojarzenie doskonale

to skojarzenie M takie ze kazdu wierzcholek z V jest incydentny z jakas krawedzia M

Skojarzenie calkowite

ze zbioru V1 w zbior V2 w grafie dwudzielnym G =(v1 u V2, E) to takie skojarzenie ze kazdy wierzcholek z v1 jest indydentny z pewna krawedzia z M

Trawersala rodziny F

nazywamy zbior roznych M elementow zbioru X wybranych po jednym z kazdego podzbioru Si

Trawesaly czesciowe rodziny F

nazywamy trawersale dowolnej podrodziny rodziny F

Pokryciem wierzcholkowym w grafie G = V,E

nazywamy taki podzbior X wierzcholkow ze kazda kraerdz z E jest incydentna z co najmnjej jednym wierzcholkjem z X

Pokryciem krawedziowym w grafie G = V,E

nazwiemy taki podzbior Y krawedzi, ze kazdy wierzcholek z V jest incydentny z co najmniej jedna krawdzi z Y

Droga przemienna wzgledem skojarzenia M

to taka droga prosta, ktorej krawedzie na przemian naleza i nie naleza do skojarzenia M

Droga powiekszona wzgledem skokarzenia M

to dowolna droga przemienna, ktora nie jest cyklem, taka ze jej konce nie sa koncami krawedzi z M

Twierdzenie Tutte

graf G = V, E ma skojarzenia doskonale jesli dla kazdego podzbioru wierzcholkow S <= V zachodzi g(G-S) <= |S|

Twierdzenie Kóning-Egenary

maksymalnie liczba jedynek nalezacych do tej samej linii rowna jest minimalnej liczbie linii zawierajacych wszystkie jedynki

Twierdzenie Mangana

w dowolnym grafie spojnym G dla dowolnych niesasiednich wierzcholkow u1, u2 maksymalnej liczbie drog rozlacznych krawedzi (wierzcholkow) laczacych u1 i u2 rowna jest minimalnej liczebnosci zbioru rozspajajacego ktory oddziela wierzcholki u1 i u2