Dělení grafu

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

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^{\prime }=(V\cup \{z\},(E\setminus \{\{x,y\}\})\cup \{\{x,z\},\{z,y\}\})$

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

Související články

• Kuratowského věta