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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Граф Петерсена''' (''J.Petersen, 1891'') - граф <math>P_{10}( = P)</math>, допускающий следующее ...)
 
Нет описания правки
Строка 1: Строка 1:
'''Граф Петерсена''' (''J.Petersen, 1891'') -  
'''Граф Петерсена''' (''[[J.Petersen]], 1891'') - [[граф]] <math>P_{10}( = P)</math>, допускающий следующее представление: Пусть
граф <math>P_{10}( = P)</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>\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
''Гиперсетью Петерсена'' называется граф <math>HP_{n} = Q_{n-3} \times P</math>, где <math>Q_{n-3}</math> --- <math>(n-3)</math>-мерный гиперкуб.
P</math>, где <math>Q_{n-3}</math> --- <math>(n-3)</math>-мерный гиперкуб.


''<math>n</math>-складной граф Петерсена'' (<math>n</math>-''folded Petersen graph'') есть
''<math>n</math>-складной граф Петерсена'' (<math>n</math>-''folded Petersen graph'') есть граф <math>FP_{n} = \underbrace{P \times \cdots \times P}_{n}</math>. Здесь <math>\times</math> обозначает декартово произведение.
граф <math>FP_{n} = \underbrace{P \times \cdots \times P}_{n}</math>. Здесь
<math>\times</math> обозначает декартово произведение.
==Литература==
==Литература==
[Харари],  
[Харари],  

Версия от 20:27, 10 октября 2009

Граф Петерсена (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] обозначает декартово произведение.

Литература

[Харари],

[Лекции],

[WG'93]