Dělení grafu

Z Wikipedie, otevřené encyklopedie

V teorii grafů je dělení grafu G takový graf, který vznikne z G posloupností operací dělení hrany.

[editovat] Dělení hrany

Nechť G = (V, E) je graf, e \in E; e = \{x, y\} a z \notin V Provedeme-li dělení hrany e, vznikne graf G', G' = \left(V \cup \{z\}, \left(E \setminus \{\{x, y\}\}\right) \cup \{\{x, z\}, \{z, y\}\}\right)

Hrana {x, y} rozdělená vrcholem z na hrany {x, z} a {z, y}
Hrana {x, y} rozdělená vrcholem z na hrany {x, z} a {z, y}

[editovat] Podívejte se také na