Граф Петерсена: различия между версиями

Перейти к навигации Перейти к поиску
нет описания правки
Нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
'''Граф Петерсена''' (''[[J.Petersen]], 1891'') - [[граф]] <math>P_{10}( = P)</math>, допускающий следующее представление:  
'''Граф Петерсена''' (''[[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> --- 5-элементное множество. [[Вершина|Вершины]] графа <math>P_{10}</math> --- это двухэлементные подмножества из <math>\Omega</math>. Две вершины в <math>P_{10}</math> [[смежные вершины|смежны]] тогда и только тогда, когда соответствующие им подмножества не пересекаются. '''Г.П.''' представляет собой сумму 1-фактора и 2-фактора, состоящего из двух 5-[[цикл|циклов]]. '''Г.П.''' есть наименьший 3-[[регулярный граф]] с [[обхват|обхватом]] 5, без [[гамильтонов цикл|гамильтонова цикла]], с повышенным [[хроматическое число|хроматическим числом]].
<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>(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.
 
[WG'93]
* Workshop. Utrecht, 1993 // Lect. Notes Comp. Sci., 1994, vol. 790.

Навигация