Багаточастковий граф

k-частковий граф — граф, множину вершин якого можна розбити на k незалежних множин (часток). Еквівалентно, це граф, який можна розфарбувати за допомогою k кольорів так, що кінці будь-якого ребра будуть пофарбовані в різні кольори. При k = 2 k-частковий граф називається двочастковим^[1].

Розпізнати двочастковий граф можна за поліноміальний час, але для будь-якого k > 2 задача визначення, чи є даний нерозфарбований граф k-частковим, стає NP-повною^[2]. Втім, у деяких застосуваннях теорії графів k-частковий граф можна задати на вході вже розфарбованим; це може статися, коли множини вершин графу відповідають різним типам об'єктів. Наприклад, фолксономії математично моделювалися тричастковими графами, в яких три множини вершин відповідають користувачам системи, ресурсам, які позначаються тегами, і власне тегам^[3]

Повний тричастковий граф K_2,2,2 — граф октаедра

Повний k-частковий граф — це k-частковий граф, такий, що будь-які дві вершини, які належать до різних часток, суміжні^[1]. Повний k-частковий граф можна описати нотацією

${\displaystyle K_{v_{1},v_{2},\ldots ,v_{k}},}$

де ${\displaystyle v_{1},v_{2},\ldots ,v_{k}}$ — число вершин у частках графу. Наприклад, ${\displaystyle K_{2,2,2}}$ — повний тричастковий граф правильного октаедра, що складається з трьох незалежних множин, кожна з яких включає дві протилежні вершини октаедра. Повний багаточастковий граф — це граф, який є повним k-частковим для деякого k^[4].

Граф Турана — повний багаточастковий граф, потужності будь-яких двох часток якого відрізняються не більше ніж на 1. Повні багаточасткові графи — частковий випадок кографів.

Див. також

• Двочасткова розмірність

Примітки

1. Лекции по теории графов, 1990, с. 11.
2. Computers and Intractability, 1979.
3. Hotho, Andreas; Jäschke, Robert; Schmitz, Christoph; Stumme, Gerd (2006), FolkRank : A Ranking Algorithm for Folksonomies, LWA 2006: Lernen - Wissensentdeckung - Adaptivität, Hildesheim, October 9th-11th 2006, с. 111—114
4. Chromatic Graph Theory, 2008, с. 41.

Література

• В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич. Лекции по теории графов. — М. : Наука, Физматлит, 1990. — 384 с. — ISBN 5-02-013992-0.
• Gary Chartrand, Ping Zhang. Chromatic Graph Theory. — CRC Press, 2008. — ISBN 9781584888017.
• Michael R. Garey, David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. — W. H. Freeman, 1979. — ISBN 0-7167-1045-5.