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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Рамочный граф.

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

Связанные классы графов[править | править вики-текст]

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

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

Характеристика[править | править вики-текст]

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

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

Алгоритмы[править | править вики-текст]

Описание рамочных графов в терминах расстояния от корня и связок вершин (см. выше) можно использовать вместе с поиском в ширину как часть алгоритма с линейным временем работы для проверки, является ли данный граф рамочным без необходимости использовать более сложные алгоритмы с линейным временем работы для проверки планарности произвольных графов[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.