Введение
Граф со всеми вершинами степени 4. В математической области теории графов, квартичный граф — это граф, в котором все вершины имеют степень 4. Иными словами, квартичный граф — это 4-регулярный граф.
In the mathematical field of graph theory, a quartic graph is a graph where all vertices have degree 4. In other words, a quartic graph is a 4 regular graph.
Примеры
Несколько хорошо известных графов являются квартичными. К ним относятся:
Полный граф K5, квартичный граф с 5 вершинами, наименьший возможный квартичный граф. Граф Хватала, другой квартичный граф с 12 вершинами, наименьший квартичный граф, не содержащий треугольников и не допускающий раскраску в три цвета. Граф Фолькмана, квартичный граф с 20 вершинами, наименьший полусимметричный граф. Граф Мередита, квартичный граф с 70 вершинами, являющийся 4-связным, но не имеющий гамильтонова цикла, что опровергает гипотезу Криспина Нэша Уильямса. Любой медиальный граф является квартичным планарным графом, и любой квартичный планарный граф является медиальным графом пары дуальных планарных графов или мультиграфов. Диаграммы узлов и диаграммы зацеплений также являются квартичными планарными мультиграфами, в которых вершины представляют собой пересечения диаграммы и снабжены дополнительной информацией о том, какая из двух ветвей узла переходит другую ветвь в данной точке.
The complete graph K5, a quartic graph with 5 vertices, the smallest possible quartic graph. The Chvátal graph, another quartic graph with 12 vertices, the smallest quartic graph that both has no triangles and cannot be colored with three colors. The Folkman graph, a quartic graph with 20 vertices, the smallest semi symmetric graph. The Meredith graph, a quartic graph with 70 vertices that is 4 connected but has no Hamiltonian cycle, disproving a conjecture of Crispin Nash Williams. Every medial graph is a quartic plane graph, and every quartic plane graph is the medial graph of a pair of dual plane graphs or multigraphs. Knot diagrams and link diagrams are also quartic plane multigraphs, in which the vertices represent the crossings of the diagram and are marked with additional information concerning which of the two branches of the knot crosses the other branch at that point.
Свойства
Поскольку степень каждой вершины в квартичном графе четна, каждый связный квартичный граф имеет эйлеров цикл. И как и в случае с регулярными двудольными графами в более общем смысле, каждый двудольный квартичный граф имеет совершенное паросочетание. В этом случае возможен гораздо более простой и быстрый алгоритм поиска такого паросочетания, чем для нерегулярных графов: выбирая каждый второй ребро эйлерова цикла, можно найти 2-фактор, который в этом случае должен представлять собой набор циклов, каждый из которых имеет четную длину, и каждая вершина графа появляется ровно в одном цикле. Повторно выбирая каждый второй ребро в этих циклах, можно получить совершенное паросочетание за линейное время. Тот же метод также можно использовать для раскраски ребер графа четырьмя цветами за линейное время. Квартичные графы имеют четное число гамильтоновых разложений.
Открытые проблемы
Открытым вопросом остаётся, имеют ли все квартичные гамильтоновы графы чётное количество гамильтоновых циклов или более одного гамильтонова цикла. Известно, что ответ отрицателен для квартичных мультиграфов.