Graf k-dzielny

Graf trzyczęściowy

Graf k-dzielny – naturalne rozszerzenie klasy grafów dwudzielnych - jest to graf, którego zbiór wierzchołków można podzielić na k parami rozłącznych podzbiorów takich, że żadne dwa węzły należące do tego samego zbioru nie są połączone krawędzią.

Innymi słowy, jeżeli $\!G$ jest grafem k-dzielnym, to na zbiorze jego wierzchołków $\!V(G)$ istnieje podział:

$\!V(G)\ =\ \bigcup _{i\in 1\cdots k}V_{i}(G)$

taki, że

$\!\forall _{u,v\in V_{i}(G)}\{u,v\}\notin E(G)$

Linki zewnętrzne

• Eric W.E.W. Weisstein Eric W.E.W., k-Partite Graph, [w:] MathWorld, Wolfram Research [dostęp 2020-12-12]  (ang.).