Список графиков

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

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

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

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

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

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

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

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

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

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

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

$K_{1}$
$K_{2}$
$K_{3}$
$K_{4}$
$K_{5}$
$K_{6}$
$K_{7}$
$K_{8}$

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

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

$K_{2,3}$
$K_{3,3}$ , граф полезности
$K_{2,4}$
$K_{3,4}$

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

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

$C_{3}$
$C_{4}$
$C_{5}$
$C_{6}$

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

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

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

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

20-фуллерен ( додекаэдрический граф)
24-фуллерен ( график шестиугольной усеченной трапецоэдра )
26-фуллереновый граф
60-фуллерен ( усеченный граф икосаэдра)
70-е годы

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

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

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

Куб
$n=8$ , $m=12$
Октаэдр
$n=6$ , $m=12$
Додекаэдр
$n=20$ , $m=30$
Икосаэдр
$n=12$ , $m=30$

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

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

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

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

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

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

Граф -колесо W _n — это граф на n вершинах, построенный путем соединения одной вершины с каждой вершиной в ( n − 1)-цикле.

Другие графики [ править ]

Этот неполный список содержит определения графов и семейств графов, которые известны под конкретными именами, но не имеют собственной статьи в Википедии.

Механизм [ править ]

Граф передач , обозначаемый G _n , представляет собой граф, полученный путем вставки дополнительной вершины между каждой парой соседних вершин на периметре графа колеса W _n . Таким образом, G _n имеет 2 n +1 вершину и 3 n ребер. ^[4] Зубчатые графы являются примерами квадратных графов и играют ключевую роль в описании запрещенных графов . ^[5] Зубчатые графики также известны как зубчатые колеса и двусторонние колеса .

Шлем [ править ]

Шлемовый граф , обозначаемый H _n , представляет собой граф, полученный путем присоединения одного ребра и узла к каждому узлу внешнего контура колесного графа W _n . ^[6]^[7]

Лобстер [ править ]

Граф омара — это дерево , все вершины которого находятся на расстоянии 2 от центрального пути . ^[8]^[9] Сравните гусеницу .

Интернет [ править ]

Веб - граф Wn _{, r r} — это граф, состоящий из концентрических копий графа циклов Cn _, соответствующие вершины которых соединены «спицами». Таким образом , _{, Wn 1} — тот же граф, что и , _Cn а Wn _,2 — призма .

Веб-граф также определяется как призменный граф Y _{n +1, 3} с удаленными ребрами внешнего цикла. ^[7]^[10]

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

^ Дэвид Грис и Фред Б. Шнайдер, Логический подход к дискретной математике , Springer, 1993, стр. 436.
^ Галлиан, Дж. А. «Динамическое обследование DS6: маркировка графиков». Электронный журнал комбинаторики , DS6, 1-58, 3 января 2007 г. [1] Архивировано 31 января 2012 г. в Wayback Machine .
^ Бринкманн, Гуннар; Платье, Андреас В.М. (1997). «Конструктивный перечень фуллеренов». Журнал алгоритмов . 23 (2): 345–358. дои : 10.1006/jagm.1996.0806 . МР 1441972 .
^ Вайсштейн, Эрик В. «Граф передач» . Математический мир .
^ Бандельт, Х.-Ю.; Чепой, В.; Эппштейн, Д. (2010), «Комбинаторика и геометрия конечных и бесконечных квадратов», SIAM Journal on Discrete Mathematics , 24 (4): 1399–1440, arXiv : 0905.4537 , doi : 10.1137/090760301 , S2CID 10788524
^ Вайсштейн, Эрик В. «График Хелма» . Математический мир .
^ Jump up to: Перейти обратно: ^а ^б «Архивная копия» (PDF) . Архивировано из оригинала (PDF) 31 января 2012 г. Проверено 16 августа 2008 г. {{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка )
^ «Google Дискуссионная группа» . Проверено 5 февраля 2014 г.
^ Вайсштейн, Эрик В. Graph.html «График лобстера» . Математический мир . {{cite web}}: Проверять |url= ценность ( помощь )
^ Вайсштейн, Эрик В. «Веб-график» . Математический мир .

[1] Дэвид Грис и Фред Б. Шнайдер, Логический подход к дискретной математике , Springer, 1993, стр. 436.

[2] Галлиан, Дж. А. «Динамическое обследование DS6: маркировка графиков». Электронный журнал комбинаторики , DS6, 1-58, 3 января 2007 г. [1] Архивировано 31 января 2012 г. в Wayback Machine .

[3] Бринкманн, Гуннар; Платье, Андреас В.М. (1997). «Конструктивный перечень фуллеренов». Журнал алгоритмов . 23 (2): 345–358. дои : 10.1006/jagm.1996.0806 . МР 1441972 .

[4] Вайсштейн, Эрик В. «Граф передач» . Математический мир .

[5] Бандельт, Х.-Ю.; Чепой, В.; Эппштейн, Д. (2010), «Комбинаторика и геометрия конечных и бесконечных квадратов», SIAM Journal on Discrete Mathematics , 24 (4): 1399–1440, arXiv : 0905.4537 , doi : 10.1137/090760301 , S2CID 10788524

[6] Вайсштейн, Эрик В. «График Хелма» . Математический мир .

[combinatorics.org-7] Jump up to: Перейти обратно: ^а ^б «Архивная копия» (PDF) . Архивировано из оригинала (PDF) 31 января 2012 г. Проверено 16 августа 2008 г. {{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка )

[8] «Google Дискуссионная группа» . Проверено 5 февраля 2014 г.

[9] Вайсштейн, Эрик В. Graph.html «График лобстера» . Математический мир . {{cite web}}: Проверять |url= ценность ( помощь )

[10] Вайсштейн, Эрик В. «Веб-график» . Математический мир .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]