Pozostale

Algorytm Kruskala

union-find Rozpatruje krawędzie w kolejności niemalejących wag i dodawaj do T te, które nie tworzą cyklu z poprzednio dodanymi, pozostałe odrzucaj, do momentu, gry T nie tworzy drzewa rozpinającego.

Graf planarny

graf, który można narysować na płaszczyźnie bez przecięć krawędzi.

Rysunek płaski

rysunek grafu planarnego taki, gdzie nie przecinają się krawędzie.

Liczba przecięć -

cr(G) - najmniejsza możliwa liczba przecięć krawędzi w dowolnym rysunku grafu G na płaszczyźnie. Miara “nieplanarności” grafu.

Grubość grafu

najmniejsza liczba „przezroczystych warstw” zawierających rysunki płaskie podgrafów G, które „złożone” dałyby graf G.

Ściana

dowolny maksymalny obszar spójny nie będący częścią grafu (krawędzią ani wierzchołkiem) w tym rysunku płaskim.

Ściana nieskończona

jedyna ściana nieograniczona (powyżej: f4 ).

Rzut stereograficzny

G=kładziemy sferę na płaszczyźnie ● Rysujemy dowolny obiekt na sferze (Uwaga: nie można tylko rysować po wierzchołku sfery) ● Rzut stereograficzny stanowi cień,

Graf wielościanu

graf utworzony przez wierzchołki i krawędzie wielościanu

Graf geometrycznie dualny G*

zastępujemy każdą ścianę G wierzchołkiem w G* ● 2 wierzchołki w G* są połączone krawędzią w G* ⇔ istnieje odpowiadająca im krawędź w G, która rozgranicza odpowiednie ściany w G.

Graf abstrakcyjnie dualny

- czyli istnieje taka wzajemnie jednoznaczna relacja między zbiorami krawędzi G i G ∗, że cykle w G odpowiadają krawędziom w G ∗

k-kolorowanie wierzchołków

- Przez kolorowanie wierzchołków grafu G nazywamy takie przyporządkowanie każdemu z jego wierzchołków pewnego koloru, reprezentowanego umownie przez liczbę naturalną, że żadne dwa sąsiednie wierzchołki nie mają przyporządkowanego tego samego koloru. G

. k-chromatyczny

gdzie liczba chromatyczna 𝜒(G) wynosi k.

Liczba chromatyczna 𝜒(G)

najmniejsza liczba k taka, że graf jest k-kolorowalny.

k-kolorowalnosc krawędzi

Graf jest k-kolorowalny(e) (k-kolorowalny krawędziowo) jeżeli jego krawędzie można pokolorować tak, że żadne dwie krawędzie incydentne z tym samym wierzchołkiem nie mają tego samego koloru.

Indeks chromatyczny𝜒’(G)

najmniejsza taka liczba k, że graf G jest k-kolorowalny(e), czyli krawędziowo.

Funkcja chromatyczna,

Funkcją chromatyczną PG (k) grafu G nazywamy funkcję, której wartość to liczba sposobów pokolorowania wierzchołków grafu G przy pomocy k kolorów

Średnica grafu -

diam(G): maksymalna odległość między wierzchołkami w tym grafie.

Ekscentryczność wierzchołka

ecc(v): maksymalna odległość od innego wierzchołka.

Promień grafu

rad(G): minimalna ekscentryczność wierzchołka w tym grafie.

Wierzchołek centralny

o minimalnej ekscentryczności

Centrum grafu

graf indukowany na zbiorze wierzchołków centralnych grafu G.

Dualność

Istnieją zagadnienia optymalizacyjne posiadające specyficzną cechę „dualności”, tzn. zadanie maksymalizacji pewnej funkcji jest równoważne zagadnieniu minimalizacji innej funkcji.

. Zbiór niezależny

- taki podzbiór X wierzchołków, że żadne dwa różne wierzchołki z X nie są sąsiednie.

. Pokrycie wierzchołkowe

w grafie G = (V, E) nazywamy taki podzbiór X wierzchołków V, że każda krawędź z E jest incydentna z co najmniej jednym wierzchołkiem z X.

Sieć przepływowa

- Sieć przepływowa ze źródłem s i ujściem t to graf skierowany G = (V, E) z wymiernymi, nieujemnymi wagami na krawędziach danymi przez funkcję (przepustowość) c: E → Q+,

Przepływ

Przepływ w sieci G z funkcją przepustowości c: E → Q+ to taka funkcja f: E → Q+ ∪ {0}, która spełnia warunki: ● f (e) ≤ c(e) dla każdej krawędzi e ∈ E (nieprzekraczalność przepustowości)

Ścieżka powiększająca

ścieżka powiększająca dany przepływ f to taka ścieżka nieskierowana (tzn. krawędzie

Łańcuchy Markowa

macierz prawdopodobieństwa przejść P wymiaru n x n wraz z n-wymiarowym wektorem wierszowym x

Klasyfikacja stanów (Markowa)

powracający wtedy i tylko wtedy, gdy będąc w nim w momencie t prawdopodobieństwo ponownego bycia w nim w pewnym czasie t’ > t wynosi 1 (na pewno wrócimy) • chwilowy wtedy i tylko wtedy gdy nie jest powracający

Liczba drzew rozpinających grafu pełnego)

