Граф без клешень
З Вікіпедії, безкоштовно encyclopedia
У теорії графів графом без клешень називається граф, який не містить клешень, як породжених підграфів.
Клешнею називається повний двочастковий граф K1,3 (тобто, зірка з трьома ребрами, трьома листками і однією центральною вершиною). Граф без клешень — це граф, в якому кожен породжений підграф не є клешнею. Тобто будь-яка підмножина з чотирьох вершин не є зіркою з трьома ребрами, що виходять з центральної вершини. Також можливо визначити граф без клешень, як граф, в якому окіл будь-якої вершини утворює доповнення графу без трикутників.
Графи без клешень спочатку вивчалися як узагальнення реберних графів і викликали додатковий інтерес лише тоді, коли було зроблено три ключових відкриття про графи без клешень:
- усі зв'язні графи без клешень парного порядку мають досконалі парування;
- відкриття поліноміального за часом алгоритму пошуку максимальних незалежних множин у графах без клешень;
- опис досконалих графів без клешень[1];
Графам без клешень присвячені сотні статей і кілька оглядів[2].