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

Материал из WikiGrapp
Перейти к:навигация, поиск

Граф Петерсена (J.Petersen, 1891) — граф P_{10}( = P), допускающий следующее представление:

J.Petersen.png

Пусть \Omega = \{1,2,3,4,5\} — 5-элементное множество. Вершины графа P_{10} — это двухэлементные подмножества из \Omega. Две вершины в P_{10} смежны тогда и только тогда, когда соответствующие им подмножества не пересекаются. Граф Петерсена представляет собой сумму 1-фактора и 2-фактора, состоящего из двух 5-циклов. Граф Петерсена есть наименьший 3-регулярный граф с обхватом 5, без гамильтонова цикла, с повышенным хроматическим числом.

Гиперсетью Петерсена называется граф HP_{n} = Q_{n-3} \times P, где Q_{n-3}(n-3)-мерный гиперкуб.

n-складной граф Петерсена (n-folded Petersen graph) есть граф FP_{n} = \underbrace{P \times \cdots \times P}_{n}. Здесь \times обозначает декартово произведение.

Литература

  • Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.
  • Харари Ф. Теория графов. — М.: Мир, 1973.
  • Workshop. Utrecht, 1993 // Lect. Notes Comp. Sci., 1994, vol. 790.