Squaregraph - Squaregraph
В теория графов, филиал математика, а квадратный граф это тип неориентированный граф это может быть нарисованный в плоскости таким образом, что каждый ограниченный лицо это четырехугольник и каждый вершина с тремя или менее соседями случается безграничное лицо.
Связанные классы графов
Квадратные графы включают как частные случаи деревья, сеточные графики, графики передач, а графики полиоминос.
А также быть планарные графы, квадраты медианные графики, что означает, что для каждых трех вершин ты, v, и ш есть единственная срединная вершина м(ты,v,ш), лежащая на кратчайших путях между каждой парой из трех вершин.[1] Как и в случае с медианными графиками в целом, квадратные графы также частичные кубики: их вершины могут быть помечены двоичные строки так что Расстояние Хэмминга между строками равно кратчайшему расстоянию между вершинами.
Граф, полученный из квадратного графа путем создания вершины для каждой зоны (класс эквивалентности параллельных ребер четырехугольников) и ребра для каждых двух зон, которые встречаются в четырехугольнике, является круговой график определяется без треугольников хордовая диаграмма единичного диска.[2]
Характеристика
Квадратные графы можно охарактеризовать несколькими способами, кроме их плоских вложений:[2]
- Они медианные графики которые не содержат в качестве индуцированный подграф любой член бесконечной семьи запрещенные графы. Эти запрещенные графы представляют собой куб ( симплексный график из K3), Декартово произведение края и коготь K1,3 (симплексный граф клешни), а графы, образованные из график передач добавлением еще одной вершины, соединенной со ступицей колеса (симплексный граф непересекающегося объединения цикла с изолированной вершиной).
- Это графы, которые связаны и двудольный, такие что (если произвольная вершина р выбран как корень ) каждая вершина имеет не более двух соседей ближе к р, и такая, что в каждой вершине v, ссылка v (граф с вершиной для каждого ребра, инцидентного v и ребро для каждого 4-цикла, содержащего v) представляет собой либо цикл длины больше трех, либо несвязное объединение путей.
- Они двойственные графы из расположение линий в гиперболическая плоскость которые не имеют трех пересекающихся линий.
Алгоритмы
Характеристика квадратных графов с точки зрения расстояния от корня и связей вершин может использоваться вместе с поиск в ширину как часть линейное время алгоритм для проверки того, является ли данный граф квадратным, без необходимости использования более сложных алгоритмов линейного времени для проверка планарности произвольных графов.[2]
Некоторые алгоритмические задачи на квадратных графах могут быть вычислены более эффективно, чем на более общих плоских или медианных графах; например, Чепои, Драган и Ваксес (2002) и Чепои, Фанчуллини и Ваксес (2004) представить линейные алгоритмы времени для вычисления диаметр квадратных графов, и для поиска вершины, минимизирующей максимальное расстояние до всех остальных вершин.
Примечания
- ^ Солтан, Замбицкий и Присончар (1973). Видеть Петерин (2006) для более общего обсуждения плоских медианных графов.
- ^ а б c Бандельт, Чепой и Эппштейн (2010).
Рекомендации
- Bandelt, H.J .; Чепой, В .; Эппштейн, Д. (2010), «Комбинаторика и геометрия конечных и бесконечных квадратных графов», Журнал SIAM по дискретной математике, 24 (4): 1399–1440, arXiv:0905.4537, Дои:10.1137/090760301, S2CID 10788524.
- Чепой, В .; Dragan, F .; Ваксес, Ю. (2002), "Проблема центра и диаметра в плоских четырехугольниках и триангуляциях", Proc. 13-й год. ACM – SIAM Symp. по дискретным алгоритмам (SODA 2002), стр. 346–355.
- Чепой, В .; Fanciullini, C .; Ваксес, Ю. (2004), "Медианная проблема в некоторых плоских триангуляциях и четырехугольниках", Comput. Геом., 27 (3): 193–210, Дои:10.1016 / j.comgeo.2003.11.002.
- Петерин, Изток (2006), «Характеристика плоских медианных графов», Обсуждения Математическая теория графов, 26 (1): 41–48, Дои:10.7151 / dmgt.1299
- Soltan, P .; Замбицкий, Д .; Присокару, К. (1973), Экстремальные задачи на графах и алгоритмы их решения (на русском языке), Кишинев, Молдова: Ştiinţa.