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

${\mathrm{\forall }}_{u,v\in V_i(G)}\{u,v\}\notin E(G)$

Linki zewnętrzne

• Szablon:MathWorld