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

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

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

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

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

• представляет собой кубический граф с 10 вершинами и 15 ребрами.
• является уникальным графом с (3,5)-клеткой и уникальным (3,5)-графом Мура.
• — нечетный граф с параметром 3. Это граф Кнезера, в котором две вершины смежны тогда и только тогда, когда соответствующие подмножества не пересекаются.
• также является дополнением к линейному графу k ₅
• — наименьший 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 ⁷ -12t ⁶ +67t ⁵ -230t ⁴ +529t ³ -814t ² +775t-352)
• Это Непланарно.
• Это не гамильтоновское.
• Граф Петерсена имеет гамильтонов путь, но не имеет гамильтонова цикла.

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

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