Graf k-dzielny

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ą^[1].

Graf trzyczęściowy

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

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

taki, że

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

Przypisy

1. Reinhard Diestel: Graph Theory. Nowy Jork: 2000, s. 14, 43. ISBN 0-387-95014-1.

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.).