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

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

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

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

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

Поскольку рамочные графы планарны, они также являются медианными, что означает, что для любых трёх вершин 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. 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.