Квадратграф
В теории графов , разделе математики , квадратный граф — это тип неориентированного графа , который можно нарисовать на плоскости таким образом, что каждая ограниченная грань является четырехугольником , а каждая вершина с тремя или меньшим количеством соседей инцидентна неограниченной грани.
Связанные классы графов
[ редактировать ]особых случаев Квадратные графы включают деревья , сеточные графы , зубчатые графы и графы полимино .
Помимо того, что квадратные графы являются плоскими графами , квадратные графы являются медианными графами , что означает, что для каждых трех вершин u , v и w существует уникальная медианная вершина m ( u , v , w ), которая лежит на кратчайших путях между каждой парой из трех вершин. . [1] Как и медианные графы в более общем смысле, квадратные графы также являются частичными кубами : их вершины могут быть помечены двоичными строками так, что расстояние Хэмминга между строками равно расстоянию кратчайшего пути между вершинами.
Граф, полученный из квадратного графа путем создания вершины для каждой зоны (класс эквивалентности параллельных ребер четырехугольников) и ребра для каждых двух зон, пересекающихся в четырехугольнике, представляет собой круговой граф, определяемый без треугольников хордовой диаграммой единицы диск. [2]
Характеристика
[ редактировать ]Квадратные графы можно охарактеризовать несколькими способами, кроме их плоских вложений: [2]
- Это медианные графы , которые не содержат в качестве индуцированного подграфа ни одного члена бесконечного семейства запрещенных графов . Этими запрещенными графами являются куб ( граф симплексный K 3 ), декартово произведение ребра и когтя K 1,3 (симплексный граф когтя), а также графы, образованные из зубчатого графа добавлением еще одной вершины. соединен со ступицей колеса (симплекс-граф непересекающегося объединения цикла с изолированной вершиной).
- Это связные и двудольные графы , такие, что (если произвольная вершина r выбрана в качестве корня ) каждая вершина имеет не более двух соседей, ближайших к r , и такие, что в каждой вершине v связь v (граф с вершиной для каждого ребра, инцидентного v , и ребром для каждого 4-цикла, содержащего v ), является либо циклом длины больше трех, либо несвязным объединением путей.
- Это двойственные графы расположения прямых на гиперболической плоскости , не имеющие трех пересекающихся прямых.
Алгоритмы
[ редактировать ]Характеристика квадратных графов с точки зрения расстояния от корня и связей вершин может использоваться вместе с поиском в ширину как часть с линейным временем алгоритма для проверки того, является ли данный граф квадратным, без необходимости использования более сложного линейного алгоритма. временные алгоритмы проверки планарности произвольных графов. [2]
Некоторые алгоритмические задачи на квадратных графах могут быть решены более эффективно, чем на более общих планарных или медианных графах; например, Chepoi, Dragan & Vaxès (2002) и Chepoi, Fanciullini & Vaxès (2004) представляют алгоритмы с линейным временем для вычисления диаметра квадратных графов и для поиска вершины, минимизирующей максимальное расстояние до всех других вершин.
Примечания
[ редактировать ]- ^ Солтан, Замбицкий и Прискару (1973) . См. Петерин (2006) для более общего обсуждения плоских медианных графиков.
- ^ Jump up to: Перейти обратно: а б с Бандельт, Чепой и Эппштейн (2010) .
Ссылки
[ редактировать ]- Бандельт, Ханс-Юрген; Чепой, Виктор; Эппштейн, Дэвид (2010), «Комбинаторика и геометрия конечных и бесконечных квадратов», SIAM Journal on Discrete Mathematics , 24 (4): 1399–1440, arXiv : 0905.4537 , doi : 10.1137/090760301 , S2CID 10788524 .
- Чепой, Виктор; Драган, Федор; Ваксес, Ян (2002), «Проблема центра и диаметра в плоских четырехугольниках и триангуляциях», Proc. 13-го года. ACM – SIAM Symp. по дискретным алгоритмам (SODA 2002) , стр. 346–355 .
- Чепой, Виктор; Фанчуллини, Клементина; Ваксес, Янн (2004), «Медианная задача в некоторых плоских триангуляциях и четырехугольниках», Computational Geometry , 27 (3): 193–210, doi : 10.1016/j.comgeo.2003.11.002 .
- Петерин, Изток (2006), «Характеристика плоских медианных графов» , «Дискуссии Mathematicae Graph Theory» , 26 (1): 41–48, doi : 10.7151/dmgt.1299
- Солтан, П.; Замбицкий Д.; Прискару, К. (1973), Экстремальные задачи на графах и алгоритмы их решения (на русском языке), Кишинев, Молдова: Штиинца .