Graf pełny Kn ma dokładnie n n-2 drzew rozpinających

charakteryzacja dwudzielnych przez cykle)

Jeżeli graf jest dwudzielny, to nie zawiera cykli nieparzystych!

Tw. Eulera "charakteryzacja grafów eulerowskich przez stopnie wierzchołków)

Graf spójny jest Eulerowski wtedy i tylko wtedy, gdy każdy jego wierzchołek ma stopień parzysty.

Tw. Orego):

Jeśli graf prosty G ma n wierzchołków (gdzie n ≥ 3) oraz deg(v) + deg(w) ≥ n dla każdej pary wierzchołków niesąsiednich v i w, to graf G jest hamiltonowski.

Tw. Cayleya

Istnieje n n-2 różnych n-wierzchołkowych drzew etykietowanych.

Kodowanie prufera

1. znalezienia liscia ktory ma najmniejsza etykiete, dodanie sasiada do zbioru S i usuniecie z grafu tego liscia, powtarzaj az graf stanie sie K2

(Nieplanarność K3,3 i K5 ):

Grafy K5 i K3,3 nie są planarne (tzw. Grafy Kuratowskiego) (dowód polega na bezpośrednim sprawdzeniu wszystkich możliwości narysowania) Wniosek: Jeśli graf zawiera graf Kuratowskiego jako podgraf to jest nieplanarny

(Tw. Kuratowskiego):

Dany graf jest planarny ⇔ nie zawiera podgrafu homeomorficznego z grafem K5 lub z grafem K3,3.

"Formuła Eulera" dla płaszczyzny):

Niech G będzie rysunkiem płaskim spójnego grafu płaskiego i niech n, m i f oznaczają odpowiednio liczbę wierzchołków, krawędzi i ścian grafu G. Wtedy n - m + f = 2

Idempotentność operacji dualności)

Jeśli graf G jest spójnym grafem płaskim, to graf G** jest izomorficzny z grafem G.

Zależność rozcięć i cykli przy dualności)

Niech G będzie grafem planarnym i niech G* będzie grafem geometrycznie dualnym do grafu G. Wówczas zbiór krawędzi grafu G tworzy cykl w G ⇔ odpowiadający mu zbiór krawędzi grafu G* jest rozcięciem w G*.

Symetryczność abstrakcyjnej dualności)

Jeżeli G* jest grafem abstrakcyjnie dualnym do grafu G, to graf G jest abstrakcyjnie dualnym do grafu G*

(d+1)-kolorowalność, gdzie d max stopień)

Jeśli G jest grafem prostym, w którym największym stopniem wierzchołka jest Δ, to graf G jest (Δ+1)-kolorowalny

Tw. Brooksa)

eśli G jest spójnym grafem prostym, niebędącym grafem pełnym, i jeśli największy stopień wierzchołka grafu G wynosi Δ (gdzie Δ ≥ 3), to graf G jest Δ-kolorowalny.

6-kolorowalność planarnych prostych

Każdy planarny graf prosty jest 6-kolorowalny.

2-kolorowalność map eulerowskich)]

Mapa G jest 2-kolorowalna(f) ⇔ graf G jest grafem eulerowskim.

k-kolorowalność(f)

mapa jest k-kolorowalna(f) ⇔ jej ściany można tak pokolorować k kolorami, że po obu stronach każdej krawędzi jest inny kolor

kolorowalność przy dualności)]

Niech G będzie grafem planarnym bez pętli i niech G* będzie grafem geometrycznie dualnym do grafu G. Wówczas graf G jest k-kolorowalny(v) ⇔ gdy graf G* jest k-kolorowalny(f). Wniosek: Każda mapa jest 4-kolorowalna

Tw. Vizinga

: Jeśli G jest grafem prostym, w którym największy stopień wierzchołka wynosi Δ, to: Δ ≤ χ ’(G) ≤ Δ+1 (gdzie χ ’(G) to indeks chromatyczny).

algorytm Fleury'ego

1. Zacznij cykl w dowolnym wierzchołku a. Usuwaj z grafu przechodzone krawędzie i wierzchołki izolowane powstające w wyniku usuwania tych krawędzi b. W każdym momencie przechodź przez most tylko wtedy, gdy nie masz innej możliwości. u

Tw. Forda Fulkersona -

Wartość maksymalnego przepływu w każdej sieci zawsze równa jest minimalnej wartości przekroju w tej sieci.

Przekrój sieci

rozcięcie w grafie reprezentującym sieć, które oddziela źródło od ujścia.

Twierdzenie o kojarzeniu małżeństw

Warunek konieczny i wystarczający rozwiązania problemu kojarzenia małżeństw to by dla każdego zbioru k dziewcząt ze zbioru V1 wszystkie one znały co najmniej k chłopców ze zbioru V2.