Граф Петерсена: различия между версиями
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Граф Петерсена''' (''[[J.Petersen]], 1891'') | '''Граф Петерсена''' (''[[J.Petersen]], 1891'') — [[граф]] <math>P_{10}( = P)</math>, допускающий следующее представление: | ||
[[Файл:J.Petersen.png|200px|left]] | [[Файл:J.Petersen.png|200px|left]] | ||
Пусть | Пусть | ||
<math>\Omega = \{1,2,3,4,5\}</math> | <math>\Omega = \{1,2,3,4,5\}</math> — 5-элементное множество. [[Вершина|Вершины]] графа <math>P_{10}</math> — это двухэлементные подмножества из <math>\Omega</math>. Две вершины в <math>P_{10}</math> [[смежные вершины|смежны]] тогда и только тогда, когда соответствующие им подмножества не пересекаются. '''Граф Петерсена''' представляет собой сумму 1-фактора и 2-фактора, состоящего из двух 5-[[цикл|циклов]]. '''Граф Петерсена''' есть наименьший 3-[[регулярный граф]] с [[обхват|обхватом]] 5, без [[гамильтонов цикл|гамильтонова цикла]], с повышенным [[хроматическое число|хроматическим числом]]. | ||
''Гиперсетью Петерсена'' называется граф <math>HP_{n} = Q_{n-3} \times P</math>, где <math>Q_{n-3}</math> | ''Гиперсетью Петерсена'' называется граф <math>HP_{n} = Q_{n-3} \times P</math>, где <math>Q_{n-3}</math> — <math>(n-3)</math>-мерный гиперкуб. | ||
''<math>n</math>-складной граф Петерсена'' (<math>n</math>-''folded Petersen graph'') есть граф <math>FP_{n} = \underbrace{P \times \cdots \times P}_{n}</math>. Здесь <math>\times</math> обозначает декартово произведение. | ''<math>n</math>-складной граф Петерсена'' (<math>n</math>-''folded Petersen graph'') есть граф <math>FP_{n} = \underbrace{P \times \cdots \times P}_{n}</math>. Здесь <math>\times</math> обозначает декартово произведение. | ||
==Литература== | ==Литература== | ||
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990. | |||
* Харари Ф. Теория графов. — М.: Мир, 1973. | |||
* Workshop. Utrecht, 1993 // Lect. Notes Comp. Sci., 1994, vol. 790. | |||
Текущая версия от 16:37, 1 февраля 2011
Граф Петерсена (J.Petersen, 1891) — граф [math]\displaystyle{ P_{10}( = P) }[/math], допускающий следующее представление:
Пусть [math]\displaystyle{ \Omega = \{1,2,3,4,5\} }[/math] — 5-элементное множество. Вершины графа [math]\displaystyle{ P_{10} }[/math] — это двухэлементные подмножества из [math]\displaystyle{ \Omega }[/math]. Две вершины в [math]\displaystyle{ P_{10} }[/math] смежны тогда и только тогда, когда соответствующие им подмножества не пересекаются. Граф Петерсена представляет собой сумму 1-фактора и 2-фактора, состоящего из двух 5-циклов. Граф Петерсена есть наименьший 3-регулярный граф с обхватом 5, без гамильтонова цикла, с повышенным хроматическим числом.
Гиперсетью Петерсена называется граф [math]\displaystyle{ HP_{n} = Q_{n-3} \times P }[/math], где [math]\displaystyle{ Q_{n-3} }[/math] — [math]\displaystyle{ (n-3) }[/math]-мерный гиперкуб.
[math]\displaystyle{ n }[/math]-складной граф Петерсена ([math]\displaystyle{ n }[/math]-folded Petersen graph) есть граф [math]\displaystyle{ FP_{n} = \underbrace{P \times \cdots \times P}_{n} }[/math]. Здесь [math]\displaystyle{ \times }[/math] обозначает декартово произведение.
Литература
- Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.
- Харари Ф. Теория графов. — М.: Мир, 1973.
- Workshop. Utrecht, 1993 // Lect. Notes Comp. Sci., 1994, vol. 790.