Квартальный граф
В математической области теории графов граф квартики — это граф , все вершины которого имеют степень 4. Другими словами, граф квартики — это 4- регулярный граф . [1]
Примеры
[ редактировать ]
Некоторые известные графы являются четвертыми. Они включают в себя:
- Полный граф K 5 , граф квартики с 5 вершинами, наименьший возможный граф квартики.
- Граф Хватала , еще один граф квартики с 12 вершинами, наименьший граф квартики, который не имеет треугольников и не может быть раскрашен в три цвета. [2]
- Граф Фолкмана , граф квартики с 20 вершинами, наименьший полусимметричный граф . [3]
- Граф Мередита , граф квартики с 70 вершинами, который является 4-связным , но не имеет гамильтонова цикла , опровергая гипотезу Криспина Нэша-Уильямса . [4]
Каждый медиальный граф является графом плоскости четвертой степени , а каждый граф плоскости четвертой степени является медиальным графом пары графов или мультиграфов двойственной плоскости. [5] Диаграммы узлов и диаграммы связей также являются мультиграфами на плоскости четвертой степени , в которых вершины представляют собой пересечения диаграммы и помечены дополнительной информацией о том, какая из двух ветвей узла пересекает другую ветвь в этой точке. [6]
Характеристики
[ редактировать ]Поскольку степень каждой вершины в графе квартики четная, каждый связный граф квартики имеет эйлеров обход .И, как и в случае с обычными двудольными графами в более общем смысле, каждый двудольный граф квартики имеет идеальное паросочетание . В этом случае возможен гораздо более простой и быстрый алгоритм поиска такого паросочетания, чем для нерегулярных графов: выбирая каждое второе ребро эйлерова тура, можно найти 2-фактор , который в данном случае должен представлять собой набор циклов , каждый из которых имеет четную длину, причем каждая вершина графа встречается ровно в одном цикле. Снова выбирая каждое второе ребро в этих циклах, можно получить идеальное паросочетание за линейное время . Тот же метод можно использовать для раскраски ребер графа в четыре цвета за линейное время. [7]
Графы квартики имеют четное число гамильтоновых разложений . [8]
Открытые проблемы
[ редактировать ]Это открытая гипотеза, все ли гамильтоновы графы квартики имеют четное количество гамильтоновых контуров или имеют более одного гамильтонова контура. Известно, что ответ неверен для мультиграфов четвертой степени . [9]
См. также
[ редактировать ]
Ссылки
[ редактировать ]- ^ Тойда, С. (1974), «Построение графов квартики», Журнал комбинаторной теории , серия B, 16 : 124–133, doi : 10.1016/0095-8956(74)90054-9 , MR 0347693 .
- ^ Хватал, В. (1970), «Наименьший 4-хроматический 4-правильный граф без треугольников», Journal of Combinatorial Theory , 9 (1): 93–94, doi : 10.1016/S0021-9800(70)80057-6 .
- ^ Фолкман, Джон (1967), «Регулярные линейно-симметричные графы», Журнал комбинаторной теории , 3 : 215–232, doi : 10.1016/s0021-9800(67)80069-3 , MR 0224498 .
- ^ Мередит, GHJ (1973), «Регулярные n -валентные n -связные негамильтоновы по n - графы, не раскрашиваемые ребрам», Journal of Combinatorial Theory , Series B, 14 : 55–60, doi : 10.1016/s0095-8956(73) 80006-1 , МР 0311503 .
- ^ Бонди, Дж.А.; Хэггквист, Р. (1981), «Непересекающиеся по краям циклы Гамильтона в 4-регулярных плоских графах», Aequationes Mathematicae , 22 (1): 42–45, doi : 10.1007/BF02190157 , MR 0623315 .
- ^ Уэлш, Доминик Дж. А. (1993), «Сложность узлов», Quo vadis, теория графов? , Анналы дискретной математики, вып. 55, Амстердам: Северная Голландия, стр. 159–171, номер документа : 10.1016/S0167-5060(08)70385-6 , MR 1217989 .
- ^ Габоу, Гарольд Н. (1976), «Использование разбиений Эйлера для граничных цветных двудольных мультиграфов», Международный журнал компьютерных и информационных наук , 5 (4): 345–355, doi : 10.1007/bf00998632 , MR 0422081 .
- ^ Томасон, А.Г. (1978), «Гамильтоновы циклы и графы, раскрашиваемые однозначно по краям», Annals of Discrete Mathematics , 3 : 259–268, doi : 10.1016/s0167-5060(08)70511-9 , MR 0499124 .
- ^ Флейшнер, Герберт (1994), «Единственность максимальных доминирующих циклов в 3-регулярных графах и гамильтоновых циклов в 4-регулярных графах», Journal of Graph Theory , 18 (5): 449–459, doi : 10.1002/jgt.3190180503 , МР 1283310 .