Клетка (теория графов)
n-клетка — кубический граф обхвата n с наименьшим возможным числом вершин. Граф называется кубическим, если из каждой его вершины выходят 3 ребра. Обхват графа — это длина наименьшего цикла в нём.
Для каждого 2 < n < 9 существует единственная n-клетка, причем все эти графы обладают высокой симметрией (являются унитранзитивными). Кроме того, при изображении на плоскости они часто дают экстремальное количество самопересечений, далее индекс самопересечения (англ.).
- 3-клетка — К4, остов тетраэдра, 4 вершины.
- 4-клетка — К3,3, один из двух минимальных не планарных графов, 6 вершин.
- 5-клетка — Граф Петерсена, 10 вершин. Минимальный кубический граф с индексом самопересечения 2.
- 6-клетка — Граф Хивуда, 14 вершин. Разбивается на 1-факторы (то есть, реберно раскрашиваем), любая сумма двух факторов образует гамильтонов цикл. Минимальный кубический граф с индексом самопересечения 3.
- 7-клетка — Граф МакГи, 24 вершины. Минимальный кубический граф с индексом самопересечения 8.
- 8-клетка — Граф Татта — Коксетера, 30 вершин.
Обобщённое определение
(r,n)-клетка — регулярный граф степени r (то есть из каждой вершины которого выходит ровно r рёбер) и обхвата n с наименьшим возможным числом вершин.
Тривиальные семейства
- (2,n)-клетками являются, очевидно, циклические графы Cn
- (r-1,3)-клетки — полные графы Кr из r вершин
- (r,4)-клетки — полные двудольные графы Кr,r, у которых в каждой доле находится по r вершин
Нетривиальные представители
- (7,5)-клетка — Граф Гофмана-Синглтона, 50 вершин.
Известны ещё некоторые клетки. В таблице ниже показано количество вершин в (r,n)-клетках степени 3≤r≤7 и обхвата 3≤n≤12. Клетки для этих и бо́льших r и n описаны здесь: [people.csse.uwa.edu.au/gordon/cages/allcages.html] (на английском языке).
| n: | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| r = 3: | 4 | 6 | 10 | 14 | 24 | 30 | 58 | 70 | 112 | 126 |
|---|---|---|---|---|---|---|---|---|---|---|
| r = 4: | 5 | 8 | 19 | 26 | 67 | 80 | 275 | 384 | 728 | |
| r = 5: | 6 | 10 | 30 | 42 | 152 | 170 | 2730 | |||
| r = 6: | 7 | 12 | 40 | 62 | 294 | 312 | 7812 | |||
| r = 7: | 8 | 14 | 50 | 90 |
Графы Мура
Количество вершин в (r,n)-клетке больше или равно
- <math>1+r\sum_{i=0}^{(n-3)/2}(r-1)^i</math> для нечётных n и
- <math>2\sum_{i=0}^{(n-2)/2}(r-1)^i</math> для чётных.
Если имеет место равенство, то соответствующий граф называется графом Мура. В то время как клетка существует для всяких r > 2 и n > 2, нетривиальных графов Мура гораздо меньше. Из вышеупомянутых клеток, графами Мура являются Граф Петерсена, граф Хивуда, граф Татта — Коксетера и граф Гофмана-Синглтона. Доказано,[1][2][3] что все нечётные случаи исчерпываются n = 5, r = 2, 3, 7 и, возможно, 57, а чётные n = 6, 8, 12.
Напишите отзыв о статье "Клетка (теория графов)"
Примечания
Литература
- Ф. Харари Теория графов. — М.: УРСС, — 2003. — 300 с — ISBN 5-354-00301-6.
Ссылки
- Weisstein, Eric W. [mathworld.wolfram.com/CageGraph.html Клеточный граф] (англ.) на сайте Wolfram MathWorld.
- people.csse.uwa.edu.au/gordon/cages/ (англ.)
|
Это заготовка статьи по математике. Вы можете помочь проекту, дополнив её. |
Отрывок, характеризующий Клетка (теория графов)
– Кю… – с усилием выговорил Залетаев. – Кью ю ю… – вытянул он, старательно оттопырив губы, – летриптала, де бу де ба и детравагала, – пропел он.– Ай, важно! Вот так хранцуз! ой… го го го го! – Что ж, еще есть хочешь?
– Дай ему каши то; ведь не скоро наестся с голоду то.
Опять ему дали каши; и Морель, посмеиваясь, принялся за третий котелок. Радостные улыбки стояли на всех лицах молодых солдат, смотревших на Мореля. Старые солдаты, считавшие неприличным заниматься такими пустяками, лежали с другой стороны костра, но изредка, приподнимаясь на локте, с улыбкой взглядывали на Мореля.
– Тоже люди, – сказал один из них, уворачиваясь в шинель. – И полынь на своем кореню растет.
– Оо! Господи, господи! Как звездно, страсть! К морозу… – И все затихло.
Звезды, как будто зная, что теперь никто не увидит их, разыгрались в черном небе. То вспыхивая, то потухая, то вздрагивая, они хлопотливо о чем то радостном, но таинственном перешептывались между собой.
Х
Войска французские равномерно таяли в математически правильной прогрессии. И тот переход через Березину, про который так много было писано, была только одна из промежуточных ступеней уничтожения французской армии, а вовсе не решительный эпизод кампании. Ежели про Березину так много писали и пишут, то со стороны французов это произошло только потому, что на Березинском прорванном мосту бедствия, претерпеваемые французской армией прежде равномерно, здесь вдруг сгруппировались в один момент и в одно трагическое зрелище, которое у всех осталось в памяти. Со стороны же русских так много говорили и писали про Березину только потому, что вдали от театра войны, в Петербурге, был составлен план (Пфулем же) поимки в стратегическую западню Наполеона на реке Березине. Все уверились, что все будет на деле точно так, как в плане, и потому настаивали на том, что именно Березинская переправа погубила французов. В сущности же, результаты Березинской переправы были гораздо менее гибельны для французов потерей орудий и пленных, чем Красное, как то показывают цифры.
Единственное значение Березинской переправы заключается в том, что эта переправа очевидно и несомненно доказала ложность всех планов отрезыванья и справедливость единственно возможного, требуемого и Кутузовым и всеми войсками (массой) образа действий, – только следования за неприятелем. Толпа французов бежала с постоянно усиливающейся силой быстроты, со всею энергией, направленной на достижение цели. Она бежала, как раненый зверь, и нельзя ей было стать на дороге. Это доказало не столько устройство переправы, сколько движение на мостах. Когда мосты были прорваны, безоружные солдаты, московские жители, женщины с детьми, бывшие в обозе французов, – все под влиянием силы инерции не сдавалось, а бежало вперед в лодки, в мерзлую воду.
Стремление это было разумно. Положение и бегущих и преследующих было одинаково дурно. Оставаясь со своими, каждый в бедствии надеялся на помощь товарища, на определенное, занимаемое им место между своими. Отдавшись же русским, он был в том же положении бедствия, но становился на низшую ступень в разделе удовлетворения потребностей жизни. Французам не нужно было иметь верных сведений о том, что половина пленных, с которыми не знали, что делать, несмотря на все желание русских спасти их, – гибли от холода и голода; они чувствовали, что это не могло быть иначе. Самые жалостливые русские начальники и охотники до французов, французы в русской службе не могли ничего сделать для пленных. Французов губило бедствие, в котором находилось русское войско. Нельзя было отнять хлеб и платье у голодных, нужных солдат, чтобы отдать не вредным, не ненавидимым, не виноватым, но просто ненужным французам. Некоторые и делали это; но это было только исключение.
