Jump to content

Квартальный граф

В математической области теории графов граф квартики — это граф , все вершины которого имеют степень 4. Другими словами, граф квартики — это 4- регулярный граф . [1]

График захвата

Некоторые известные графы являются четвертыми. Они включают в себя:

Каждый медиальный граф является графом плоскости четвертой степени , а каждый граф плоскости четвертой степени является медиальным графом пары графов или мультиграфов двойственной плоскости. [5] Диаграммы узлов и диаграммы связей также являются мультиграфами на плоскости четвертой степени , в которых вершины представляют собой пересечения диаграммы и помечены дополнительной информацией о том, какая из двух ветвей узла пересекает другую ветвь в этой точке. [6]

Характеристики

[ редактировать ]

Поскольку степень каждой вершины в графе квартики четная, каждый связный граф квартики имеет эйлеров обход .И, как и в случае с обычными двудольными графами в более общем смысле, каждый двудольный граф квартики имеет идеальное паросочетание . В этом случае возможен гораздо более простой и быстрый алгоритм поиска такого паросочетания, чем для нерегулярных графов: выбирая каждое второе ребро эйлерова тура, можно найти 2-фактор , который в данном случае должен представлять собой набор циклов , каждый из которых имеет четную длину, причем каждая вершина графа встречается ровно в одном цикле. Снова выбирая каждое второе ребро в этих циклах, можно получить идеальное паросочетание за линейное время . Тот же метод можно использовать для раскраски ребер графа в четыре цвета за линейное время. [7]

Графы квартики имеют четное число гамильтоновых разложений . [8]

Открытые проблемы

[ редактировать ]

Это открытая гипотеза, все ли гамильтоновы графы квартики имеют четное количество гамильтоновых контуров или имеют более одного гамильтонова контура. Известно, что ответ неверен для мультиграфов четвертой степени . [9]

См. также

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