MAT 09. Obyčejné grafy

(U, H), U... konečná množina uzlů, H ⊆ {{u,v}, u,v ∈ U, u ≠ v} ... konečná množina hran

(U, H), U... konečná množina uzlů, H ⊆ {(u,v), u,v ∈ U, u ≠ v} ⊆ U×U ... konečná množina hran

(U, H, e), U... konečná množina uzlů, H... konečná množina hran, e: H → {(u,v), u,v ∈ U, u ≠ v}

obsahuje orientované i neorientované hrany

H ⊆ {(u,v), u,v ∈ U}

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}

sled, pro který i ≠ j ⇒ h_i ≠ h_j

tah, pro který i ≠ j ⇒ w_i ≠ w_j

H = Ø

H = {{u,v}, u,v ∈ U, u ≠ v}

sled, pro který u = v (uzavřený tah)

kružnice, která prochází každým uzlem grafu právě jednou

obsahuje Hamiltonovskou kružnici

⇔ existuje sled mezi libovolnými uzly u,v ∈ U

graf G' = (U', H'), U' ⊆ U, H' ⊆ H

podgraf, (u, v ∈ U' ∧ {u,v} ∈ H) ⇒ {u,v} ∈ H'

uzlově maximální souvislý faktor grafu

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

deg(u), počet hran incidentních s uzlem u, ∑deg(u) = 2|H|

bijektivní zobrazení φ: U1 → U2, {u,v} ∈ H1 ⇒ {φ(u),φ(v)} ∈ H2

isomorfismus, φ: U → U

obyčejný graf, jehož žádný podgraf není kružnicí

Obyčejný souvislý graf, jehož žádný podgraf není kružnicí, |H| = |U| - 1, každá hrana je mostem

podgraf G' = (U, H'), pokud je strom

G = (U, H, c), c: H → R, c(h) je cena hrany, c(G') = ∑c(u') cena podgrafu

K, kostra grafu s minimální cenou, c(K) ≤ c(L) pro každou kostru L

• 1. setřídění hran podle ceny
• 2. postupné přidávání nejlevnějších hran, tak aby nevznikla kružnice

• 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

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

graf je možno obarvit pomocí k barev, není nutné použít všechny

nejmenší hodnota k, pro kterou je graf k-obarvitelný

graf, který lze nakreslit v rovině tak, aby se jeho hrany protínaly pouze v jeho uzlech

planární graf nakreslený v rovině

dvourozměrná oblast ohraničená hranami rovinného grafu, |U| - |H| + |B| = 2

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ů