В теории графов , разделе математики , квадратный граф - это тип неориентированного графа, который может быть нарисован на плоскости таким образом, что каждая ограниченная грань является четырехугольником, а каждая вершина с тремя или меньшим числом соседей инцидентна неограниченной грани.
Связанные классы графов [ править ]
Квадратные графы включают в себя как частные случаи деревья , сеточные графы , графы шестеренок и графы полимино .
Помимо того , что квадратные графы являются планарными , они являются медианными графами , что означает, что для каждых трех вершин 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) представляют алгоритмы линейного времени для вычисления диаметра квадратных графов и для поиска вершины, минимизирующей максимальное расстояние до всех остальных вершин.
Заметки [ править ]
- ^ Солтан, Zambitskii & Prisǎcaru (1973) . См. Более общее обсуждение плоских медианных графов в Peterin (2006) .
- ^ a b c Bandelt, Chepoi & Eppstein (2010) .
Ссылки [ править ]
- Bandelt, H.J .; Чепой, В .; Эппштейн, Д. (2010), «Комбинаторика и геометрия конечных и бесконечных квадратных графов», Журнал SIAM по дискретной математике , 24 (4): 1399–1440, arXiv : 0905.4537 , doi : 10.1137 / 090760301 , S2CID 10788524.
- Чепой, В .; Dragan, F .; Vaxès, Y. (2002), "Проблема центра и диаметра в плоских четырехугольниках и триангуляциях", Proc. 13-й год. ACM – SIAM Symp. по дискретным алгоритмам (SODA 2002) , стр. 346–355..
- Чепой, В .; Fanciullini, C .; Ваксес, Y. (2004), "Медианная проблема в некоторых плоских триангуляциях и четырехугольниках", Ж. вычисл . Геом. , 27 (3): 193–210, DOI : 10.1016 / j.comgeo.2003.11.002.
- Peterin, Iztok (2006), "Характеристика плоскостных срединных графов" , Discussiones Mathematicae Теория графов , 26 (1): 41-48, DOI : 10,7151 / dmgt.1299
- Soltan, P .; Замбицкий, Д .; Прискару Ч. (1973), Экстремальные задачи на графах и алгоритмы их решения , Кишинев, Молдова: Ştiinţa.
