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