Pozostale

 0    53 cartonașe    adamomasz
printează joacă Testează-te
 
Întrebare - Răspuns -
Algorytm Kruskala
începe să înveți
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
începe să înveți
graf, który można narysować na płaszczyźnie bez przecięć krawędzi.
Rysunek płaski
începe să înveți
rysunek grafu planarnego taki, gdzie nie przecinają się krawędzie.
Liczba przecięć -
începe să înveți
cr(G) - najmniejsza możliwa liczba przecięć krawędzi w dowolnym rysunku grafu G na płaszczyźnie. Miara “nieplanarności” grafu.
Grubość grafu
începe să înveți
najmniejsza liczba „przezroczystych warstw” zawierających rysunki płaskie podgrafów G, które „złożone” dałyby graf G.
Ściana
începe să înveți
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
începe să înveți
jedyna ściana nieograniczona (powyżej: f4 ).
Rzut stereograficzny
începe să înveți
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ń,
jaki rzucałby rysunek gdyby umieścić punktowe źródła światła w wierzchołku sfery
Graf wielościanu
începe să înveți
graf utworzony przez wierzchołki i krawędzie wielościanu
Graf geometrycznie dualny G*
începe să înveți
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
începe să înveți
- 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
începe să înveți
- 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
începe să înveți
gdzie liczba chromatyczna 𝜒(G) wynosi k.
Liczba chromatyczna 𝜒(G)
începe să înveți
najmniejsza liczba k taka, że graf jest k-kolorowalny.
k-kolorowalnosc krawędzi
începe să înveți
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)
începe să înveți
najmniejsza taka liczba k, że graf G jest k-kolorowalny(e), czyli krawędziowo.
Funkcja chromatyczna,
începe să înveți
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 -
începe să înveți
diam(G): maksymalna odległość między wierzchołkami w tym grafie.
Ekscentryczność wierzchołka
începe să înveți
ecc(v): maksymalna odległość od innego wierzchołka.
Promień grafu
începe să înveți
rad(G): minimalna ekscentryczność wierzchołka w tym grafie.
Wierzchołek centralny
începe să înveți
o minimalnej ekscentryczności
Centrum grafu
începe să înveți
graf indukowany na zbiorze wierzchołków centralnych grafu G.
Dualność
începe să înveți
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
începe să înveți
- taki podzbiór X wierzchołków, że żadne dwa różne wierzchołki z X nie są sąsiednie.
. Pokrycie wierzchołkowe
începe să înveți
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
începe să înveți
- 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+,
przy czym indeg(s) = 0 i outdeg(t) = 0. Wagę c(e) krawędzi e ∈ E nazywamy przepustowością krawędzi.
Przepływ
începe să înveți
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)
dla każdego wierzchołka poza s i t zachodzi: prawo zachowania przepływu w węzłach
Ścieżka powiększająca
începe să înveți
ścieżka powiększająca dany przepływ f to taka ścieżka nieskierowana (tzn. krawędzie
● każda krawędź e skierowana od źródła do ujścia jest nienasycona (krawędź nasycona to spełniająca warunek: f(e) = c(e)) ● dla każdej krawędzi ścieżki e skierowanej przeciwnie (od ujścia do źródła) f (e) > 0.
Łańcuchy Markowa
începe să înveți
macierz prawdopodobieństwa przejść P wymiaru n x n wraz z n-wymiarowym wektorem wierszowym x
Klasyfikacja stanów (Markowa)
începe să înveți
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
• pochłaniający wtedy i tylko wtedy gdy prawdopodobieństwo przejścia w jednym kroku z v do innego stanu wynosi 0 • okresowy o okresie 1 < τ ∈ N wtedy i tylko wtedy gdy powrócić do stanu v można tylko po liczbie kroków będącej wielokrotnością τ
Liczba drzew rozpinających grafu pełnego)
începe să înveți
Graf pełny Kn ma dokładnie n n-2 drzew rozpinających
charakteryzacja dwudzielnych przez cykle)
începe să înveți
Jeżeli graf jest dwudzielny, to nie zawiera cykli nieparzystych!
Tw. Eulera "charakteryzacja grafów eulerowskich przez stopnie wierzchołków)
începe să înveți
Graf spójny jest Eulerowski wtedy i tylko wtedy, gdy każdy jego wierzchołek ma stopień parzysty.
Tw. Orego):
începe să înveți
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
începe să înveți
Istnieje n n-2 różnych n-wierzchołkowych drzew etykietowanych.
Kodowanie prufera
începe să înveți
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 ):
începe să înveți
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):
începe să înveți
Dany graf jest planarny ⇔ nie zawiera podgrafu homeomorficznego z grafem K5 lub z grafem K3,3.
"Formuła Eulera" dla płaszczyzny):
începe să înveți
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)
începe să înveți
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)
începe să înveți
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)
începe să înveți
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ń)
începe să înveți
Jeśli G jest grafem prostym, w którym największym stopniem wierzchołka jest Δ, to graf G jest (Δ+1)-kolorowalny
Tw. Brooksa)
începe să înveți
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
începe să înveți
Każdy planarny graf prosty jest 6-kolorowalny.
2-kolorowalność map eulerowskich)]
începe să înveți
Mapa G jest 2-kolorowalna(f) ⇔ graf G jest grafem eulerowskim.
k-kolorowalność(f)
începe să înveți
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)]
începe să înveți
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
începe să înveți
: 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
începe să înveți
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 -
începe să înveți
Wartość maksymalnego przepływu w każdej sieci zawsze równa jest minimalnej wartości przekroju w tej sieci.
Przekrój sieci
începe să înveți
rozcięcie w grafie reprezentującym sieć, które oddziela źródło od ujścia.
Twierdzenie o kojarzeniu małżeństw
începe să înveți
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.

Trebuie să te autentifici pentru a posta un comentariu.