Мултипартитни граф

У теорији графова, делу математике, к-партитни граф је граф чија темена су или могу бити подељена на к различитих независних склопова. Еквивалентно томе, то је граф који може бити обојен с к боја, тако сваке две крајње тачке ивице немају исту боју. Када је к = 2 то су бипартитни графови, а када је к = 3 називају се трипартитни графови.

Бипартитни графови могу бити признати у полиномијалном времену али, за свако k > 2 то је нп-комплетан (нп-цомплете), дат је необојен граф, да би се тестирало да ли је к-партитан. Међутим, у неким применама теорије графова, к-партитни граф може бити дат као унос за рачунање са већ одређеним својим бојама; ово може да се деси када склопови темена у графу презентују различите типове објеката. На пример, фолксномије (фолксномиес) су моделоване математички са трипартитним графовима у којима три склопа темена у графу презентују кориснике система, средства која корисници означавају, и ознаке које су корисници применили на ресурсима.

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

Комплетни к-партитни граф је к-партитни граф у коме постоји ивица између сваког пара темена из различитих независних склопова. Ови графови су описани с великим словом к, као нотацијом и у индексу слова се пише секвенца величине сваког независног склопа у том делу. На пример, к2,2,2 је комплетни трипартитни граф правилног октаедра, који може бити подељен на три независна склопа, од којих се сваки састоји од два супротна темена. Комплетни мултипартитни граф је граф који је комплетан к-партитни за неко к. Туранови графови су специјални случајеви комплетних мултипартитних графова у којима се свака два независна склопа разликују по величини за највише једно теме. Комплетни к-партитни графови и комплетни мултипартитни графови су специјални случајеви кографова (цограпхс), и могу бити признати у полиномијалном времену чак и кад део није обезбеђен као део уноса.