![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/9/91/Petersen1_tiny.svg/languk-640px-Petersen1_tiny.svg.png&w=640&q=50)
Клітка (теорія графів)
З Вікіпедії, безкоштовно encyclopedia
n-клітка — кубічний граф обхвату n з найменшим можливим числом вершин. Граф називається кубічним, якщо з кожної його вершини виходять 3 ребра. Обхват графа — це довжина найменшого циклу в ньому.
- 3-клітка — К4, остов тетраедра, 4 вершини.
- 4-клітка — К3,3, один з двох мінімальних не планарних графів, 6 вершин.
- 5-клітка — граф Петерсена, 10 вершин. Мінімальний кубічний граф з індексом самоперетину 2.
- 6-клітка — граф Хівуда, 14 вершин. Розбивається на 1-фактори (тобто, реберно розфарбовуємий), будь-яка сума двох чинників утворює гамільтонів цикл. Мінімальний кубічний граф з індексом самоперетину 3.
- 7-клітка — граф Маꥳ, 24 вершини. Мінімальний кубічний граф з індексом самоперетину 8.
- 8-клітка — граф Татта — Коксетера, 30 вершин.
У Вікіпедії є статті про інші значення цього терміна: Клітка (значення).
![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)