Граф Турана: відмінності між версіями

27 байтів вилучено ,  7 місяців тому
вікіфікація
Немає опису редагування
(вікіфікація)
Будь-який граф Турана є [[кограф]]ом. Таким чином, його можна утворити з окремих вершин послідовністю операцій [[Диз'юнктне об'єднання|диз'юнктного об'єднання]] і [[Доповнення графа|доповнення]]. Зокрема, таку послідовність можна почати утворенням усіх незалежних множин графу Турана як диз'юнктного об'єднання ізольованих вершин. Тоді весь граф є доповненням диз'юнктного об'єднання доповнень цих незалежних множин.
 
Чао і Новацький (Chao, Novacky, 1982) показали, що графи Турана ''хроматично єдині'' — ніякі інші графи не мають таких самих [[Хроматичний многочлен|хроматичних многочленів]]. Нікіфоров (Nikiforov, 2005) використовував графи Турана для знаходження нижньої межі суми ''k''-х [[Власні вектори та власні числазначення|власних значень]] графу і його доповнення.
 
Фолс, Повел і Сноїнк (Falls, Powell, Snoeyink) розробили ефективний алгоритм для пошуку кластерів ортологічних груп генів у геномі поданням даних як графу і пошуком великих підграфів Турана.