У теорії графів рамковим графом називають вид неорієнтованого графа, який можна намалювати на площині таким способом, що будь-яка обмежена грань є чотирикутником і будь-яка вершина з трьома і менше сусідами інцидентна необмеженій грані.
Пов'язані класи графів Окремими випадками рамкових графів є дерева, решітки, шестірні і графи поліміно.
Оскільки рамкові графи планарні, вони також є медіанними, що означає, що для будь-яких трьох вершин u, v і w існує єдина вершина m(u,v,w) (називана медіаною), яка лежить на найкоротшому шляху між кожною парою цих трьох вершин. Див. загальніше обговорення планарних медіанних графів у Петеріна ().. Як і у випадку загальніших медіанних графів, рамкові графи є частковими кубами - їх вершини можна позначити бітовими рядками так, що відстань Геммінга між рядками дорівнюватиме найкоротшій відстані між вершинами.
Характеристика
Рамкові графи можна схарактеризувати кількома способами, відмінними від властивості планарності.:
Вони є медіанними графами, що не містять породженим підграфом будь-якого члена нескінченного сімейства заборонених графів. До цих заборонених графів належать куб ( K3), прямий добуток ребра і клешні K1,3 (симплекс-граф клешні) і графи, утворені зі шестерні додаванням вершини, з'єднаної ребром з центром колеса. Вони є зв'язними і двочастковими графами такими, що якщо вибрати будь-яку вершину r як корінь, то будь-яка вершина має максимум два сусіди, що містяться ближче до r, і такі, що для будь-якої вершини v зв'язка вершини v (граф, що складається з вершин для кожного інцидентного v ребра і ребер для всіх циклів довжини 4, що містять вершину v) є або циклом довжини не менше трьох, або незв'язним набором шляхів. Вони є двоїстими графами конфігурацій прямих на гіперболічній площині, в яких немає трьох попарно перетинних прямих.
Алгоритми Опис рамкових графів у термінах відстані від кореня і зв'язок вершин (див. вище) можна використати разом з пошуком у ширину як частину алгоритму з лінійним часом роботи для перевірки, чи є даний граф рамковим без необхідності використовувати складніші алгоритми з лінійним часом роботи для перевірки планарності довільних графів.
Деякі алгоритмічні задачі на рамкових графах можна розв'язати ефективніше, ніж ті самі задачі для загальніших планарних графів. Наприклад, Чепой, Драган, Ваксес і Фансілліні запропонували лінійні за часом алгоритми обчислення діаметра рамкових графів і для пошуку вершини, розташованої на мінімальній відстані від усіх інших вершин (тобто вершини, на якій досягається мінімум максимальної відстані до всіх інших вершин).
Примітки
Література