Рамочный граф

Перейти к навигацииПерейти к поиску
Рамочный граф.

В теории графов рамочным графом называется вид неориентированного графа, который можно нарисовать на плоскости таким способом, что любая ограниченная грань является четырёхугольником и любая вершина с тремя и менее соседями инцидентна неограниченной грани.

Связанные классы графов

Рамочные графы включают в качестве специальных случаев деревья, решётки, шестерёнки и графы полимино.

Поскольку рамочные графы планарны, они также являются медианными, что означает, что для любых трёх вершин u, v и w существует единственная вершина m(u,v,w) (называемая медианой), которая лежит на кратчайшем пути между каждой парой этих трёх вершин[1]. Как и в случае более общих медианных графов, рамочные графы являются частичными кубами — их вершины можно пометить битовыми строками таким образом, что расстояние Хэмминга между строками равно кратчайшему расстоянию между вершинами.

Характеристика

Шестерня с дополнительной вершиной — запрещённый подграф рамочных графов.

Рамочные графы можно охарактеризовать несколькими путями, отличными от свойства планарности[2]:

  • Они являются медианными графами, не содержащими в качестве порождённого подграфа любой член бесконечного семейства запрещённых графов. Эти запрещённые графы включают куб (симплекс-граф[англ.] K3), прямое произведение ребра и клешни K1,3 (симплекс-граф клешни) и графы, образованные из шестерни добавлением дополнительной вершины, соединённой ребром с центром колеса.
  • Они являются связными и двудольными графами такими, что если выбрать любую вершину r в качестве корня любая вершина имеет максимум два соседа, находящихся ближе к r, и такие, что для любой вершины v связка вершины v (граф, состоящий из вершин для каждого инцидентного v ребра и рёбер для всех циклов длины 4, содержащих вершину v) является либо циклом длины не менее трёх, либо несвязным набором путей.
  • Они являются двойственными графами конфигураций прямых на гиперболической плоскости, в которых нет трёх попарно пересекающихся прямых.

Алгоритмы

Описание рамочных графов в терминах расстояния от корня и связок вершин (см. выше) можно использовать вместе с поиском в ширину как часть алгоритма с линейным временем работы для проверки, является ли данный граф рамочным без необходимости использовать более сложные алгоритмы с линейным временем работы для проверки планарности произвольных графов[2].

Некоторые алгоритмические задачи на рамочных графах могут быть решены эффективнее, чем те же задачи для более общих планарных графов. Например, Чепой, Драган, Ваксес и Фансиллини[3][4] предложили линейные по времени алгоритмы вычисления диаметра рамочных графов и для поиска вершины, которая находится на минимальном расстоянии до всех остальных вершин (то есть вершина, на которой достигается минимум максимального расстояния до всех остальных вершин).

Примечания

  1. ↑ Солтан, Замбицкий, Присакару, 1973. Смотрите более общее обсуждение планарных медианных графов у Петерина Peterin, 2006.
  2. ↑ 1 2 Bandelt, Chepoi, Eppstein, 2010.
  3. ↑ Chepoi, Dragan, Vaxès, 2002.
  4. ↑ Chepoi, Fanciullini, Vaxès, 2004.

Литература

  • H.-J. Bandelt, V. Chepoi, D. Eppstein. Combinatorics and geometry of finite and infinite squaregraphs // SIAM Journal on Discrete Mathematics. — 2010. — Т. 24, вып. 4. — С. 1399—1440. — doi:10.1137/090760301. — arXiv:0905.4537.
  • V. Chepoi, F. Dragan, Y. Vaxès. Proc. 13th Annu. ACM–SIAM Symp. on Discrete Algorithms (SODA 2002). — 2002. — С. 346–355.
  • V. Chepoi, C. Fanciullini, Y. Vaxès. Median problem in some plane triangulations and quadrangulations // Comput. Geom.. — 2004. — Т. 27, вып. 3. — С. 193—210. — doi:10.1016/j.comgeo.2003.11.002.
  • I. Peterin. A characterization of planar median graphs // Discussiones Mathematicae Graph Theory. — 2006. — Т. 26. — С. 41—48. (недоступная ссылка)
  • Солтан П. С., Замбицкий Д. К., Присакару К. Ф. Экстремальные задачи на графах и алгоритмы их решения. — Chişinǎu, Moldova: Штиинца, 1973.