MAT 09. Obyčejné grafy

Card Set Information

Author:
hrbi
ID:
222347
Filename:
MAT 09. Obyčejné grafy
Updated:
2013-06-04 06:54:09
Tags:
mat
Folders:

Description:
msz 2013
Show Answers:

Home > Flashcards > Print Preview

The flashcards below were created by user hrbi on FreezingBlue Flashcards. What would you like to do?


  1. Obyčejný graf
    (U, H), U... konečná množina uzlů, H ⊆ {{u,v}, u,v ∈ U, u ≠ v} ... konečná množina hran
  2. Orientovaný graf
    (U, H), U... konečná množina uzlů, H ⊆ {(u,v), u,v ∈ U, u ≠ v} ⊆ U×U ... konečná množina hran
  3. Obecný graf
    (U, H, e), U... konečná množina uzlů, H... konečná množina hran, e: H → {(u,v), u,v ∈ U, u ≠ v}
  4. Smíšený graf
    obsahuje orientované i neorientované hrany
  5. Graf se smyčkami
    H ⊆ {(u,v), u,v ∈ U}
  6. Sled
    posloupnost (u=w_0,h_1,w_1,h_2,...,h_n,w_n=v) taková, že w_i ∈ U, h_i ∈ H, hi = {w_i-1, w_i}
  7. Tah
    sled, pro který i ≠ j ⇒ h_i ≠ h_j
  8. Cesta
    tah, pro který i ≠ j ⇒ w_i ≠ w_j
  9. Diskrétní graf
    H = Ø
  10. Úplný graf
    H = {{u,v}, u,v ∈ U, u ≠ v}
  11. Kružnice
    sled, pro který u = v (uzavřený tah)
  12. Hamiltonovská kružnice
    kružnice, která prochází každým uzlem grafu právě jednou
  13. Hamiltonovský graf
    obsahuje Hamiltonovskou kružnici
  14. Souvislý graf
    ⇔ existuje sled mezi libovolnými uzly u,v ∈ U
  15. Podgraf
    graf G' = (U', H'), U' ⊆ U, H' ⊆ H
  16. Faktor
    podgraf, (u, v ∈ U' ∧ {u,v} ∈ H) ⇒ {u,v} ∈ H'
  17. Komponenta
    uzlově maximální souvislý faktor grafu
  18. Most
    hrana h = {u,v}, jejímž odstraněním se zvýší počet komponent v grafu, (u,h,v) je jediná cesta mezi uzly u a v
  19. Stupeň vrcholu
    deg(u), počet hran incidentních s uzlem u, ∑deg(u) = 2|H|
  20. Isomorfismus obyčejných grafů
    bijektivní zobrazení φ: U1 → U2, {u,v} ∈ H1 ⇒ {φ(u),φ(v)} ∈ H2
  21. Automorfismus
    isomorfismus, φ: U → U
  22. Les
    obyčejný graf, jehož žádný podgraf není kružnicí
  23. Strom
    Obyčejný souvislý graf, jehož žádný podgraf není kružnicí, |H| = |U| - 1, každá hrana je mostem
  24. Kostra grafu
    podgraf G' = (U, H'), pokud je strom
  25. Oceněný graf
    G = (U, H, c), c: H → R, c(h) je cena hrany, c(G') = ∑c(u') cena podgrafu
  26. Minimální kostra
    K, kostra grafu s minimální cenou, c(K) ≤ c(L) pro každou kostru L
  27. Kruskalův algoritmus
    • 1. setřídění hran podle ceny
    • 2. postupné přidávání nejlevnějších hran, tak aby nevznikla kružnice
  28. Primův algoritmus
    • 1. začátek v libovolném uzlu
    • 2. postupné přidávání hran s nejmenší cenou tak, aby byl graf souvislý a nevznikla kružnice
  29. Obarvený graf
    každému uzlu je přidělena barva tak, že dvěma uzlům spojených hranou jsou přiřazeny různé barvy
  30. k-obarvitelný graf
    graf je možno obarvit pomocí k barev, není nutné použít všechny
  31. Chromatické číslo grafu
    nejmenší hodnota k, pro kterou je graf k-obarvitelný
  32. Planární graf
    graf, který lze nakreslit v rovině tak, aby se jeho hrany protínaly pouze v jeho uzlech
  33. Rovinný graf
    planární graf nakreslený v rovině
  34. Buňka rovinného grafu
    dvourozměrná oblast ohraničená hranami rovinného grafu, |U| - |H| + |B| = 2
  35. Homeomorfní grafy
    grafy shodné až na uzly stupně 2, tedy získané postupným rozpůlením některých hran a vložením nových uzlů

What would you like to do?

Home > Flashcards > Print Preview