Обхват (теория графов)
Обхват в теории графов — длина наименьшего цикла, содержащегося в данном графе[1]. Если граф не содержит циклов (то есть является ациклическим графом), его обхват по определению равен бесконечности[2]. Например, 4-цикл (квадрат) имеет обхват 4. Квадратная решётка имеет также обхват 4, а треугольная сетка имеет обхват 3. Граф с обхватом четыре и более не имеет треугольников.
Клетки
Кубические графы (все вершины имеют степень три) с как можно меньшим обхватом <math>g</math> известны как <math>g</math>-клетки (или как (3,<math>g</math>)-клетки). Граф Петерсена — это единственная 5-клетка (наименьший кубический граф с обхватом 5), граф Хивуда — это единственная 6-клетка, граф Макги — это единственная 7-клетка, а граф Татта — Коксетера — это единственная 8-клетка[3]. Может существовать несколько (графов-)клеток для данного обхвата. Например, существует три неизоморфных 10-клетки, каждая с 70 вершинами — 10-клетка Балабана[en], граф Харриса[en] и граф Харриса — Вона[en].
- Petersen1 tiny.svg
Граф Петерсена имеет обхват 5
- Heawood Graph.svg
Граф Хивуда имеет обхват 6
- McGee graph.svg
граф Макги имеет обхват 7
- Tutte eight cage.svg
Граф Татта — Коксетера (8-клетка Татта) имеет обхват 8
Обхват и раскраска графа
Для любого положительного целого <math>k</math> существует граф <math>G</math> с обхватом <math>g(G) \ge k</math> и хроматическим числом <math>chi(G) \ge k</math>. Например, граф Грёча является графом без треугольников и имеет хроматическое число 4, а многократное повторение конструкции Мыцельскиана, используемой для создания графа Грёча, образует графы без треугольников со сколь угодно большим хроматическим числом. Пол Эрдёш доказал эту теорему используя вероятностный метод[4].
План доказательства. Назовём циклы длиной не более <math>k</math> короткими, а множества с <math>|G|/k</math> и более вершин — большими. Для доказательства теоремы достаточно найти граф <math>G</math> без коротких циклов и больших независимых множеств вершин. Тогда множества цветов в раскраске не будут большими, и, как следствие, для раскраски потребуется <math>k</math> цветов.
Чтобы найти такой граф, будем фиксировать вероятность выбора <math>p</math> равной <math>n^{\epsilon - 1}</math>. При малых <math>\epsilon</math> в <math>G</math> возникает лишь малое число коротких циклов. Если теперь удалить по вершине из каждого такого цикла, полученный граф <math>H</math> не будет иметь коротких циклов, а его число независимости будет не меньше, чем у графа <math>G</math>[1].
Близкие концепции
Нечётный обхват и чётный обхват графа — это длины наименьшего нечётного цикла и чётного цикла соответственно.
Окружность графа — это длина наибольшего по длине цикла, а не наименьшего.
Рамышления [неизвестный термин] о длине наименьшего нетривиального цикла можно рассматривать как обобщение 1-систолы или большей систолы в систолической геометрии[en].
Напишите отзыв о статье "Обхват (теория графов)"
Примечания
- ↑ 1 2 Рейнгард Дистель. Теория графов. — Новосибирск: Издательство института математики, 2002.
- ↑ Girth -- Wolfram MathWorld.
- ↑ Andries E. Brouwer Cages. Электронное приложение к книге Distance-Regular Graphs (Brouwer, Cohen, Neumaier 1989, Springer-Verlag).
- ↑ Paul Erdős Graph theory and probability // Canadian Journal of Mathematics. — 1959. — Т. 11. — С. 34—38. — DOI:10.4153/CJM-1959-003-9.
<imagemap>: неверное или отсутствующее изображение |
Для улучшения этой статьи желательно?:
|
Отрывок, характеризующий Обхват (теория графов)
Эсаул посмотрел по направлению, указываемому Денисовым.– Едут двое – офицер и казак. Только не предположительно, чтобы был сам подполковник, – сказал эсаул, любивший употреблять неизвестные казакам слова.
Ехавшие, спустившись под гору, скрылись из вида и через несколько минут опять показались. Впереди усталым галопом, погоняя нагайкой, ехал офицер – растрепанный, насквозь промокший и с взбившимися выше колен панталонами. За ним, стоя на стременах, рысил казак. Офицер этот, очень молоденький мальчик, с широким румяным лицом и быстрыми, веселыми глазами, подскакал к Денисову и подал ему промокший конверт.
– От генерала, – сказал офицер, – извините, что не совсем сухо…
Денисов, нахмурившись, взял конверт и стал распечатывать.
– Вот говорили всё, что опасно, опасно, – сказал офицер, обращаясь к эсаулу, в то время как Денисов читал поданный ему конверт. – Впрочем, мы с Комаровым, – он указал на казака, – приготовились. У нас по два писто… А это что ж? – спросил он, увидав французского барабанщика, – пленный? Вы уже в сраженье были? Можно с ним поговорить?
– Ростов! Петя! – крикнул в это время Денисов, пробежав поданный ему конверт. – Да как же ты не сказал, кто ты? – И Денисов с улыбкой, обернувшись, протянул руку офицеру.
Офицер этот был Петя Ростов.
Во всю дорогу Петя приготавливался к тому, как он, как следует большому и офицеру, не намекая на прежнее знакомство, будет держать себя с Денисовым. Но как только Денисов улыбнулся ему, Петя тотчас же просиял, покраснел от радости и, забыв приготовленную официальность, начал рассказывать о том, как он проехал мимо французов, и как он рад, что ему дано такое поручение, и что он был уже в сражении под Вязьмой, и что там отличился один гусар.
– Ну, я г'ад тебя видеть, – перебил его Денисов, и лицо его приняло опять озабоченное выражение.
– Михаил Феоклитыч, – обратился он к эсаулу, – ведь это опять от немца. Он пг'и нем состоит. – И Денисов рассказал эсаулу, что содержание бумаги, привезенной сейчас, состояло в повторенном требовании от генерала немца присоединиться для нападения на транспорт. – Ежели мы его завтг'а не возьмем, они у нас из под носа выг'вут, – заключил он.
В то время как Денисов говорил с эсаулом, Петя, сконфуженный холодным тоном Денисова и предполагая, что причиной этого тона было положение его панталон, так, чтобы никто этого не заметил, под шинелью поправлял взбившиеся панталоны, стараясь иметь вид как можно воинственнее.
– Будет какое нибудь приказание от вашего высокоблагородия? – сказал он Денисову, приставляя руку к козырьку и опять возвращаясь к игре в адъютанта и генерала, к которой он приготовился, – или должен я оставаться при вашем высокоблагородии?
– Приказания?.. – задумчиво сказал Денисов. – Да ты можешь ли остаться до завтрашнего дня?
– Ах, пожалуйста… Можно мне при вас остаться? – вскрикнул Петя.
– Да как тебе именно велено от генег'ала – сейчас вег'нуться? – спросил Денисов. Петя покраснел.
– Да он ничего не велел. Я думаю, можно? – сказал он вопросительно.
– Ну, ладно, – сказал Денисов. И, обратившись к своим подчиненным, он сделал распоряжения о том, чтоб партия шла к назначенному у караулки в лесу месту отдыха и чтобы офицер на киргизской лошади (офицер этот исполнял должность адъютанта) ехал отыскивать Долохова, узнать, где он и придет ли он вечером. Сам же Денисов с эсаулом и Петей намеревался подъехать к опушке леса, выходившей к Шамшеву, с тем, чтобы взглянуть на то место расположения французов, на которое должно было быть направлено завтрашнее нападение.
