Różnice

Różnice między wybraną wersją a wersją aktualną.

Odnośnik do tego porównania

przedmioty:matematyka_dyskretna_ii [2007/06/20 15:48] (aktualna)
Linia 1: Linia 1:
 +====== Matematyka dyskretna II ======
 +Definicje:
 +  * Graf nieskierowany <​m>​(W,​ K, γ), γ: K-> delim{lbrace}{delim{lbrace}{v,​w}{rbrace}:​ v,w in W }{rbrace}</​m>,​ skierowany, prosty (bez pętli i krawędzi wielokrotnych),​ dwudzielny, izomorfizm grafów <​m>​G_1=(W_1,​K_1,​γ_1),​ G_2=(W_2, K_2, γ_2)</​m>​ <​m>​{forall}under{k in K_1}{forall}under{a,​b in W_1}γ_1(k)=delim{lbrace}{a,​b}{rbrace} doubleleftright γ_2(β(k))=delim{lbrace}{α(a),​α(b)}{rbrace}</​m>,​ stopień wierzchołka w grafie, grafie skierowanym,​ macierz sąsiedztwa (liczba krawędzi łączących),​ macierz incydencji (0-1)
 +  * Droga, droga zamknięta, tor (bez powtarzających się krawędzi), łuk (bez powtarzających się wierzchołków),​ cykl
 +  * Tor eulerowski (przez wszystkie krawędzie),​ otwarty tor eulerowski, graf eulerowski, graf półeulerowski
 +  * Droga Hamiltona (przez wszystkie wierzchołki),​ cykl Hamiltona, graf hamiltonowski,​ graf półhamiltonowski
 +  * Graf acykliczny, graf spójny, składowa, most, drzewo, drzewo spinające, las
 +  * Graf z wagami, waga drogi, zagadnienie najkrótszej drogi, problem komiwojażera,​ problem chińskiego listonosza
 +  * Transwersala,​ skojarzenie w grafie dwudzielnym,​ rząd wyrazowy macierzy, macierz incydencji rodziny zbiorów
 +  * Sieć przepływowa (G,c,s,t) (G-graf skier. prosty, c-przepustowość,​ s,t - źródło i ujście), przepustowość <​m>​c:​W*W right delim{[}{0,​infty}{]}</​m>,​ przepływ <​m>​f:​W*W right bbR</​m>,​ wartość przepływu, sieć residualna, łuk powiększający,​ przekrój, przpustowość przekroju, przepływ netto przez przekrój
 +
 +Twierdzenia:​
 +  * lemat o uściskach dłoni\\ (suma stopni wszystkich wierzchołków w grafie jest zawsze parzysta)
 +  * twierdzenie o zależności między torami a łukami
 +  * twierdzenie o najkrótszej drodze łączącej wierzchołki
 +  * twierdzenie o istnieniu łuku łączącego wierzchołki
 +  * twierdzenie o torach w grafie acyklicznym
 +  * twierdzenie charakteryzujące krawędzie nie będące mostami
 +  * twierdzenia charakteryzujące grafy eulerowskie i półeulerowskie\\ graf jest eulerowski, gddy wszystkie jego wierzchołki mają stopień parzysty.\\ graf jest pół eulerowski, gddy dokładnie dwa jego wierzchołki mają stopień nieparzysty
 +  * twierdzenia podające warunki dostateczne istnienia cyklu Hamiltona
 +  * twierdzenie o istnieniu drzewa spinającego
 +  * twierdzenia charakteryzujące drzewa
 +  * twierdzenie o liczbie wierzchołków drzewa
 +  * twierdzenie Cayley'​a\\ Istnieje <​m>​n^{n-2}</​m>​ różnych drzew oznakowanych o n wierzchołkach ​
 +  * twierdzenie Halla o małżeństwach
 +    * wersja klasyczna
 +    * wersja grafowa
 +    * wersja transwersalowa
 +    * wersja macierzowa
 +  * twierdzenie Koniga-Egervary'​ego\\ rząd wyrazowy macierzy zerojedynkowej jest równy najmniejszej liczbie linii zawierających w sumie wszystkie jedynki tej macierzy
 +  * twierdzenie o maksymalnym przepływie i minimalnym przekroju\\ Maksymalny przepływ w sieci przepływowej jest równy minimalnemu przekrojowi
 +
 +Algorytmy:
 +  * Znajdowania cyklu Euler'​a:​
 +    * Algorytm Fleury'​ego
 +  * Rozwiązywania problemu komiwojażera:​
 +    * Algorytm Najkrótszej wstawki
 +  * Znajdowania minimalnego drzewa spinającego:​
 +    * Algorytm Prima
 +    * Algorytm Kruskala
 +  * Znajdowania maksymalnego przepływu:
 +    * Algorytm Forda-Fulkersona
 +  * Znajdowania drogi o najmniejszej wadze:
 +    * Algorytm Dijkstry
  
Recent changes RSS feed Creative Commons License Donate Minima Template by Wikidesign Driven by DokuWiki