Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

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



План:


Введення

Граф Петерсена
Інше уявлення графа Петерсена

Граф Петерсена - досить простий об'єкт теорії графів з цікавими властивостями. Названий на честь Юліуса Петерсена, датського математика.


1. Загальна інформація

Граф Петерсена є неорієнтованим кубічним графом. Його можна побудувати, взявши доповнення реберного графа від повного 5-графа. Має 10 вершин і 15 ребер. Сильно регулярний і реберно регулярний, тобто, вибравши вершину або ребро можна відобразити граф на себе, перевівши вибраний об'єкт в будь-яку вершину (ребро). Граф є клітиною і графом Мура. Його група - S 5. Конфігурація Дезарга в проективної геометрії відповідає додатком графа Петерсена і відповідно має ту ж групу S 5.


2. Властивості

  • Не є Гамільтона, в той же час, результат видалення вершини - гамільтонів граф.
  • Хроматичної число графа - 3.
  • Хроматичний клас (розмальовка ребер) - 4, іншими словами, граф не є сумою трьох 1-факторів, що показав ще сам Петерсен. [1]
  • При зображенні на площині має не менше двох самоперетинів.
  • Між будь-якими двома вершинами існує єдиний шлях довжини не більше двох.

Примітки

  1. Ф. Харарі Теорія графів стор 113

Література



Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Граф
Граф Нулін
Тотожний граф
Граф, Девід
Граф, Штеффі
Граф Монтенегро
Граф алгоритму
Граф Ессекс
Граф Лестер
© Усі права захищені
написати до нас
Рейтинг@Mail.ru