— — Operace (lokální úpravy) na grafech

Operace (lokální úpravy) na grafech

Definujeme si G = (V, E).

(i) Odebrání hrany e ∈ E: G → G − e = (V, E \ {e}). (ii) Přidání hrany e ∈ \binom{V}{2} \ E: G → G + e = (V, E ∪ \{e\}). (iii) Odebrání vrcholu v ∈ V: G → G − v = (V \ {u}, {e ∈ E, v ∉ e}). (iv) Dělení hrany e = {x, y} ∈ E:

G → G % e = (V ∪ {z}, (E \ {e}) ∪ {{x, z}, {y, z}})

G′ je dělení grafu G, pokud: G′ dostaneme z G postupným opakováním operace dělení hrany. Ekvivalentně — G′ dostaneme z G nahrazením hran cestami délek ≥ 1.

Příklad:

o ------ o o ----- o

— “ — “

— “ ---¿ o o

—  “  —  “
o  o  o  o

/L:1 1