![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/9/91/Petersen1_tiny.svg/langru-640px-Petersen1_tiny.svg.png&w=640&q=50)
Клетка (теория графов)
регулярный граф, который содержит так мало вершин, насколько возможно для его обхвата / Материал из Википедии — свободной encyclopedia
Уважаемый Wikiwand AI, давайте упростим задачу, просто ответив на эти ключевые вопросы:
Перечислите основные факты и статистические данные о Клетка (теория графов)?
Кратко изложите эту статью для 10-летнего ребёнка
ПОКАЗАТЬ ВСЕ ВОПРОСЫ
У этого термина существуют и другие значения, см. Клетка (значения).
n-клетка — кубический граф обхвата n с наименьшим возможным числом вершин. Граф называется кубическим, если из каждой его вершины выходят 3 ребра. Обхват графа — это длина наименьшего цикла в нём.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/9/91/Petersen1_tiny.svg/220px-Petersen1_tiny.svg.png)
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/4/47/Heawood_tiny.svg/220px-Heawood_tiny.svg.png)
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a9/McGee_graph.svg/220px-McGee_graph.svg.png)
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/4/41/Tutte_eight_cage.svg/320px-Tutte_eight_cage.svg.png)
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/5/58/Hoffman_singleton_graph_circle2.gif/320px-Hoffman_singleton_graph_circle2.gif)
Для каждого 2 < n < 9 существует единственная n-клетка, причем все эти графы обладают высокой симметрией (являются унитранзитивными). Кроме того, при изображении на плоскости они часто дают экстремальное количество самопересечений, далее индекс самопересечения[англ.].
- 3-клетка — К4, остов тетраэдра, 4 вершины.
- 4-клетка — К3,3, один из двух минимальных не планарных графов, 6 вершин.
- 5-клетка — Граф Петерсена, 10 вершин. Минимальный кубический граф с индексом самопересечения 2.
- 6-клетка — Граф Хивуда, 14 вершин. Разбивается на 1-факторы (то есть, реберно раскрашиваем), любая сумма двух факторов образует гамильтонов цикл. Минимальный кубический граф с индексом самопересечения 3.
- 7-клетка — Граф МакГи, 24 вершины. Минимальный кубический граф с индексом самопересечения 8.
- 8-клетка — Граф Татта — Коксетера, 30 вершин.