Что такое график Петерсона?

Опубликовано: 26 Февраля, 2023

Граф — это структура данных, которая определяется двумя компонентами:

  • Узел или вершина.
  • Ребро E или упорядоченная пара — это соединение между двумя узлами u,v, которое идентифицируется уникальной парой (u,v). Пара (u,v) упорядочена, потому что (u,v) не совпадает с (v,u) в случае ориентированного графа. Ребро может иметь вес или установлено равным единице в случае невзвешенного графа.

График Петерсона:

Граф Петерсона

  • представляет собой кубический граф с 10 вершинами и 15 ребрами.
  • является уникальным графом с (3,5)-клеткой и уникальным (3,5)-графом Мура.
  • — нечетный граф с параметром 3. Это граф Кнезера, в котором две вершины смежны тогда и только тогда, когда соответствующие подмножества не пересекаются.
  • также является дополнением к линейному графу k 5
  • — наименьший 3-регулярный граф без мостов без 3-раскраски ребер
  • имеет наибольшее количество остовных деревьев среди всех 3-регулярных графов с десятью вершинами, с 2000.

В графе Петерсона нет 3-цикла или 4-цикла.

Строительство

Граф Петерсона состоит из вершин и ребер полудодекаэдра, который представляет собой додекаэдр с противоположными точками, линиями и гранями, идентифицированными вместе.

Обобщенные графы Петерсона

Семейство кубических графов, полученных путем соединения вершин правильного многоугольника с эквивалентными вершинами звездчатого многоугольника, известно как обобщенный граф Петерсона . Обобщенные графы Петерсона обозначаются через P(n,k).

Если n=7 , k = 7/2 =3 , P(7,1); Р(7,2); Р(7,3)

Хроматическое число графика Петерсона:

График, как показано на рисунке выше, не является полным. Кроме того, у него нечетное количество ребер. В результате это не двудольный граф.

Поскольку граф имеет четное число вершин, хроматическое число графа Петерсена равно 3.

Другие характеристики:

  • Это 3-связный граф и, следовательно, 3-реберно связный и не имеющий мостов.
  • Имеет хроматический полином t (t-1) (t-2) (t 7 -12t 6 +67t 5 -230t 4 +529t 3 -814t 2 +775t-352)
  • Это Непланарно.
  • Это не гамильтоновское.
  • Граф Петерсена имеет гамильтонов путь, но не имеет гамильтонова цикла.

Пример: Докажите, что граф Петерсона не является гамильтоновым.

Предположим, что G — граф Петерсена, и предположим противное, что G гамильтонов. Обозначим вершины G цифрами A, B, C, D… J. Пусть T = {AF, EJ, DI, CH, BG} — подмножество ребер G. Тогда G − T несвязно. Таким образом, любой гамильтоновый цикл группы G должен содержать четные ребра в T. Нетрудно видеть, что любой цикл, содержащий ровно два ребра в T, не является гамильтоновым.