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