Галерея именованных графов

Некоторые из конечных структур, рассматриваемых в теории графов, имеют имена, иногда вдохновленные топологией графа, а иногда и именами их первооткрывателя. Известным примером является граф Петерсена , конкретный граф с 10 вершинами, который появляется как минимальный пример или контрпример во многих различных контекстах.

Индивидуальные графики [ править ]

• 

  Балабан 10-клеточный

• 

  Балабан 11-клеточный

• 

  Куб Бидьякиса

• 

  Граф Бринкмана

• 

  Бычий график

• 

  График бабочки

• 

  Хваталь граф

• 

  Алмазный график

• 

  Граф Дюрера

• 

  Эллингема – Хортона, 54 графика

• 

  78-график Эллингема – Хортона

• 

  График Эрреры

• 

  Граф Франклина

• Граф Фрухта

• График Гольднера – Харари

• Граф Голомба

• График Грёча

• Граф Харриса

• График Харриса – Вонга

• Граф Гершеля

• Граф Хоффмана

• Граф Холта

• График Хортона

• График Киттелла

• График Маркстрёма

• График Макги

• График Мередита

• Шпиндель Мозера

• График Сусселье

• Граф Пуссена

• Граф Робертсона

• График Сильвестра

• Фрагмент Тутте

• График Тутте

• График Юнга – Фибоначчи

• График Вагнера

• График Уэллса

• График Винера – Арая

Высоко симметричные графики [ править ]

Сильно регулярные графики [ править ]

Сильно регулярный граф на v вершинах и ранга к обычно обозначаемое SRG ( v, к , λ, μ).

• Граф Клебша

• Граф Кэмерона

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

• График Холла – Янко

• Граф Хоффмана – Синглтона

• График Хигмана – Симса

• Граф Пэли порядка 13

• Граф Шриханде

• Граф Шлефли

• График Брауэра – Хемерса

• Локальный график Маклафлина

• График Перкеля

• Граф Гевиртца

Симметричные графики [ править ]

Симметрический граф является тот , в котором имеется симметрия ( граф автоморфизм ) принимать какую - либо упорядоченную пару смежных вершин в любую другую упорядоченной пару; в переписи Фостера перечислены все маленькие симметричные 3-регулярные графы. Каждый сильно регулярный граф симметричен, но не наоборот.

• График Хивуда

• Граф Мебиуса – Кантора

• График Паппа

• Граф дезарга

• Науру график

• Граф Кокстера

• График Тутте – Кокстера

• Граф Дика

• Граф Клейна

• Граф Фостера

• График Биггса – Смита

• Rado график

Полусимметричные графы [ править ]

• Граф Фолькмана

• Серый график

• Любляна график

• Тутте 12 клеток

Семейства графов [ править ]

Полные графики [ править ]

Полный граф на вершинах часто называют -clique и обычно обозначается , от немецкого Komplett . ^[1]${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle K_ {n}}$

• ${\ displaystyle K_ {1}}$

• ${\ displaystyle K_ {2}}$

• ${\ displaystyle K_ {3}}$

• ${\ displaystyle K_ {4}}$

• ${\ displaystyle K_ {5}}$

• ${\ displaystyle K_ {6}}$

• ${\ displaystyle K_ {7}}$

• ${\ displaystyle K_ {8}}$

Полные двудольные графы [ править ]

Полный двудольный граф обычно обозначается . Для смотрите раздел звездных графиков. График равен 4-циклу (квадрату), представленному ниже. ${\ displaystyle K_ {n, m}}$${\ Displaystyle п = 1}$${\ displaystyle K_ {2,2}}$${\ displaystyle C_ {4}}$

• ${\ displaystyle K_ {2,3}}$

• ${\ displaystyle K_ {3,3}}$, граф полезности

• ${\ displaystyle K_ {2,4}}$

• ${\ displaystyle K_ {3,4}}$

Циклы [ править ]

Граф циклов на вершинах называется n-циклом и обычно обозначается . Его также называют циклическим графом , многоугольником или n-угольником . Особые случаи - треугольник , квадрат , а затем несколько с греческим названием пятиугольник , шестиугольник и т. Д.${\ displaystyle n}$${\displaystyle C_{n}}$ ${\displaystyle C_{3}}$ ${\displaystyle C_{4}}$ ${\displaystyle C_{5}}$ ${\displaystyle C_{6}}$

• ${\displaystyle C_{3}}$

• ${\displaystyle C_{4}}$

• ${\displaystyle C_{5}}$

• ${\displaystyle C_{6}}$

Графики дружбы [ править ]

Граф дружбы F _n может быть построен путем соединения n копий графа циклов C ₃ с общей вершиной. ^[2]

Графики фуллеренов [ править ]

В теории графов, термин фуллерна относится к любому 3- регулярного , плоскому графу со всеми гранями размера 5 или 6 ( в том числе наружной поверхности). Как следует из многогранника формулы Эйлера , V  -  E  +  F  = 2 (где V , E , F указывают число вершин, ребер и граней), то есть ровно 12 пентагонов в фуллерен и ч  =  V / 2 - 10 шестиугольники. Следовательно, V  = 20 + 2 ч ; E  = 30 + 3 ч . Графики фуллеренов - этоШлегелевские представления соответствующих фуллереновых соединений.

• 20-фуллерен ( додекаэдрический граф)

• 24-фуллерен ( гексагональный усеченный трапециевидный граф)

• 26-фуллереновый граф

• 60-фуллерен ( усеченный икосаэдрический граф)

• 70-фуллерен

Алгоритм генерации всех неизоморфных фуллеренов с заданным числом шестиугольных граней был разработан Г. Бринкманном и А. Дрессом. ^[3] Г. Бринкманн также предоставил свободно доступную реализацию под названием fullgen .

Платоновы тела [ править ]

Полный граф на четырех вершинах образует скелет тетраэдра , а в более общем полные графы образуют скелеты симплексов . В графе гиперкуб также скелеты многомерных регулярных многогранников .

• Куб ,
  ${\displaystyle n=8}$${\displaystyle m=12}$

• Октаэдр ,
  ${\displaystyle n=6}$${\displaystyle m=12}$

• Додекаэдр ,
  ${\displaystyle n=20}$${\displaystyle m=30}$

• Икосаэдр ,
  ${\displaystyle n=12}$${\displaystyle m=30}$

Усеченные тела [ править ]

• Усеченный тетраэдр

• Усеченный куб

• Усеченный октаэдр

• Усеченный додекаэдр

• Усеченный икосаэдр

Снаркс [ править ]

Снарк является bridgeless кубического графом , который требует четыре цветов в любом надлежащей раскраски ребер . Самый маленький снарк - это граф Петерсена , уже упомянутый выше.

• Блануша снарк (первая)

• Блануша Снарк (вторая)

• Двойная звезда снарк

• Цветочный снарк

• Лупекин Снарк (первый)

• Лупекин Снарк (второй)

• Секерес Снарк

• График Титце

• Уоткинс Снарк

Звездочка [ править ]

Звезда S _к является полный двудольный граф K _{1, K} . Звезда S ₃ называется графом когтей.

Графики колес [ править ]

Колеса граф Ш _п представляет собой график , на п вершины строится путем соединения одной вершины каждой вершине в ( п  - 1) - цикле.

Колеса - .${\displaystyle W_{4}}$${\displaystyle W_{9}}$

Ссылки [ править ]