Multipartitni graf

U teoriji grafova, delu matematike, k-partitni graf je graf čija temena su ili mogu biti podeljena na k različitih nezavisnih sklopova. Ekvivalentno tome, to je graf koji može biti obojen s k boja, tako svake dve krajnje tačke ivice nemaju istu boju. Kada je k = 2 to su bipartitni grafovi, a kada je k = 3 nazivaju se tripartitni grafovi.

Bipartitni grafovi mogu biti priznati u polinomijalnom vremenu ali, za svako k > 2 to je np-kompletan (np-complete), dat je neobojen graf, da bi se testiralo da li je k-partitan. Međutim, u nekim primenama teorije grafova, k-partitni graf može biti dat kao unos za računanje sa već određenim svojim bojama; ovo može da se desi kada sklopovi temena u grafu prezentuju različite tipove objekata. Na primer, folksnomije (folksnomies) su modelovane matematički sa tripartitnim grafovima u kojima tri sklopa temena u grafu prezentuju korisnike sistema, sredstva koja korisnici označavaju, i oznake koje su korisnici primenili na resursima.

The complete tripartite graph K_2,2,2, the graph of the octahedron

Kompletni k-partitni graf je k-partitni graf u kome postoji ivica između svakog para temena iz različitih nezavisnih sklopova. Ovi grafovi su opisani s velikim slovom k, kao notacijom i u indeksu slova se piše sekvenca veličine svakog nezavisnog sklopa u tom delu. Na primer, k2,2,2 je kompletni tripartitni graf pravilnog oktaedra, koji može biti podeljen na tri nezavisna sklopa, od kojih se svaki sastoji od dva suprotna temena. Kompletni multipartitni graf je graf koji je kompletan k-partitni za neko k. Turanovi grafovi su specijalni slučajevi kompletnih multipartitnih grafova u kojima se svaka dva nezavisna sklopa razlikuju po veličini za najviše jedno teme. Kompletni k-partitni grafovi i kompletni multipartitni grafovi su specijalni slučajevi kografova (cographs), i mogu biti priznati u polinomijalnom vremenu čak i kad deo nije obezbeđen kao deo unosa.