====== 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

przedmioty/matematyka_dyskretna_ii.txt · ostatnio zmienione: 2007/06/20 15:48 (edycja zewnętrzna)
Recent changes RSS feed Creative Commons License Donate Minima Template by Wikidesign Driven by DokuWiki