Русская Википедия:Теория графов

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Файл:Leonhard Euler 1741-1766 by F B Frey.png
Отец теории графов Леонард Эйлер

Тео́рия гра́фов — раздел дискретной математики, изучающий графы, одна из ветвей топологии. В самом общем смысле граф — это множество точек (вершин, узлов), которые соединяются множеством линий (рёбер, дуг)Шаблон:Sfn. Теория графов (то есть систем линий, соединяющих заданные точки) включена в учебные программы для начинающих математиков, посколькуШаблон:SfnШаблон:SfnШаблон:SfnШаблон:Sfn:

  • как и геометрия, обладает наглядностью;
  • как и теория чисел, проста в объяснении и имеет сложные нерешённые задачи;
  • не имеет громоздкого математического аппарата («комбинаторные методы нахождения нужного упорядочения объектов существенно отличаются от классических методов анализа поведения систем с помощью уравнений»Шаблон:Sfn);
  • имеет выраженный прикладной характер.

На протяжении более сотни лет развитие теории графов определялось в основном проблемой четырёх красок. Решение этой задачи в 1976 году оказалось поворотным моментом истории теории графов, после которого произошло её развитие как основы современной прикладной математики. Универсальность графов незаменима при проектировании и анализе коммуникационных сетейШаблон:Sfn.

Теория графов, как математическое орудие, приложима как к наукам о поведении (теории информации, кибернетике, теории игр, теории систем, транспортным сетям), так и к чисто абстрактным дисциплинам (теории множеств, теории матриц, теории групп и так далее)Шаблон:SfnШаблон:Sfn.

Несмотря на разнообразные, усложнённые, малопонятные и специализированные термины многие модельные (схемные, структурные) и конфигурационные проблемы переформулируются на языке теории графов, что позволяет значительно проще выявить их концептуальные трудностиШаблон:Sfn. В разных областях знаний понятие «граф» может встречаться под следующими названиями:

и так далееШаблон:Sfn.

Первые использования и открытия графов

Шаблон:Основная статья

Теория графов как раздел прикладной математики «открывалась» несколько раз. Ключ к пониманию теории графов и её комбинаторной сущности отражены в словах Джеймса Сильвестра: «Теория отростков (Шаблон:Lang-en) — одна из теорий чистого обобщения, для неё не существенны ни размеры, ни положение объекта; в ней используются геометрические линии, но они относятся к делу не больше, чем такие же линии в генеалогических таблицах помогают объяснять законы воспроизведения»Шаблон:Sfn.

Первое использование диаграммы графа в науке

Файл:Дерево Порфирия.png
Дерево Порфирия

Диаграмма одной из разновидностей графа — дерева — использовалась издавна (конечно, без понимания, что это «граф»). Генеалогическое древо применялось для наглядного представления родственных связей. Но только античный комментатор работ Аристотеля финикийский философ и математик Порфирий использовал изображение дерева в науке как иллюстрацию дихотомического деления в своей работе «Введение» (Шаблон:Lang-el, Шаблон:Lang-la) для классификации философского понятия материиШаблон:Sfn.

Первое использование и «открытие» теории графов

Шаблон:Основная статья

Файл:Königsberg graph.svg
Мультиграф задачи о кёнигсбергских мостах

Швейцарский, прусский и российский математик Леонард Эйлер в статье (на латинском языке, изданной Петербургской академией наук) о решении знаменитой задачи о кёнигсбергских мостах, датированной 1736 годом, первым применил идеи теории графов при доказательстве некоторых утверждений. При этом Эйлер не использовал ни сам термин «граф», ни какие-либо термины теории графов, ни изображения графовШаблон:Sfn. Леонард Эйлер считается отцом теории графов (как и топологии), открывшим понятие графаШаблон:Sfn, а 1736 год назначен годом рождения теории графовШаблон:Sfn.

Второе «открытие» графов

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

Третье «открытие» графов

В 1857 году английский математик Артур Кэли, занимаясь практическими задачами органической химии, открыл важный класс графов — деревья. Кэли пытался перечислить химические изомеры предельных (насыщенных) углеводородов CnH2n+2 с фиксированным числом n атомов углеродаШаблон:Sfn.

Четвёртое «открытие» графов

Шаблон:Основная статья

В 1859 году ирландский математик сэр Уильям Гамильтон придумал игру «Вокруг света». В этой игре использовался додекаэдр, каждая из 20 вершин которого соответствовала известному городу. От играющего требовалось обойти «вокруг света», то есть пройти по рёбрам додекаэдра так, чтобы пройти через каждую вершину ровно один разШаблон:Sfn.

Пятое «открытие» графов

В 1869 году, независимо от Артура Кэли, французский математик Камиль Жордан (в частности, в статье « Sur les assemblages de lignes ») придумал и исследовал деревья в рамках чистой математики. При этом Жордан использовал термины теории графов «вершина» (Шаблон:Lang-fr) и «ребро» (Шаблон:Lang-fr), но вместо термина «граф» было «соединение рёбер» (Шаблон:Lang-fr) или просто «соединение» (Шаблон:Lang-fr). Рисунки Жордан не использовалШаблон:Sfn. При этом Жордан не подозревал о значении своего открытия для органической химииШаблон:Sfn.

Шаблон:Начало цитаты Soient x, y, z, u, … des points en nombre quelconque ; xy, xz, yu, … des arêtes droites ou courbes, mais non bifurquées, dont chacune joint ensemble deux de ces points. Nous appellerons un semblable système un assemblage d’arêtes, dont x, y, z, u, … sont les sommets. Шаблон:Конец цитаты

Возникновение слова «граф»

Первое появление слова «граф» в смысле теории графов состоялось в 1878 году в краткой заметке (на английском языке) английского математика Джеймса Сильвестра в журнале Nature и имеет графическое происхождение как обобщение понятий «диаграмма Кекуле» и «химикограф»Шаблон:SfnШаблон:Sfn.

Шаблон:Начало цитаты Every invariant and covariant thus becomes expressible by a graph precisely identical with a Kekuléan diagram or chemicograph. Шаблон:Конец цитаты

В переводе:

Шаблон:Начало цитаты Таким образом, каждый инвариант и ковариант выражается некоторым графом, точно идентичным диаграмме Кекуле или химикографу. Шаблон:Конец цитаты

Начало систематического использования слова «граф» и диаграмм графов

Файл:Denes Konig 1928.jpg
Денеш Кёниг
Файл:Domino 28 graph.png
Псевдограф домино (28 костей)

Мы привычно рисуем точки, изображающие людей, населённые пункты, химические молекулы и т. д., и соединяем эти точки линиями, означающими отношения. Это социограммы (в психологии), симплексы (в топологии), электрические цепи (в физике), диаграммы организации (в экономике), сети коммуникаций, генеалогические деревья и т. д. В начале XX века венгерский математик Денеш Кёниг первый предложил называть эти схемы «графами» и изучать их общие свойстваШаблон:Sfn. В 1936 году вышла первая в мире книга по теории графов (на немецком языке) Денеша Кёнига «Теория конечных и бесконечных графов» с большей частью результатов за прошедшие 200 лет, начиная с 1736 года — даты выхода первой статьи Леонарда Эйлера по теории графов с решением задачи о кёнигсбергских мостахШаблон:Sfn. В частности, в книге Кёнига имеется общий параграф для задачи о кёнигсбергских мостах и задаче о домино (построение замкнутой цепи из всех костей домино по правилам игры)Шаблон:SfnШаблон:Sfn.

История возникновения теории графов

Шаблон:Основная статья

Теория графов (другими словами, системы линий, соединяющих заданные точки) очень удобна для начинающихШаблон:Sfn:

  • имеет геометрическую наглядность;
  • имеет математическую содержательность;
  • не имеет громоздкого математического аппарата.

«Как и теория чисел, теория графов концептуально проста, но порождает сложные нерешенные проблемы. Как и геометрия, она визуально приятна. Эти два аспекта, наряду с их разнообразными приложениями, делают теорию графов идеальным предметом для включения в учебные программы по математике»Шаблон:Sfn.

Возникновение этого раздела математики в XVIII веке связано с математическими головоломками. Достаточно продолжительное время теория графов была «несерьёзна» и целиком связана с играми и развлечениями. Такая судьба теории графов повторяет судьбу теории вероятностей, также сначала находившей себе применение только в азартных играхШаблон:Sfn.

Краткая хронология событий развития теории графовШаблон:Sfn
Год Событие
1735 Представление Эйлером статьи по теории графов в Петербургской академии наук
1736 Год, считающийся годом рождения теории графов
1741 Публикация (датированная 1736 годом) статьи Эйлера по теории графов в Петербургской академии наук
1852 Френсис Гатри сообщает о проблеме четырёх красок Августу де Моргану
1879 Историческая публикация 1879 года с объяснением проблемы четырёх красок Артура Кэли
1879 Ошибочное «доказательство» проблемы четырёх красок Альфредом Кемпе
1890 Перси Джон Хивуд обнаружил ошибку в «доказательстве» Кемпе, доказал, что теорема верна, если «четыре» заменить на «пять», обобщил понятие «карты страны» с плоскости на замкнутые поверхности и сформулировал гипотезу Хивуда
1927 Лев Семёнович Понтрягин доказал (но не опубликовал) теорему Понтрягина — Куратовского
1930 Казимеж Куратовский опубликовал (независимо о Понтрягина) теорему Понтрягина — Куратовского
1936 Вышла первая в мире книга по теории графов Денеша Кёнига «Теория конечных и бесконечных графов»
1968 Группа математиков из разных стран доказала гипотезу Хивуда
1976 Группа математиков осуществили первое компьютерное доказательство теоремы о четырёх красках
1977 Фрэнк Харари основал журнал «Теория графов»

Геометрия положения

Отцом теории графов (как и топологии) считается швейцарский математик и механик Леонард Эйлер (1707—1783)Шаблон:Sfn, написавший статью с решением задачи о кёнигсбергских мостах. Эйлер писалШаблон:Sfn:

Шаблон:Начало цитаты В дополнение к той ветви геометрии, которая занимается величинами и которой всегда уделялось самое большое внимание, существует другая ветвь, прежде почти неизвестная, о которой впервые упоминал Лейбниц, назвав ее геометрией положения [geometria situs]. Эта ветвь занимается только определением положения и его свойствами, она не включает ни измерений, ни вычислений, с ними связанных... Шаблон:Конец цитаты

Далее Эйлер пишет, что не ясно, какие задачи и методы их решения относятся к геометрии положения. Тем не менее, Эйлер считал кёнигсбергские мосты именно такой задачей, о чём говорит и заголовок статьи. В действительности, Готфрид Лейбниц не позже 1679 года написал в письме к Христиану ГюйгенсуШаблон:Sfn:

Шаблон:Начало цитаты Меня не удовлетворяет алгебра в том отношении, что не позволяет получить ни кратчайшие доказательства, ни самые красивые конструкции геометрии. Следовательно, в силу этого я считаю, что нам нужен другой способ анализа, геометрический или линейный, который прямо бы работал с положением точно так же, как алгебра работает с величиной... Шаблон:Конец цитаты

Лейбниц, введя термин analysis situs (анализ положения), не заложил основы новой математической дисциплины, но указал направление будущих исследованийШаблон:Sfn.

Задача о кёнигсбергских мостах

Шаблон:Основная статья

Публикация статьи Леонарда Эйлера «Решение одной задачи, связанной с геометрией положения» о решении задачи о кёнигсбергских мостах имеет следующую историю:

  • Шаблон:СС3 — письмо Шаблон:Iw, австрийскому астроному и математику, которое целиком посвящено задаче о кёнигсбергских мостахШаблон:Sfn;
  • Шаблон:СС3 — письмо Шаблон:Iw, немецкому политическому деятелю и астроному, в конце которого идёт речь об основных идеях статьиШаблон:Sfn;

Шаблон:Начало цитаты Leonhardi Euleri. Solutio problematis ad geometriam situs pertinentis / Commentarii academiae scientiarum Petropolitanae. 8 (1736). 1741. P. 128—140. Шаблон:Конец цитаты В переводеШаблон:Sfn: Шаблон:Начало цитаты Леонард Эйлер. Решение одной задачи, связанной с геометрией положения / Труды Петербургской академии наук. 8 (1736). 1741. С. 128—140. Шаблон:Конец цитаты

Поскольку выход статьи Эйлера из печати датируется 1736 годом (и обоих писем тоже), этот год назначен датой рождения теории графовШаблон:Sfn.

Эйлер в своей статье так сформулировал задачу о семи кёнигсбергских мостахШаблон:Sfn: Шаблон:Начало цитаты В городе Кенигсберге, в Пруссии, есть остров, называемый Кнайпхоф; река, окружающая его, делится на два рукава, что можно увидеть на рисунке. Рукава этой реки пересекают семь мостов а, Ь, с, d, e, f и g. В связи с этими мостами был поставлен вопрос, можно ли совершить по ним прогулку так, чтобы пройти по каждому из этих мостов, причём ровно по одному разу.

Файл:Solutio problematis ad geometriam situs pertinentis, Fig. 1 - Cleaned Up.png

Шаблон:Конец цитаты

В конце статьи Эйлер записал выводы вполне современным языкомШаблон:Sfn: Шаблон:Начало цитаты 20. Значит в каждом возможном случае следующее правило позволяет непосредственно и без труда выяснить, можно ли осуществить прогулку по всем мостам без повторений:

Если имеется более двух областей, в которые ведёт нечётное число мостов, можно заявить с уверенностью, что такая прогулка невозможна.

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

Если, наконец, нет ни одной области, в которую ведёт нечётное число мостов, прогулка с требуемыми условиями осуществима, причём начинаться она может в любой области.

Следовательно, с помощью этого правила поставленная задача может быть полностью решена. Шаблон:Конец цитаты

Теорема о четырёх красках

Шаблон:Основная статья

Теорема о четырёх красках — наиболее известное утверждение в теории графов (а может, и во всей математике), долгое время не поддающееся доказательству (а может, так и не доказанное). Эту легендарную задачу в течение пяти минут может объяснить любой математик любому прохожему, после чего оба, понимая проблему, решить её не смогут. Следующая цитата из ставшей исторической статьи 1965 года американского математика Шаблон:IwШаблон:Sfn: Шаблон:Начало цитаты [Предполагается, что] любую карту на плоскости или поверхности шара можно раскрасить только четырьмя красками таким образом, чтобы никакие две смежные страны не были одного и того же цвета. Каждая страна должна состоять из одной связной области, а смежными называются страны, которые имеют общую границу в виде линии (а не просто одной общей точки). Эта гипотеза тесно связана с наиболее модными направлениями теории графов, а в разделе математики, называемом комбинаторной топологией, она действовала подобно катализатору. На протяжении более чем половины столетия многие математики (кое-кто говорит, что все) предпринимали попытки решить эту проблему, но смогли доказать справедливость гипотезы только для отдельных случаев... Единодушно признается, что гипотеза справедлива, но маловероятно, что она будет доказана в общем случае. Кажется, что ей на некоторое время предназначено сохранить отличительную черту быть одновременно и наиболее простой, и наиболее заманчивой нерешённой проблемой математики. Шаблон:Конец цитаты

Файл:Grafo ejemplo 5 conecsi.png
Карта стран и соответствующий ей граф

Теорема о четырёх красках относится к теории графов, так как каждая карта порождает граф следующим образом:

  • страны (включая внешнюю область) — это вершины;
  • вершины смежных стран соединяются ребром.

Этот граф рисуется на плоскости без пересечения рёбер. Теорема о четырёх красках доказана, если доказано, что вершины любого подобного графа можно раскрасить четырьмя красками так, чтобы смежные вершины имели разные цветаШаблон:Sfn.

Теорема о четырёх красках имеет легендарную историю, интересную и иногда непонятнуюШаблон:SfnШаблон:Sfn:

  • имеются неподтверждённые сообщения, что Августу Мёбиусу эта проблема была известна в 1840 году;
  • точно известно, что Шаблон:Iw, южноафриканский математик и ботаник, 23 октября 1852 года сообщил шотландскому математику и логику Августу де Моргану о данной проблеме, после чего велись обсуждения в узких кругах математиков и дилетантов;
  • историческая публикация 1879 года с объяснением проблемы

Шаблон:Начало цитаты Cayley Arthur. On the Colouring of Maps // Proceedings of the Royal Geographical Society. 1879. Vol. 1, No. 4. P. 259–261 Шаблон:Конец цитаты принадлежит Артуру Кэли, английскому математику. Теперь проблема приобретает большую известность;

  • в том же 1879 году вышла публикация ошибочного «доказательства» проблемы

Шаблон:Начало цитаты Kempe A. B. On the Geographical Problem of the Four Colours // American Journal of Mathematics. 1879. Vol. 2, No. 3. P. 193–200 Шаблон:Конец цитаты английского церковного юриста и любителя математики Шаблон:Iw. Это было не только первое из многих ошибочных «доказательств», но и самое «правильное»: на основе идей этой статьи удалось сначала доказать, что пяти красок хватит, а затем провести полное компьютерное доказательство теоремы о четырёх красках;

  • ошибку в «доказательстве» Кемпе через 11 лет в 1890 году обнаружил английский математик Перси Джон Хивуд, и в опубликованной по этому поводу статье

Шаблон:Начало цитаты Heawood P. J. Map colour theorems //Quarterly Journal of Pure and Applied Mathematics. 24 (1890). P. 332—338 Шаблон:Конец цитаты также доказал, что теорема верна, если «четыре» заменить на «пять», и, кроме того, обобщил понятие «карты страны» с плоскости на замкнутые поверхности и сформулировал гипотезу Хивуда;

  • в 1968 году группа математиков из разных стран доказала гипотезу Хивуда;
  • в 1976 году американские математики осуществили первое компьютерное доказательство теоремы о четырёх красках.

Теорема Понтрягина — Куратовского

Шаблон:Основная статья

Теория графов содержит топологические аспекты. Первым результатом в этом направлении является формула Эйлера в теории графов, полученная им в 1736 году. Следующий результат в виде теоремы Понтрягина — Куратовского был получен только через 191 год: в 1927 году советский математик Лев Семёнович Понтрягин доказал (но не опубликовал) этот результат, а в 1930 году польский математик Казимеж Куратовский опубликовал его (независимо от Понтрягина). Теорему Понтрягина — Куратовского также называют критерием Понтрягина — КуратовскогоШаблон:Sfn:

Планарный граф — это граф, который можно нарисовать на плоскости без пересечения рёбер. Граф, который нельзя так нарисовать, называется непланарным. Ниже показаны два важных непланарных графа, обозначаемых <math>K_5</math> и <math>K_{3,3}</math>, их нельзя нарисовать на плоскости без пересечения рёбер. Эти два графа выделяются среди других тем, что только они используются в критерии Понтрягина — КуратовскогоШаблон:Sfn.

Файл:Tesseract graph nonplanar visual proof.svg
Доказательство без слов непланарности тессеракта. Вверху — тессеракт содержит <math>K_5</math>, внизу — <math>K_{3,3}</math>

До появления критерия Понтрягина — Куратовского доказательство планарности или непланарности графов было очень сложной проблемой теории графовШаблон:Sfn. Шаблон:Начало цитаты Теорема Понтрягина — Куратовского. Граф планарен тогда и только тогда, когда он ни в каком виде не содержит графов <math>K_5</math> и <math>K_{3,3}</math>. Шаблон:Конец цитаты

Справа приведены два простых доказательства без слов того, что остов четырёхмерного гиперкуба (тессеракта) как граф непланарен. На верхнем рисунке показано, что в тессеракте содержится полный граф с пятью вершинами <math>K_5</math>, на нижнем — полный двудольный граф (3, 3) <math>K_{3,3}</math>.

Основные легендарные издания

Файл:Frank Harary 1972.jpg
Один из отцов современной теории графов Фрэнк Харари

Ранняя теория графов — теория графов до 1936 года, до выхода книги КёнигаШаблон:Sfn.

В 1936 году вышла первая в мире книга по теории графов венгерского математика Денеша Кёнига «Теория конечных и бесконечных графов» на немецком языке: Шаблон:Начало цитаты Kőnig, Dénes. Theorie der endlichen und unendlichen Graphen. Leipzig: Akademische Verlagsgesellschaf, 1936. Шаблон:Конец цитаты Эта книга состояла из 248 страниц (без учёта предисловия, оглавления и библиографии) и большей части результатов теории графов за 200 лет — с даты выхода статьи Леонарда Эйлера с решением задачи о кёнигсбергских мостахШаблон:Sfn.

Современная теория графов — теории графов, начиная с 1936 года, с момента выхода книги Кёнига. С времени выхода книги Кёнига, но в основном с конца Второй мировой войны, теория графов начала ускоренно развиваться. Этот рост заключался не только в увеличении числа книг по теории графов, но и в том, что развились специальные аспекты теории графовШаблон:Sfn:

Один из отцов современной теории графов — Фрэнк Харари, который в 1977 году основал журнал Шаблон:IwШаблон:SfnШаблон:Sfn.

Книга Фрэнка Харари «Теория графов» стала классической де-фактоШаблон:SfnШаблон:Sfn.

Книга Рейнгарда Дистеля «Теория графов» (выдержала 5 редакций) не имеет конкурентов в русскоязычной библиографии. Этот канон вводного курса в теорию графов инициировал отождествление некоторых областей обучения и исследованияШаблон:SfnШаблон:Sfn.

Описание ранней теории графов

Ранняя теория графов продолжалась ровно 200 лет, от первой статьи по теории графов Леонарда Эйлера 1736 года до первой книги по теории графов Денеша Кёнига 1936 года. В предисловии к книге написано, что изложение теории графов ограничивается областью абсолютных графов (абстрактных графов в современной терминологии), а относительная теория графов (топологическая теория графов в современной терминологии) и перечислительная теория графов не рассматриваются. Ниже приведено полное название книги Денеша Кёнига и её краткое оглавление, состоящее из названий главШаблон:SfnШаблон:SfnШаблон:Sfn.

  • Теория конечных и бесконечных графов. Комбинаторная топология одномерных комплексов (Шаблон:Lang-de, Шаблон:Lang-en).
Глава I. Основы (Шаблон:Lang-de, Шаблон:Lang-en).
Глава II. Эйлеровы и гамильтоновы обходы (Шаблон:Lang-de, Шаблон:Lang-en).
Глава III. Задача о лабиринте (Шаблон:Lang-de, Шаблон:Lang-en).
Глава IV. Ациклические графы (Шаблон:Lang-de, Шаблон:Lang-en).
Глава V. Центры деревьев (Шаблон:Lang-de, Шаблон:Lang-en).
Глава VI. Специальные методы исследования бесконечных графов (Шаблон:Lang-de, Шаблон:Lang-en).
Глава VII. Основные задачи ориентированных графов (Шаблон:Lang-de, Шаблон:Lang-en).
Глава VIII. Некоторые приложения ориентированных графов (логика — теория игр — теория групп) (Шаблон:Lang-de, Шаблон:Lang-en).
Глава IX. Циклы, звёзды и соответствующие линейные формы (Шаблон:Lang-de, Шаблон:Lang-en).
Глава X. Композиция циклов и звёзд (Шаблон:Lang-de, Шаблон:Lang-en).
Глава XI. Факторизация регулярных конечных графов (Шаблон:Lang-de, Шаблон:Lang-en).
Глава XII. Факторизация регулярных конечных графов третьей степени (Шаблон:Lang-de, Шаблон:Lang-en).
Глава XIII. Факторизация регулярных бесконечных графов (Шаблон:Lang-de, Шаблон:Lang-en).
Глава XIV. Разделяющие вершины и множества вершин (Шаблон:Lang-de, Шаблон:Lang-en).

Проблемы представления теории графов

Проблемы терминологии

Обычно упоминаемый факт пестроты и неупорядоченности терминологии и обозначений в теории графов — частично следствие того, что этой наукой интересуются специалисты из весьма разнообразных областей знанияШаблон:Sfn. Кроме того, в терминологии самой теории графов имеется некоторый люфт, немного затрудняющий изучение и представление теории графов. С особой осторожностью приходится применять такие понятия, как «маршрут», «путь» и «цепь», которые, означая почти одно и то же, могут принимать разные конкретные значения у разных авторовШаблон:Sfn.

Вот что писал в начале своей классической книги Фрэнк Харари (переизданной в 2003 году)Шаблон:SfnШаблон:Sfn.

Шаблон:Начало цитаты Большинство специалистов по теории графов употребляют в книгах, статьях и лекциях свою собственную терминологию. На конференциях по теории графов каждый выступающий, чтобы избежать неправильного понимания, считает необходимым определить прежде всего язык, которым он будет пользоваться. Даже само слово «граф» не является священным. Некоторые авторы действительно определяют «граф» как граф, другие же имеют в виду такие понятия, как мультиграф, псевдограф, ориентированный граф или сеть. Нам кажется, что единообразие в терминологии теории графов никогда не будет достигнуто, но, может быть, оно и ни к чему.Шаблон:Конец цитаты

Наиболее радикален взгляд с позиций конструктивной математикиШаблон:SfnШаблон:Sfn.

Шаблон:Начало цитаты …нам кажется не слишком важным, как назвать точки, соединённые линиями: «графом», «орграфом», «мультиграфом», «псевдографом». Графы, построенные на основе реальных структур, слишком разнообразны, чтобы их классифицировать по тем признакам, о которых говорили родоначальники этой науки. Нас гложет сомнение: нужно ли вообще различать такие понятия, как «ребро» — «дуга», «контур» — «цикл», «путь» — «маршрут», «центр» — «центроид» и т. д. Ведь на практике (а графы в основном имеют прикладное значение) все эти ряды терминов забываются и заменяются каки-либо одним словом: «граф», «ребро», «цикл», «путь», «центр». Информатику трудно понять, почему граф с петлёй уже не является полноценным графом, а только «псевдографом». …Разве информатик или кто-либо другой из специалистов не в состоянии сам решить, каким словом ему пользоваться — «путь» или «маршрут», — и через какие буквы его маршрут-путь лучше обозначить? Граф — это наглядный образ, достоинство которого как раз и состоит в том, что он требует минимума слов и символов. Шаблон:Конец цитаты

Программисты тоже вносят свою лепту в разброс терминологииШаблон:Sfn.

Шаблон:Начало цитаты В программистском мире нет единого мнения о том, какой из двух терминов «граф» или «сеть» более употребителен. Мы выбрали термин «сеть», так как он, по-видимому, чаще встречается в прикладных областях. Шаблон:Конец цитаты

Но в изданиях последних лет речь идёт уже о «в основном стандартной» терминологииШаблон:SfnШаблон:Sfn.

Шаблон:Начало цитаты Используемая в этой книге терминология в основном стандартна. Альтернативы, конечно, существуют и некоторые из них даются при первом определении понятия. Шаблон:Конец цитаты

Например, в фундаментальном труде в области кибернетики «Алгоритмы: построение и анализ» используется стандартная терминологияШаблон:Sfn.

Шаблон:Начало цитаты При описании времени работы алгоритма над данным графом <math>G = (V, E)</math> мы обычно определяем размер входного графа в терминах количества его вершин <math>|V|</math> и количества рёбер <math>|E|</math> графа, т. е. размер входных данных описываем двумя, а не одним параметром. Шаблон:Конец цитаты

Проблемы рисования графов

Абстрактные графы можно изображать на плоскости по-разному. Вопрос о том, изоморфны ли данные изображения графов, то есть изоморфны ли данные изображения графов одному абстрактному графу, может быть нетривиальным. Иногда этот вопрос решается просто. Например, следующие два графа неизоморфны, поскольку они имеют разное число вершинШаблон:Sfn.

Следующие два графа также неизоморфны, поскольку они имеют разное число рёберШаблон:Sfn.

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

1-2-3-4-8-7-6-5-1,

а второй граф не имеет. То есть при любой нумерации вершин второго графа нельзя получить на нём гамильтонов цикл, соответствующий гамильтонову циклу первого графаШаблон:Sfn.

Если сразу не ясно, как доказать неизоморфность графов, то вопрос о наличии изоморфизма может оказаться труден. Два следующих изоморфных графа на первый взгляд неизоморфныШаблон:Sfn.

Проблемы литературы

На какие источники лучше ориентироваться, представляя теорию графов? Вот отзывы о некоторых книгах.

  • Харари Фрэнк. Теория графов, 2003.
Книга Фрэнка Харари стала классической де-фактоШаблон:SfnШаблон:Sfn.

Шаблон:Начало цитаты Прошло 30 лет после выпуска монографии Ф. Харари «Теория графов», но её привлекательные качества нисколько не потускнели. Унификация терминологии, проведённой автором и широко распространенной благодаря этой книге, стала общепринятой. Преподавание теории графов с использованием книги Ф. Харари ведется во многих вузах нашей страны. Шаблон:Конец цитаты

В книге Герберта Фляйшнера «Эйлеровы графы и смежные вопросы» приведён список книг, рекомендуемых в качестве введения в теорию графов. Это книги на английском языке, из которых только первая переведена на русский: это книга Фрэнка Харари «Теория графов»Шаблон:Sfn.
  • Дистель Р. Теория графов, 2002.
Книга Рейнгарда Дистеля «Теория графов» (выдержала 5 редакций) не имеет конкурентов в русскоязычной библиографии. Этот канон вводного курса в теорию графов инициировал отождествление некоторых областей обучения и исследованияШаблон:SfnШаблон:Sfn.

Шаблон:Начало цитаты …сейчас хватает переводов на русский язык учебников по теории графов, в первую очередь замечательной книги Дистеля. И, увы, только книги Дистеля.

…Именно работа над переводом 5-го издания книги Дистеля стимулировала продолжение работы над моей книгой в 2017 году после долгого перерыва. Я заметил, насколько велика «симметрическая разность» его книги и моей. Шаблон:Конец цитаты

Классификация теории графов

Классификацию теории графов приходится собирать по разным источникам.

Основные термины теории графов

Теория графов, как и любая современная математическая модель, использует стенографические символы, экономящие мышление и делающие математическую модель гибкой и эффективнойШаблон:Sfn.

Здесь деликатно и сжато приведены первые термины основной части теории графов. Большинство стандартных терминов настолько наглядны, что легко усваиваются. Необходимо достаточно строго определить ряд понятий, чтобы в дальнейшем иметь возможность их широко использоватьШаблон:SfnШаблон:SfnШаблон:Sfn.

Графы (Шаблон:Lang-en)

Шаблон:Основная статья

Краткая, но представительная сводка основных определений теории графов, примыкающих к понятию собственно графа. Эти понятия вводятся одно за другим достаточно систематически, хотя и несколько утомительноШаблон:SfnШаблон:SfnШаблон:Sfn.

Вершина графа (узел, точка) — это элемент множества <math>V</math> графа. Обозначение: <math>v \in V(G)</math>.
Ребро графа (линия, дуга) — это элемент множества <math>E</math> графа. Обозначение: <math>e \in E(G)</math>.
Ребро в старых изданиях могли также назвать ветвью, звеномШаблон:Sfn или кривойШаблон:Sfn.
Обычно граф представляют диаграммой, которую часто и называют графом.
Порядок графа — это число вершин графа <math>G</math>. Обозначение: <math>|G|</math>. Число рёбер графа обозначается <math>\|G\|</math>.
Пустой граф — это граф без вершин. Обозначение: <math>G (\varnothing, \varnothing) \equiv \varnothing</math>.
Тривиальный граф — это граф порядка 0 или 1.
  • Концевые вершины, или концы, ребра — это две вершины, которые определяют ребро. Ребро соединяет свои концевые вершины. Ребро и его концевая вершина инцидентны, или одно находится при другом. Множество всех рёбер при вершине <math>v \in V(G)</math> обозначается <math>E(v)</math>.
Смежные, или соседние, вершины — это две вершины, инцидентные одному ребру.
Смежные рёбра — это рёбра, которые имеют общий конец.
Полный граф — это граф, все вершины которого попарно смежны, то есть любые две вершины соединены ребром. Обозначение полного графа с <math>n</math> вершинами: <math>K_n</math>Шаблон:Sfn (иногда <math>K^n</math>). Граф <math>K_3</math> называется треугольником.
Двудольный граф, или биграф, — это граф, который допускает разбиение множества вершин на два подмножества такое, что:
  • концы любого ребра принадлежат разным подмножествам разбиения;
  • вершины в каждом подмножестве разбиения попарно несмежны.
Полный двудольный граф— это двудольный граф, в котором каждые две вершины из разных подмножеств разбиения смежны.
Обозначение полного двудольного графа с числом вершин в подмножествах разбиения <math>n</math> и <math>m</math>: <math>K_{n, m}</math>Шаблон:Sfn.
Изолированная вершина графа — это вершина с нулевой степенью.
Концевая, или висячая, вершина графа — это вершина с первой степенью.
Минимальная степень вершин графа <math>G</math> обозначается через <math>\min \deg G \equiv \delta(G)</math>, максимальная степень — <math>\max \deg G \equiv \Delta(G)</math>.
Регулярный, или однородный граф — это граф, все вершины которого имеют одну и ту же степень. Другими словами, для такого графа <math>G</math> его степени <math>\delta(G) = \Delta(G)</math>.
r-регулярный, или r-однородный, граф — это граф <math>G</math> с <math>\delta(G) = \Delta(G) = r</math>. Такие графы называются также просто регулярными, или однородными. 3-регулярный граф называется кубическим.
Каждое ребро графа инцидентно двум вершинам, и в сумму степеней вершин графа каждое ребро вносит двойку. Получаем исторически первую теорему теории графов, доказанную Леонардом Эйлером в статье, датированной 1736 годом (первый результат теории графов в той же статье — решение задачи о кёнигсбергских мостах).
Теорема. Сумма степеней вершин графа равна удвоенному числу его рёбер.
Следствие 1. В любом графе число вершин с нечётными степенями чётно.
Следствие 2. Любой кубический граф имеет чётное число вершин.

Типы графов (Шаблон:Lang-en)

Шаблон:Основная статья

Продолжение краткой, но представительной сводки основных теоретико-графовых определений, примыкающих к понятию графа. Для полноты перечислим ряд разновидностей графовШаблон:SfnШаблон:SfnШаблон:Sfn.

Ясно, что изоморфизм — это отношение эквивалентности на графах.
Обычно изоморфные графы не различают и пишут <math>G = H</math> вместо <math>G \simeq H</math>, понятие изоморфизма широко используется при изображениях графов.
Инвариант графа — это число, которое принимает одно и то же значение на изоморфных графах.
Полный набор инвариантов определяет граф с точностью до изоморфизма. Например, число вершин и число рёбер графа — полный набор инвариантов для любого графа с числом вершин, не большим 3.
  • Подграф графа — это граф, все вершины и рёбра которого принадлежат исходному графу. Исходный граф — это надграф своего подграфа. Другими словами, граф <math>G</math> содержит граф <math>G'</math>: <math>G \subseteq G'</math>.
Óстовный подграф графа — это подграф, содержащий все вершины своего надграфа.
Порождённый, или индуцированный, подграф графа — это подграф, содержащий все рёбра надграфа для множества своих вершин, то есть две вершины порождённого подграфа смежны тогда и только тогда, когда они смежны в надграфе.
  • Мультиграф — это конечные непересекающиеся множество и мультимножество, причём мультимножество состоит из 2-элементных подмножеств множества. Обозначение: <math>G = (V, E)</math>Шаблон:Sfn, где любой элемент <math>e \in E</math> мультимножества <math>e \in V \times V</math> и <math>V \cap E = \varnothing</math>.
В мультиграфе пара вершин может быть соединена более чем одним ребром.
Кратные рёбра — это рёбра, соединяющие одну и ту же пару вершин.
Другими словами, мультиграф — это граф с кратными рёбрами, а граф — это мультиграф без кратных рёбер.
Простой, или обыкновенный, граф — это граф без кратных рёбер, если графом назвать мультиграф.
Псевдограф — это конечные непересекающиеся множество и мультимножество, причём мультимножество состоит как из 1-элементных, так и из 2-элементных подмножеств множества. Обозначение: <math>G = (V, E)</math>, где мультимножество <math>E \subseteq V \cup (V \times V)</math> и <math>V \cap E = \varnothing</math>.
В псевдографе ребро может соединять вершину саму с собой.
Петля— это ребро, у которого концевые вершины совпадают.
Иногда псевдограф называют мультиграфом.
Гиперграф — это конечные непересекающиеся множество и мультимножество, причём мультимножество состоит из любых подмножеств множества. Обозначение: <math>G = (V, E)</math>, где любой элемент <math>e \in E</math> мультимножества принадлежит булеану: <math>e \in P(V)</math>, и <math>V \cap E = \varnothing</math>.
Другими словами, в гиперграфе ребро может соединять не только одну или две вершины, но произвольное число вершин.
Ориентированный граф, или орграф — это псевдограф, рёбра которого ориентированы, то есть имеют начальную вершину и концевую вершину. Обозначение: <math>D = (V, E)</math>Шаблон:Sfn, где мультимножество <math>E</math> состоит из упорядоченных пар <math>v, u \in V</math> и <math>V \cap E = \varnothing</math>.
Ориентированное ребро, или дуга — это ребро орграфа.

Пути и связность (Шаблон:Lang-en)

Шаблон:Основная статья

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

  • Путь, или простой путь, в графе — это подграф, представляющий собой последовательность различных вершин, в которой каждая вершина соединена со следующей ребром. Обозначение пути (Шаблон:Lang-en): <math>P = (V, E)</math>, где
<math>V = \{x_0, x_1, x_2, \dots, x_k\}</math>, <math>E = \{x_0x_1, x_1x_2, x_2x_3, \dots, x_{k-1}x_k\}</math>,
все <math>x_i</math> различны.
В теоретических и практических работах путь может называться по-разному, например, простая цепь.
Концевые вершины, или концы, пути — это вершины <math>x_0</math> и <math>x_k</math>. Вершины <math>x_0</math> и <math>x_k</math> соединены путём Шаблон:S
Внутренние вершины пути — это вершины <math>x_1, x_2, \dots, x_{k-1}</math>.
Длина пути — это число рёбер пути. Обозначение пути длиной <math>k</math>: <math>P_k</math>.
Цикл, или простой цикл, в графе — это подграф, представляющий собой замкнутую последовательность различных вершин, в которой каждая вершина соединена со следующей ребром. Обозначение цикла (Шаблон:Lang-en): <math>C = (V, E)</math>, где
<math>V = \{x_0, x_1, x_2, \dots, x_k, x_0\}</math>, <math>E = \{x_0x_1, x_1x_2, x_2x_3, \dots, x_{k-1}x_k, x_kx_0\}</math>,
все <math>x_i</math> различны.
Длина цикла — это число рёбер цикла. Обозначение цикла длиной <math>k</math>: <math>C_k</math>.
Хорда цикла — это рёбро, которое не принадлежит циклу и соединяет две его вершины.
Теорема. Любой граф <math>G</math> с минимальной степенью вершин <math>\delta(G) \geqslant 2</math> содержит цикл длины не менее <math>\delta(G) + 1</math>.
  • Связный граф — это граф, у которого две любые вершины соединены путём.
Компонента связности, или компонента, графа — это максимальный связный подграф графа.
Несвязный граф состоит по крайней мере из двух компонент связности.
Компонента, будучи связной, непуста; поэтому пустой граф не имеет компонент.
Разделяющая вершина, или точка сочленения графа — это вершина графа, при удалении которой число компонент связности графа увеличивается.
Мост графа — это ребро графа, при удалении которого число компонент связности графа увеличивается.
Конечные вершины моста — это разделяющие вершины.
Ясно, что мосты в графе — это те и только те рёбра, которые не принадлежат никакому циклу.
Неразделимый граф — это непустой связный граф без разделяющих вершин.
  • Маршрут в графе — это подграф, представляющий собой последовательность вершин, в которой каждая вершина соединена со следующей ребром. Обозначение маршрута: <math>(V, E)</math>, где
<math>V = \{x_0, x_1, x_2, \dots, x_k\}</math>, <math>E = \{x_0x_1, x_1x_2, x_2x_3, \dots, x_{k-1}x_k\}</math>.
В маршруте могут быть совпадающие рёбра и врешины.
Ясно, что если все вершины в маршруте различны, то это путь.
Маршрут замкнут, если <math>x_0 = x_k</math>, иначе маршрут открыт.
Эйлеров цикл, или эйлеров обход, графа — это замкнутый маршрут в графе, который проходит по всем рёбрам графа ровно один раз.
Эйлеров граф — это граф, который имеет эйлеров цикл.
Ясно, что эйлеров граф связен.
Теорема (Эйлер, 1736). Связный граф Эйлеров тогда и только тогда, когда все вершины графа имеют чётную степень.
Следствие. Связный граф с двумя вершинами нечётной степени имеет открытый маршрут, проходящий по всем рёбрам ровно один раз. Причём этот маршрут начинается в одной из вершин с нечётной степенью и заканчивается в другой.

Деревья (Шаблон:Lang-en)

Шаблон:Основная статья

Четыре семейства графов были представлены выше, это полные, двудольные, регулярные и эйлеровы графы. Ещё одно семейство графов в разных областях науки называется одинаково — деревья. Деревья находят приложения в различных областях знания и имеют особый статус в самой теории графов по причине предельной простоты их строения, и при решении задачи о графах её сначала могут исследовать на деревьяхШаблон:SfnШаблон:SfnШаблон:Sfn.

Файл:Euclidean minimum spanning tree.svg
Дерево
  • Лес — это граф без циклов.
Дерево — это связный лес. Обозначение дерева (Шаблон:Lang-en): <math>T</math>.
Другими словами, лес — это граф, компоненты которого суть деревья.
Лист — это вершина степени 1 в дереве.
Любое нетривиальное дерево имеет по крайней мере два листа. При удалении листа остаётся снова дерево.
Теорема. Для графа следующие утверждения равносильны:
(i) граф — дерево;
(ii) каждые две вершины графа соединены единственным путём;
(iii) граф — минимальный связный, то есть граф связен и становится несвязным при удалении любого ребра;
(iv) граф — максимальный ациклический, то есть граф не имеет цикла и цикл возникает при соединении ребром любых двух несмежных вершин.
Следствие 1. Любой связный граф имеет остовное дерево.
Доказательство. Из равносильности условий (i) и (iii) теоремы следует, что любой минимальный остовный подграф — дерево.
Следствие 2. Связный <math>n</math>-вершинный граф — дерево тогда и только тогда, когда он имеет ровно <math>n - 1</math> ребро.
Файл:Grid-tree.svg
Корневое дерево (дерево с выделенной вершиной)
  • Корень дерева — это фиксированная вершина дерева. Обозначение корня (Шаблон:Lang-en): <math>r</math>.
Корневое дерево — это дерево с корнем.
Древесный порядок — это частичный порядок на вершинах дерева, определяемый деревом и его корнем: для любых двух вершин <math>x</math> и <math>y</math> дерева <math>x \leqslant y</math>, если <math>x</math> принадлежит пути с концами <math>r</math> и <math>y</math>.
В древесном порядке:
  • корень дерева <math>r</math> — наименьший элемент;
  • любой лист дерева, отличный от корня, — наибольший элемент;
  • концы любого ребра дерева сравнимы.
Цепь, или линейно упорядоченное множество, — это частично упорядоченное множество, в котором любая пара элементов сравнима.
Теорема. Вершины пути на дереве с концами <math>r</math> и <math>y</math> образуют цепь, где <math>y</math> — любая фиксированная вершина дерева, отличная от корня <math>r</math>.
Файл:Depth-First-Search.gif
Динамика поиска в глубину на графе
Нормальное остовное дерево также называется деревом поиска в глубину по способу их применения в компьютерном поиске.
Теорема. Любой связный граф имеет нормальное остовное дерево, причём корнем дерева может быть любая вершина графа.
На иллюстрации ниже показаны два возможных остовых дерева полного графа <math>K_4</math>. Остовые деревья представлены жирными рёбрами. Левое остовное дерево — нормальное, если его корень — вершина A или D; при корнях B или C нормальности не получается, поскольку тогда концы ребра, например, A-D несравнимы. Правое остовное дерево не может быть нормальным при любом выборе его корня, всегда найдётся ребро с несравнимыми концами.

Современное состояние теории графов

Современному состоянию теории графов отвечает стандартный учебник, сочетающий в себе классику и активнуюе математику и охватывающий основной материал предмета. Оглавление подобной книги даёт краткое представление о современном состоянии теории графов, из которого и состоит этот разделШаблон:Sfn.

Паросочетания, покрытия и упаковка (Шаблон:Lang-en)

Шаблон:Основная статья

Как найти максимально возможное число независимых рёбер в графе? Можно ли все вершины графа разбить на пары? Ответы начинаются со следующих понятийШаблон:SfnШаблон:SfnШаблон:Sfn.

  • Паросочетание покрывает множество вершин графа, если каждая из вершин множества входит в какое-нибудь ребро паросочетания.
Файл:Bipartite graph with matching.svg
Теорема о свадьбах
Теорема о свадьбах (Холл, 1935). Двудольный граф содержит паросочетание, покрывающее одну из долей, тогда и только тогда, когда любое число вершин этой доли связаны с не меньшим числом вершин другой доли.
Древесность — это минимальное число лесов, на которые можно разбить граф.
Например, граф <math>K_5</math> имеет 5 вершин, поэтому максимальный размер его остовного дерева 4. С другой стороны, граф <math>K_5</math> имет 10 рёбер, поэтому для их покрытия потребуется минимум 3 дерева. Следовательно, показанное ниже разбиение графа <math>K_5</math> на 3 леса минимально.

Связность (Шаблон:Lang-en)

Шаблон:Основная статья

Более глубоко связность графа раскрывается путём использования понятий <math>k</math>-связности, блока и независимости путейШаблон:SfnШаблон:Sfn.

  • имеет больше <math>k</math> вершин;
  • остаётся связным после удаления менее <math>k</math> любых вершин.
Например, любой непустой граф 0-связен, а любой связный граф с более чем одной вершиной 1-связен. Двусвязный граф остаётся связным при удалении любой вершины.
Связность, или вершинная связность, графа <math>\kappa</math> — это наибольшее целое число <math>k</math>, при котором граф <math>k</math>-связен.
Например, <math>\kappa = 0</math> тогда и только тогда, когда граф:
  • либо несвязен;
  • либо состоит из одной вершины.
Связность связного графа с точкой сочленения равна 1. Полный граф <math>K_n</math> остаётся связным при удалении любого числа вершин и имеет одну вершину после удаления <math>n - 1</math> вершины, поэтому <math>\kappa(K_n) = n - 1</math> при всех <math>n \geqslant 1</math>.
Аналогично определяется рёберно <math>k</math>-связный граф и рёберная связность графа <math>\lambda</math>.
Например, <math>\lambda = 0</math> тогда и только тогда, когда граф:
  • либо несвязен;
  • либо состоит из одной вершины.
Рёберная связность связного графа с мостом равна 1.
Связность , рёберная связность <math>\lambda</math> и минимальная степень вершин <math>\delta</math> связаны следующим неравенством.
Теорема (Уитни, 1932). Для любого графа <math>G</math> с числом вершин больше одной
<math>\kappa(G) \leqslant \lambda(G) \leqslant \delta(G)</math>.
  • Блок графа — это максимальный связный подграф без точек сочленения.
У блока не своих точек сочленения, но вполне могут быть точки сочленения исходного графа.
Граф из одного блока может называться просто блоком.
Подграф является блоком тогда и только тогда, когда он:
  • максимальный двусвязный подграф;
  • мост со своими вершинами;
  • изолированная вершина.
Разные блоки в графе по причине своей максимальности могут пересекаться только по одной точке сочленения. Следовательно:
  • каждое ребро графа состоит в единственном блоке;
  • сам граф — это объединение блоков.
В этом смысле блоки — это двусвязные аналоги компонент связности. Только компоненты связности не пересекаются, а блоки могут пересекаться. Блоки вместе со способами их пересечения определяют грубую структуру графа — граф блоков и точек сочленения.
Граф блоков и точек сочленения графа — это двудольный граф с сериями вершин <math>a</math> и <math>B</math>, построенный следующим образом:
  • вершины <math>a</math> соответствуют всем точкам сочленения исходного графа, вершины <math>B</math> — блокам;
  • ребро соединяет вершину <math>a</math> с вершиной <math>B</math>, если точка сочленения <math>a</math> принадлежит блоку <math>B</math>.
Теорема. Граф блоков связного графа — дерево.
Определение <math>k</math>-связности связано с удалением <math>k</math> вершин. Возможно, более наглядно такое определение: граф <math>k</math>-связен, когда две его любые вершины можно соединить <math>k</math> независимыми путями. Эти два определения эквивалентны, это двойственные формулировки одного и того же свойства.
Классическая теорема Менгера — один из камней в основании теории графов.
Теорема (Менгер, 1927). Для любых подмножеств вершин графа <math>A</math> и <math>B</math> минимальное число вершин, отделяющих <math>A</math> от <math>B</math>, равно максимальному числу независимых путей из <math>A</math> в <math>B</math>.
Глобальный вариант теоремы Менгера.
(i) Граф <math>k</math>-связен тогда и только тогда, когда между любыми двумя его вершинами имеется <math>k</math> независимых путей.
(ii) Граф рёберно <math>k</math>-связен тогда и только тогда, когда между любыми двумя его вершинами имеется <math>k</math> непересекающихся по рёбрам путей.
На следующем рисунке показан граф, у которого две несмежные белые вершины можно разделить удалением не меньше чем двух вершин. Из теоремы Менгера следует, что наибольшее число независимых путей между этими вершинами равно 2.

Планарные графы (Шаблон:Lang-en)

Шаблон:Основная статья

Желательно, чтобы граф, нарисованный на листе бумаги, воспринимался как можно легче. Один из способов уменьшить хаос множества линий — избегать их пересечения. Можно ли нарисовать граф таким образом, чтобы рёбра не пересекались, то есть пересекались бы только в общих концевых вершинахШаблон:SfnШаблон:SfnШаблон:Sfn?

  • Плоский граф — это граф, нарисованный на плоскости без пересечения рёбер, то есть рёбра пересекаются только в общих концевых вершинах.
Грань плоского графа — это одна из открытых областей, получающихся после удаления графа из плоскости. Внешняя грань — это единственная неограниченная грань графа; остальные грани называются внутренними.
Теорема. У плоского леса только одна грань — внешняя.
Теорема (формула Эйлера, 1736). Для любого связного плоского графа с <math>n</math> вершинами, <math>m</math> рёбрами и <math>l</math> гранями верна формула
<math>n - m + l = 2</math>.
Следствие формулы Эйлера. Плоский граф с тремя или более вершинами имеет не более <math>3n - 6</math> рёбер.
  • Планарный граф — это граф, который можно нарисовать на плоскости как плоский.
Например, полный граф с четырьмя вершинами <math>K_4</math> планарен.
Два легендарных графа непланарны:
Докажем, что граф <math>K_5</math> непланарен. От противного. Предположим, что <math>K_5</math> планарен. Тогда по следствию формулы Эйлера <math>K_5</math> имеет не более <math>3\cdot5 - 6 = 9</math> рёбер. Но <math>K_5</math> имеет 10 рёбер. Полученное противоречие доказывает, что граф <math>K_5</math> непланарен.
  • Стягивание ребра графа — это удаление ребра из графа и слияние концевых вершин этого ребра в одну вершину вместе со своими рёбрами.
Теорема Понтрягина — Куратовского (1927, 1930), или теорема Куратовского (1930). Граф планарен тогда и только тогда, когда из него нельзя получить удалением рёбер и вершин с их рёбрами и последующим стягиванием рёбер ни граф <math>K_5</math>, ни граф <math>K_{3,3}</math>.
Например, из непланарного графа Петерсена можно получить подобным образом:
  • граф <math>K_5</math> стягиванием внешних маленьких рёбер, направленных к центру графа: 0—5, 1—6, 2—7, 3—8, 4—9;
  • граф <math>K_{3,3}</math> таким образом, как показано на следующем анимационном рисунке.

Раскраска (Шаблон:Lang-en)

Шаблон:Основная статья

Сколькими цветами можно раскрасить страны на карте так, чтобы смежные страны имели разный цвет? Сколько дней заседает парламентский комитет, если каждый комитет заседает один день, а некоторые члены парламента служат в нескольких комитетах? Какова минимальная длина школьного расписания, если известно, как часто каждый преподаватель преподаёт в каждом классеШаблон:SfnШаблон:Sfn?

k-раскраска графа, или вершинная k-раскраска графа, или k-раскрашиваемость, — это вершинная раскраска графа в k цветов.
Хроматическое число графа, или вершинное хроматическое число графа, или k-хроматичность, — это минимальное k, при котором граф имеет k-раскраску. Обозначение: <math>\chi</math>.
Например, граф 1-хроматичен, когда он имеет хотя бы одну вершину и не имеет рёбер. Полный граф <math>K_n</math> n-хроматичен. Граф-звезда с 5 вершинами 2-хроматичен. И все графы-звёзды 2-хроматичны. Более того, граф двудолен тогда и только тогда, когда он 2-хроматичен.
Теорема. У графа с m рёбрами
<math>\chi \leqslant \frac12 + \sqrt{2m + \frac14}</math>.
Доказательство. Пусть граф <math>\chi</math>-раскрашен. Тогда для любых двух цветов имеется хотя бы одно ребро с концами, окрашенными в эти цвета. Значит, таких рёбер не меньше, чем <math>\frac12 \chi(\chi - 1)</math>, то есть <math>m \geqslant \frac12 \chi(\chi - 1)</math>. Решая неравенство относительно <math>\chi</math>, получаем утверждение теоремы.
  • Теорема о четырёх красках. Любой плоский граф 4-раскрашиваем.
Возможно, это единственный результат теории графов, который претендует на известность во всём мире. Отсюда следует, что каждая географическая карта может быть окрашена не более чем в четыре цвета так, чтобы соседние страны имели разный цвет. В настоящее время доказательство этой теоремы носит сложный компьютерный характер.
Гораздо проще доказывается следующая ослабленное утверждение.
Теорема о пяти красках. Любой плоский граф 5-раскрашиваем.
Следующее утверждение тоже широко известно.
Теорема (Грёч, 1959). Любой плоский граф без треугольников 3-раскрашиваем.
Рёберная k-раскраска графа, или рёберная k-раскрашиваемость, — это рёберная раскраска графа в k цветов.
Хроматический индекс графа, или рёберное хроматическое число графа, или рёберная k-хроматичность, — это минимальное k, при котором граф имеет рёберную k-раскраску. Обозначение: <math>\chi'</math>.
Для хроматического числа графа <math>\chi</math> доказаны лишь очень грубые оценки, тогда как для хроматический индекс графа <math>\chi'</math> равен либо максимальной степени вершин графа <math>\Delta</math>, либо <math>\Delta + 1</math>.
Ясно, что для любого графа <math>\chi' \geqslant \Delta</math>.
Теорема (Кёниг, 1916). Для любого двудольного графа <math>\chi' = \Delta</math>.
Теорема (Визинг, 1964). Для любого графа <math>\Delta \leqslant \chi' \leqslant \Delta + 1</math>.
Теорема Визинга делит конечные графы на два класса: имеющие <math>\chi' = \Delta</math> и имеющий <math>\chi' = \Delta + 1</math>.

Потоки (Шаблон:Lang-en)

Шаблон:Основная статья

Граф можно рассматривать как сеть, когда рёбра несут некоторый поток, например поток воды, или электрического тока, или данных и так далее. Как моделируется подобная ситуация математическиШаблон:SfnШаблон:Sfn?

  • Разбиение множества — это набор попарно непересекающихся подмножеств, объединение которых даёт всё множество.
Разрез в графе — это набор всех рёбер графа, пересекающих некоторое разбиение всех вершин графа на два множества — на стороны разбиения, то есть концевые вершины каждого ребра разреза находятся в разных сторонах разбиения.
Ясно, что стороны разбиения однозначно определяют разрез.
Бонд, или коцикл, — это минимальный по количеству рёбер непустой разрез в графе, то есть при удалении любого числа рёбра из разреза разрез перестаёт быть каким-либо разрезом.
В следующем примере 5-рёберный разрез не минимальный, поскольку при удалении 3 рёбер получается минимальный разрез, показанный справа.
  • Поток на графе — это набор целых чисел <math>f(x, y)</math>, приписанных каждой упорядоченной паре <math>(x, y)</math> смежных узлов (вершин) сети (графа) такой, что:
  • выполняется антисимметричность потока <math>f(x, y) = -f(y, x)</math>;
  • в узлах <math>x</math>, в которых поток в сеть не входит и не выходит, выполняется первое правило Кирхгофа <math>\sum f(x, y) = 0</math>, где суммирование проводится по всем <math>y</math>, смежным с <math>x</math>.
Источник — это узел, где поток входит в сеть. Обозначение: <math>s</math>.
Сток — это узел, где поток выходит из сети. Обозначение: <math>t</math>.
Теория потоков:
  • моделирует реальные потоки;
  • взаимодействует с другими разделами теории графов (особенно со связностью и раскрасками).
Ребро мультиграфа не определяется однозначно парой <math>(x, y)</math> или <math>(y, x)</math>.
Ориентированное ребро мультиграфа — это тройка <math>(e, x, y)</math>, где <math>e</math> — ребро мультиграфа, начинающееся в вершине <math>x</math> и заканчивающееся в вершине <math>y</math>.
Ребро <math>e</math> с <math>x \ne y</math> имеет два направления <math>(e, x, y)</math> и <math>(e, y, x)</math>. Петля имеет одно направление <math>(e, x, x)</math>.
Циркуляция на графе — это функция <math>f(e, x, y)</math> такая, что:
(F1) выполняется антисимметричность циркуляции <math>f(e, x, y) = -f(e, y, x)</math> для всех ориентированных рёбер графа <math>(e, x, y)</math> с <math>x \ne y</math>;
(F2) во всех узлах <math>v</math> выполняется первое правило Кирхгофа <math>\sum f(e, v, w) = 0</math>, где суммирование проводится по всем <math>w</math>, смежным с <math>v</math>.
Теорема. В циркуляции суммарный поток через любой разрез равен нулю:
<math>\sum f(e, v, w) = 0</math>, где суммирование идёт по всем рёбрам <math>(e, v, w)</math> произвольного разреза графа.
  • Функция пропускной способности на графе, или пропускная способность рёбер графа, — это набор натуральных чисел (с нулём), приписанных каждому ориентированному ребру мультиграфа.
Функция пропускной способности на графе определена независимо для обоих направлений ребра.
Сеть — это мультиграф с двумя выделенными узлами (вершинами) <math>s</math> и <math>t</math> и функцией пропускной способности <math>c(e, x, y)</math> на каждом ориентированном ребре <math>(e, x, y)</math>.
Разрез сети — это разрез мультиграфа сети такой, что выделенные узлы <math>s</math> и <math>t</math> лежат на разных сторонах разреза.
Пропускная способность разреза сети — это сумма <math>\sum c(e, v, w)</math>, где суммирование идёт по всем рёбрам <math>(e, v, w)</math> разреза сети.
Поток в сети — это вещественнозначная функция <math>f(e, x, y)</math> в сети такая, что:
(F1) выполняется антисимметричность потока <math>f(e, x, y) = -f(e, y, x)</math> для всех ориентированных рёбер сети (графа) <math>(e, x, y)</math> с <math>x \ne y</math>;
(F2') во всех узлах (вершинах) <math>v</math>, кроме <math>s</math> и <math>t</math>, выполняется первое правило Кирхгофа <math>\sum f(e, v, w) = 0</math>, где суммирование проводится по всем <math>w</math>, смежными с <math>v</math>;
(F3) <math>f(e, x, y) \leqslant c(e, x, y)</math> для всех ориентированных рёбер сети <math>(e, x, y)</math>.
Величина потока разреза сети — это сумма <math>\sum f(e, v, w)</math>, где суммирование идёт по всем рёбрам <math>(e, v, w)</math> разреза сети.
Величина потока разреза сети одинакова для всех разрезов сети и называется величиной потока сети.
Теорема (Форд, Фалкерсон, 1956). В любой сети максимальная величина потока равна минимальной пропускной способности разрезов.

Экстремальная теория графов (Шаблон:Lang-en)

Шаблон:Основная статья

Какая рёберная плотность необходима для существования заданного подграфа — типичная экстремальная задача на графах. Достаточно высокая средняя степень вершин или большое хроматическое число гарантируют, что нужная подструктура обязательно встретится в графе? Какое наибольшее возможное число рёбер может иметь <math>n</math>-вершинный граф, чтобы не иметь другой, меньший, граф в качестве подграфаШаблон:SfnШаблон:Sfn?

  • Экстремальный граф — для заданных натурального числа <math>n</math> и графа <math>H</math> это <math>n</math>-вершинный граф <math>G</math> с максимально возможным числом рёбер, не содержащий подграф <math>H</math>: <math>G \nsupseteq H</math>. Такое максимальное число рёбер обозначается <math>\operatorname{ex}(n, H)</math>.
Максимальный граф — для заданных натурального числа <math>n</math> и графа <math>H</math> это <math>n</math>-вершинный граф <math>G</math> такой, что <math>G \nsupseteq H</math>, но при добавлении любого нового ребра <math>G \supseteq H</math>.
Ясно, что экстремальный граф максимален. Но не наоборот, как показано на рисунке ниже.
  • конечные вершины каждого ребра лежат в разных долях;
  • вершины одной доли попарно несмежны.
Полный <math>r</math>-дольный граф — это <math>r</math>-дольный граф, в котором каждые две вершины из разных долей смежны. Обозначение: <math>K_{n_1, n_2, \dots, n_r}</math>.
  • Граф Турана — это <math>n</math>-вершинный граф со следующими свойствами:
  • это <math>r</math>-дольный граф с <math>r \leqslant n</math>;
  • количества вершин долей отличаются друг от друга не более чем на 1.
Обозначение: граф Турана <math>T_r(n)</math> имеет <math>t_r(n)</math> рёбер.
Граф Турана <math>T_r(n)</math> плотен (то есть близок к полному графу), так как имеет около <math>n^2</math> рёбер, точнее,
<math>t_r(n) \leqslant n^2 \frac{r-1}{2r}</math>,
и равенство достигается, когда <math>r</math> делит <math>n</math>.
Теорема (Туран, 1941). Граф Турана <math>T_{r - 1}(n)</math> — это единственный экстремальный граф для <math>n</math> и <math>K_r</math>, причём <math>\operatorname{ex}(n, K_r) = t_{r - 1}(n)</math>.

Бесконечные графы (Шаблон:Lang-en)

Шаблон:Основная статья

Изучение бесконечных графов привлекательно, однако этим разделом теории графов часто пренебрегают. Терминология совпадает с терминологией конечных графов, за исключением принципиально новых понятий бесконечных графов. Наиболее типичные подобные понятия появляются уже при «минимуме бесконечности», когда у графа всего лишь счётное число вершин и только конечное число рёбер в вершинахШаблон:Sfn.

  • Локально конечный граф — это граф, в каждой вершине которого сходится конечное число рёбер.
Луч — это граф с бесконечными множествами вершин и рёбер, соответственно пронумерованных следующим образом:
<math>\{x_0, x_1, x_2, \dots \}, \{x_0x_1, x_1x_2, x_2x_3, \dots \}.</math>
Двойной луч — это граф с бесконечными множествами вершин и рёбер, соответственно пронумерованных следующим образом:
<math>\{ \dots, x_{-1}, x_0, x_1, \dots \}, \{ \dots, x_{-1}x_0, x_0x_1, x_1x_2, \dots \}.</math>
Ясно, что с точностью до изоморфизма существует только один луч и один двойной луч.
Двойной луч, во всех вершинах которого сходятся ровно два ребра, — это бесконечный 2-регулярный связный граф.
Путь — это либо конечный путь, либо луч, либо двойной луч.
Хвост — это подлуч луча или двойного луча. Луч имеет бесконечно много хвостов, которые отличаются только начальным конечным сегментом.
Гребень — это объединение луча с бесконечным количеством непересекающихся конечных путей, которые имеют первую вершину на луче. Зубья гребня — это последние вершины конечных путей гребня.
  • граф — объединение бесконечного числа непересекающихся непустых конечных множеств <math>V_0, V_1, V_2, \dots</math>;
  • у каждой вершины <math>v</math> из <math>V_n</math> при <math>n \geqslant 1</math> есть сосед <math>f(v)</math> из <math>V_{n-1}</math>.
Тогда граф содержит луч <math>v_0v_1v_2\dots</math> с <math>v_n \in V_n</math> для всех <math>n</math>.
Доказательство. 1. Имеется бесконечное множество конечных путей вида <math>v f(v) f(f(v)) \dots</math>, которые заканчиваются в <math>V_0</math>. Поскольку <math>V_0</math> конечно, то имеется такая вершина <math>v_0</math> в <math>V_0</math>, в которой заканчиваются бесконечно много таких путей.
2. Бесконечно много путей, заканчивающихся в <math>v_0</math>, имеют предпоследнюю вершину в <math>V_1</math>. Путей бесконечно много, а <math>V_1</math> конечно, поэтому имеется такая вершина <math>v_1</math> в <math>V_1</math>, которая принадлежит бесконечному множеству таких путей.
3. Бесконечно много путей, проходящих через <math>v_1</math>, имеют вершину в <math>V_2</math>, поэтому имеется такая вершина <math>v_2</math> в <math>V_2</math>, которая принадлежит бесконечному множеству этих путей.
4. И так далее до бесконечности. Бесконечный луч <math>v_0v_1v_2\dots</math> построен.
Приложения этой леммы о бесконечном пути основаны на том, что счётный граф можно рассматривать как бесконечную последовательность конечных подграфов.
Определим концы лестницы, бесконечной в две стороны. Каждый луч в этом графе содержит вершины, расположенные как угодно далеко либо слева, либо справа, но не одновременно слева и справа. Эти два типа лучей образуют два класса эквивалентности, поэтому лестница имеет два конца. На рисунке ниже эти концы графа отмечены точками.
Особенно просты концы дерева:
  • два луча дерева эквивалентны тогда и только тогда, когда они имеют общий хвост;
  • для каждой фиксированной вершины дерева каждый конец содержит ровно один луч, начинающийся с этой вершины.
Даже локально конечное дерево может иметь континуум концов. Например, двоичное дерево, в котором вершины обозначены конечными 0—1 последовательностями, с пустым множеством <math>\emptyset</math> в качестве корня. Тогда концы такого дерева соответствуют его лучам, начинающимся с корня <math>\emptyset</math>, и, следовательно, континууму бесконечных последовательностей 0—1.

Теория Рамсея для графов (Шаблон:Lang-en)

Шаблон:Основная статья

Каждый ли достаточно большой граф содержит или полный граф <math>K_r</math>, или индуцированное дополнение <math>\overline{K_r}</math>? Несмотря на сходство с экстремальными задачами с их поиском локальных следствий глобальных предположений, последний вопрос приводит к математике несколько иного рода. Действительно, теоремы и доказательства теории Рамсея имеют больше общего с подобными результатами из алгебры или геометрии. Язык графов естествен в рамсеевских задачах, и материал показывает разнообразие идей и методов, достаточное для того, чтобы передать обаяние этой теории в целомШаблон:SfnШаблон:SfnШаблон:Sfn?

  • множество верши совпадает с множеством вершин исходного графа;
  • вершины соединены ребром тогда и только тогда, когда они не соединены ребром в исходном графе. Обозначение для графа <math>G</math>: <math>\overline{G}</math>.
Дополнение полного графа <math>K_r</math> — вполне несвязный граф <math>\overline{K_r}</math>, содержащий только вершины.

Самодополнительный граф — это граф, который изоморфен своему дополнению. Наименьшие нетривиальные самодополнительные графы содержат 4 и 5 вершин.

  • доказать, что среди шести человек всегда присутствуют либо трое попарно знакомых, либо трое попарно незнакомых.
Формулировка задачи Рамсея в теории графов:
  • шесть вершин графа — это люди, рёбра — это знакомства. Доказать, что найдутся либо три вершины, попарно соединённые рёбрами, либо три вершины, попарно не соединённые.
Точная формулировка с использованием дополнения графа.
Теорема. Любой граф с шестью вершинами либо содержит треугольник, либо его дополнение содержит треугольник.
Доказательство. 1. Пусть дан граф <math>G</math> с шестью вершинами. Возьмём любую его вершину <math>v</math>. Вершина <math>v</math> соединена ребром с любой из остальных пяти вершин или в <math>G</math>, или в <math>\overline{G}</math>. Поэтому, не теряя общности, предположим, что <math>v</math> соединена с вершинами <math>u_1, u_2, u_3</math> в <math>G</math>.
2. Если из вершин <math>u_1, u_2, u_3</math> какие-нибудь две соединены ребром, то с <math>v</math> получается треугольник в <math>G</math>. Если никакие две из вершин <math>u_1, u_2, u_3</math> не соединены ребром, то они образуют треугольник в <math>\overline{G}</math>.
Обобщение теоремы.
Теорема (Рамсей, 1930). Для любого натурального числа <math>r</math> существует натуральное число <math>n</math> такое, что любой граф с не менее чем <math>n</math> вершинами или его дополнение содержат <math>K_r</math>.
Удобно использовать раскраску в формулировке теоремы Рамсея:
  • для любого полного графа <math>K_r</math> существует такой полный граф <math>K_n</math>, что любая его двуцветная раскраска ребёр содержит одноцветный <math>K_r</math>.
Число Рамсея — это наименьшее <math>n</math> для данного <math>r</math> в теореме Рамсея. Обозначение: <math>R(r)</math>.

Из стандартного доказательства теоремы Рамсея следует верхняя оценка числа Рамсея: <math>R(r) \leqslant 2^{2r-3}</math>. С помощью вероятностного метода можно найти нижнюю оценку: <math>R(r) \geqslant 2^{r/2}</math>.
Например, <math>R(3) = 6</math>:
  • из решения задачи Рамсея следует, что <math>R(3) \leqslant 6</math>;
  • докажем, что <math>R(3) > 5</math>. Достаточно привести один пример графа с 5 вершинами, который не удовлетворяет теореме Рамсея для <math>K_3</math>. Это самодополнительный пятиугольник, показанный выше, имеет 5 вершин и не содержит треугольников, и также не содержит треугольников его дополнение, которое с ним совпадает;
  • <math>R(3) \leqslant 6</math> и <math>R(3) > 5</math>, то есть <math>R(3) = 6</math>.
  • Теорема Рамсея верна не только для полного графа <math>K_r</math>, но и для любого графа <math>H</math> просто потому, что <math>H</math> — подграф полного графа <math>K_h</math>, где <math>h</math> — число вершин <math>H</math>.
Число Рамсея любого графа <math>H</math> — это наименьшее натуральное число <math>n</math> такое, что любой <math>n</math>-вершинный граф или его дополнение содержат <math>H</math>. Обозначение: <math>R(H)</math>.
Если в графе мало рёбер, то он легче включается в другой граф, и можно ожидать <math>R(H) < R(h) = R(K_h)</math>, где <math>h</math> — число вершин <math>H</math>.
Ещё немного обобщим.
Число Рамсея пары графов <math>H_1</math> и <math>H_2</math> — это наименьшее натуральное число <math>n</math> такое, что для любого <math>n</math>-вершинного графа либо сам граф содержит <math>H_1</math>, либо его дополнение содержит <math>H_2</math>. Обозначение: <math>R(H_1, H_2)</math>, для полных графов <math>R(K_r, K_s) \equiv R(r, s)</math>.
Ясно, что <math>R(H, H) = R(H)</math>, <math>R(r, r) = R(r)</math>.
Для большинства графов известны только очень грубые оценки для чисел Рамсея, точные нетривиальные числа Рамсея известны лишь для очень немногих графов.
Например, <math>R(3) = 6</math>, <math>R(4) = 18</math>, <math>R(3, 4) = R(4, 3) = 9</math>, <math>R(4, 5) = R(5, 4) = 25</math>.

Гамильтоновы циклы (Шаблон:Lang-en)

Шаблон:Основная статья

Задача о том, содержит ли граф замкнутый маршрут, проходящий через каждое ребро в точности один раз, легко решается с помощью простой теоремы Эйлера (1736). Намного труднее решается такой же вопрос относительно вершин: когда граф содержит замкнутый маршрут, проходящий через каждую вершину в точности один разШаблон:SfnШаблон:SfnШаблон:Sfn?

  • Гамильтонов цикл — это замкнутый маршрут, проходящий через каждую вершину графа в точности один раз.
Гамильтонов граф — это граф, который имеет гамильтонов цикл.
Ясно, что в каждую вершину гамильтонова графа входят по меньшей мере два ребра.
Теорема. Любой гамильтонов граф двусвязен.
То есть двусвязность — необходимое условие гамильтоновости. Не каждый двусвязный граф гамильтонов.
  • Тета-граф — это граф, который содержит только следующие вершины:
  • две вершины, в которые входят по три ребра;
  • вершины, в которые входят по два ребра.
То есть тета-граф имеет две вершины степени 3 и три непересекающиеся простые цепи, которые соединяют эти две вершины, длиной не менее 2 каждая.
Тета-граф негамильтонов. Простейший негамильтонов двусвязный граф — полный двудольный граф <math>K_{2, 3}</math>.
Теорема. В каждом негамильтоновом двусвязном графе имеется тета-подграф.
То есть наличие тета-подграфа — необходимое условие негамильтоновости. Не каждый граф с тета-подграфом негамильтонов.
Простейший гамильтонов граф с тета-подграфом — полный двудольный граф <math>K_{2, 3}</math> с добавленным ребром.
  • Выше были приведены некоторые необходимые условия гамильтоновости и негамильтоновости. Какие условия могут быть достаточными для гамильтоновости? Только несколько условий сразу.
Теорема (Шаблон:Iw, 1952). Граф с <math>n \geqslant 3</math> вершинами гамильтонов, если:
1) минимальная степень <math>\delta</math> его вершин зависит от n;
2) <math>\delta \geqslant n/2</math>.
То есть <math>\delta \geqslant n/2</math> — достаточное условие гамильтоновости. Не для каждого гамильтонова графа выполняется это условие. Например, для простейшего гамильтонова графа с тета-подграфом условие не выполнено.
Кубический граф — это 3-регулярный граф, то есть граф, в каждой вершине которого сходится ровно 3 ребра.
Для планарных графов гамильтоновость связана с проблемой четырёх красок. Для доказательства теоремы о четырех красках достаточно доказать гипотезу Тэйта: любой 3-связный планарный кубический граф имеет гамильтонов цикл.
Гипотеза не подтвердилась. Первый контрпример был найден Таттом в 1946 году.
Теорема (Татт, 1956). Любой 4-связный планарный граф гамильтонов.

Случайные графы (Шаблон:Lang-en)

Шаблон:Основная статья

Вероятностный метод позволяет доказать существование объекта с заданным свойством следующим образом: 1) определяется вероятностное пространство на некотором большем классе объектов, заведомо непустом; 2) показывается, что искомое свойство выполняются для случайно выбранного элемента пространства с положительной вероятностью. Суть вероятностного метода в том, чтобы неконструктивно показать, что заданная раскраска существует или нетШаблон:SfnШаблон:SfnШаблон:Sfn.

  • Вероятностный метод хорошо иллюстрируется следующим примером: получим нижнюю оценку для числа Рамсея <math>R(k)</math>.
1. Построим вероятностное пространство. Случайно раскрасим полный граф <math>K_n</math>, то есть с равной вероятностью раскрасим каждое ребро <math>K_n</math> независимо в красный или синий цвет. Таким образом, вероятность для ребра <math>K_n</math> получить красный цвет равна <math>\frac{1}{2} = 2^{-1}</math>, синий цвет — тоже <math>2^{-1}</math>.
2. Определим на случайно раскрашенном <math>K_n</math> следующее событие: случайно выбранный полный подграф <math>K_k</math> монохромен, то есть либо красный, либо синий. Подграф <math>K_k</math> имеет <math>{k\choose 2}</math> рёбер, поэтому вероятность уже выбранного подграфа <math>K_k</math> оказаться красным равна <math>2^{-{k\choose 2}}</math>, синим — тоже <math>2^{-{k\choose 2}}</math>, монохромным — <math>2^{-{k\choose 2}} + 2^{-{k\choose 2}} = 2^{1-{k\choose 2}}</math>.
Вероятность уже выбранного подграфа <math>K_k</math> быть одноцветным не зависит от <math>n</math>. Например, вероятность <math>K_3</math> быть одноцветным всегда равна
<math>2^{1-{3\choose 2}} = 2^{1-\frac{3!}{2!1!}} = 2^{1-\frac{6}{2}} = 2^{-2} = \frac{1}{4}</math>,
вероятность <math>K_4</math> быть одноцветным всегда равна
<math>2^{1-{4\choose 2}} = 2^{1-\frac{4!}{2!2!}} = 2^{1-\frac{24}{4}} = 2^{-5} = \frac{1}{32}</math>.
3. Подсчитаем теперь вероятность случайно выбранного подграфа <math>K_k</math> оказаться монохромным. Выбрать подграф <math>K_k</math> в полном графе <math>K_n</math> можно <math>{n\choose k}</math> разными способами. Поскольку события оказаться монохромными для этих подграфов могут оказаться зависимыми друг от друга, то вероятность случайно выбранного в <math>K_n</math> подграфа <math>K_k</math> оказаться монохромным всего лишь не больше суммы их вероятностей <math>{n\choose k}2^{1-{k\choose 2}}</math>.
Например, вероятность <math>K_3</math> оказаться монохромным в <math>K_3</math> не больше
<math>{3\choose 3}2^{1-{3\choose 2}} = \frac{3!}{3!0!}2^{1-\frac{3!}{2!1!}} = 2^{1-\frac{6}{2}} = 2^{-2} = \frac{1}{4}</math>,
вероятность <math>K_3</math> оказаться монохромным в <math>K_4</math> не больше
<math>{4\choose 3}2^{1-{3\choose 2}} = \frac{4!}{3!1!}2^{1-\frac{3!}{2!1!}} = 4\cdot2^{1-\frac{6}{2}} = 2^22^{-2} = 1</math>.
  • Оценим число Рамсея снизу. Если <math>n</math> достаточно мало для данного <math>k</math>, то число Рамсея <math>R(k) > n</math>.
Лемма. Если <math>{n\choose k}2^{1-{k\choose 2}} < 1</math>, то <math>R(k) > n</math>.
Доказательство. 1. Пусть <math>{n\choose k}2^{1-{k\choose 2}} < 1</math>, то есть вероятность случайно выбранного в <math>K_n</math> подграфа <math>K_k</math> оказаться монохромным меньше 1.
2. Тогда вероятность всех подграфов <math>K_k</math> не оказаться монохромными больше нуля: <math>1- {n\choose k}2^{1-{k\choose 2}} > 0</math>.
3. Другими словами, существует 2-раскраска <math>K_n</math> без монохроматических <math>K_k</math>, то есть <math>R(k) > n</math>.

Теорема (Эрдёш, 1947). Для любого натурального <math>k \geqslant 3</math> число Рамсея <math>R(k) > 2^{k/2}</math>.
Эта нижняя <math>R(k) > 2^{k/2}</math> и верхняя <math>R(k) \leqslant 2^{2k-3}</math> оценки весьма близки.
Доказательство. 1. При <math>k = 3</math> имеем:
<math>{n\choose k} = {n\choose 3} = \frac{n!}{3!(n-3)!} = \frac{n(n-1)(n-2)}{6} < \frac{n^3}{6}</math>,
<math>2^{1-{k\choose 2}} = 2^{1-{3\choose 2}} = 2^{1-\frac{3!}{2!1!}} = 2^{-2} = \frac{1}{2^2}</math>.
При всех <math>n \leqslant 2^{3/2}</math> имеем:
<math>{n\choose k} < \frac{n^3}{6} \leqslant \frac{2^{9/2}}{6} = \frac{2^{7/2}}{3}</math>,
<math>{n\choose k}2^{1-{k\choose 2}} < \frac{2^{7/2}}{3}\frac{1}{2^2} = \frac{2^{3/2}}{3} < \frac{2,83}{3} < 1</math>.
Теперь по лемме <math>R(3) > n</math> для всех <math>n \leqslant 2^{3/2}</math>, то есть <math>R(3) > 2^{3/2}</math>.
2. Пусть теперь <math>k \geqslant 4</math>. Имеем:
<math>k! = 1\cdot2\cdot3\cdot4\cdot\,\dots\,\cdot k = 2\cdot2\cdot3\cdot2\cdot\,\dots\,\cdot k > 2^k</math>.
При всех <math>n \leqslant 2^{k/2}</math> выкладки как при <math>k = 3</math>:
<math>{n\choose k}2^{1-{k\choose 2}} = \frac{1}{k!}\frac{n!}{(n - k)!}2^{1-\frac{k!}{2!(k-2)!}} < \frac{n^k}{2^k}2^{1-\frac{k(k-1)}{2}} \leqslant \frac{2^{k^2/2}}{2^k}2^{1-k^2/2 + k/2} =</math>
<math>= \frac{2^{1 + k/2}}{2^k} = 2^{1-k/2} \leqslant 2^{1-4/2} = \frac{1}{2} < 1</math>.
Теперь по лемме <math>R(k) > n</math> для всех <math>n \leqslant 2^{k/2}</math>, то есть <math>R(k) > 2^{k/2}</math>.
  • Случайный граф — это подграф полного графа <math>K_n</math>, полученный случайным образом. Например, если все рёбра <math>K_n</math> случайным образом окрашены в красный или синий цвет, то случайным граф — это подграф, образованный всеми красными рёбрами. Ясно, что случайные графы — это независимые события. Обозначение: вероятность случайного графа <math>G</math> обозначается <math>P(G)</math>.
Случайная величина — это неотрицательное вещественное число, заданное на каждом случайном графе <math>G</math>. Например, это может быть число вершин случайного графа, связность, хроматическое число и так далее. Обозначение: <math>X(G)</math>.
Математическое ожидание, или среднее, случайной величины — это взвешенная сумма вероятностей всех случайных графов:
<math>E(X) = \sum P(G)X(G)</math>.
Математическое ожидание линейно, то есть равенства
<math>E(X + Y) = E(X) + E(Y)</math> и <math>E(\lambda X) = \lambda E(X)</math>
выполняются для любых двух случайных величин <math>X</math> и <math>Y</math> и любого вещественного числа <math>\lambda</math>.
Если математическое ожидание, то есть среднее значение случайной величины, мало, то случайная величина должна быть мала для многих случайных графов. Тогда естественно предположить, что среди последних существует граф с требуемым свойством. Эта идея лежит в основе неконструктивных доказательств существования. Количественное выражение этой идеи следующее.
Неравенство Маркова. Для любой случайной величины <math>X \geqslant 0</math> и любого вещественного числа <math>a > 0</math> выполняется неравенство
<math>P(X \geqslant a) \leqslant \frac{E(X)}{a}</math>.
Доказательство. Очевидно, что (суммирование ведётся по всем случайным графам <math>G</math>)
<math>E(X) = \sum\limits_G P(G)X(G) \geqslant \sum\limits_{G\atop X(G) \geqslant a} P(G)X(G) \geqslant</math>
<math>\geqslant \sum\limits_{G\atop X(G) \geqslant a} P(G)a = a P(X \geqslant a)</math>.

Миноры, деревья и полный предпорядок (Шаблон:Lang-en)

Шаблон:Основная статья

Одна из самых глубоких математических теорем, которая затмевает любую другую теорему теории графов — это теорема о минорах графа: любое бесконечное множество графов содержит два графа таких, что один есть минор другого. Ниже объясняются некоторые основные понятия на подступах к этой теореме, доказательство которой занимает 500 страницШаблон:SfnШаблон:Sfn.

Шаблон:Iw, или правильный квазипорядок — это предпорядок, при котором любая бесконечная последовательность элементов множества содержит два предупорядоченных элемента, причём больший элемент следует в последовательности за меньшим. Другими словами, любая последовательность <math>x_0, x_1, x_2, \dots</math> в множестве <math>X</math> содержит <math>x_i \leqslant x_j</math>, <math>i < j</math>.
Вполне предупорядоченные элементы — это элементы вполне предупорядоченного множества.
Теорема. Предпорядок на множестве тогда и только тогда полный, когда множество не содержит следующих бесконечных последовательностей элементов:
  • с попарно несравнимыми элементами;
  • строго убывающей, то есть последовательности <math>x_0 > x_1 > x_2 > \dots</math>, где <math>x_i > x_j</math> означает <math>x_i \geqslant x_j</math> и <math>x_i \ne x_j</math>.
Примеры. 1. Отношение делимости <math>\,\vdots\,</math> на множестве натуральных чисел предупорядочено и даже частично упорядочено, но не вполне предупорядочено, поскольку бесконечная последовательность простых чисел не содержит предупорядоченной пары.
2. Отношение делимости на множестве целых чисел предупорядочено и не частично упорядочено (поскольку, например, <math>2\,\vdots-2</math> и <math>-2\,\vdots\,2</math>, но <math>2\ne-2</math>) и также не вполне предупорядочено.
Топологический минор графа — это граф, подразбиение которого есть подграф исходного графа.
Топологический минор сохраняет топологическую форму подграфа исходного графа.
Минор графа — это граф, полученный из исходного графа удалением вершин и удалением и стягиванием рёбер. Обозначение отношения <math>X</math> — минор <math>Y</math>: <math>X \preccurlyeq Y</math>
Любой подграф графа — его минор. Любой граф — свой собственный минор.
Теорема. (i) Любой топологический минор графа есть также его (обычный) минор. Обратное в общем случае неверно.
(ii) Для графа, в каждую вершину которого входит не более 3 рёбер, любой минор есть топологический минор.
Теорема. На множестве всех конечных графов отношения быть минором <math>\preccurlyeq</math> и быть топологическим минором суть частичные порядки.
По предыдущей теореме, множество запрещённых миноров замкнуто относительно взятия миноров: если граф <math>G</math> — запрещённый минор и <math>H \preccurlyeq G</math>, то граф <math>H</math> — тоже запрещённый минор.
Теорема. Свойство графов можно задать запрещёнными минорами тогда и только тогда, когда оно замкнуто относительно взятия миноров.
Свойства графов, замкнутые относительно взятия миноров, часто встречаются в теории графов. Наиболее известный пример дан теоремой Понтрягина — Куратовского: планарность задаётся запрещением миноров <math>K_5</math> и <math>K_{3, 3}</math>.
Характеризация запрещёнными графами — это хорошая характеризация.
Хорошая характеризация — это характеризация свойства графов, упрощающая доказательство отсутствия этого свойства. Просто убедиться, что граф обладает некоторым свойством, достаточно изобразить граф определённым образом. Сложности возникают при доказательстве отсутствия свойства. Но, например, при наличии запрещённых миноров для свойства его отсутствие легко доказывается предъявлением какого-нибудь запрещённого минора.
Теорема. При наличии запрещённых миноров всегда существует единственное наименьшее их множество, элементы которого — миноры всех запрещённых миноров.
Ясно, что запрещённые миноры из наименьшего множества несравнимы по отношению <math>\preccurlyeq</math> быть минором. Следующая теорема утверждает, что любое множество несравнимых по <math>\preccurlyeq</math> графов конечно.
Теорема Робертсона — Сеймура (1986—2004). Конечные графы вполне предупорядочены по отношению <math>\preccurlyeq</math> быть минором.
Следствие. Любое свойство графов, замкнутое по взятию миноров, можно задать конечным множеством запрещённых миноров.
Сильный вариант этой теоремы для деревьев следующий.
Шаблон:Iw. Конечные деревья вполне предупорядочены по отношению быть топологическим минором.

Немного линейной алгебры (Шаблон:Lang-en)

Шаблон:Основная статья

В основе простых циклов и рёберных разрезов графов лежит алгебраическая структура, достижение понимания которой делает возможным применение мощных и красивых методов линейной алгебры, которые приводят, в свою очередь, к более глубокому пониманию теории графов и соответствующих алгоритмов на графахШаблон:SfnШаблон:SfnШаблон:SfnШаблон:Sfn.

Вектор этого пространства — это подмножество вершин графа:
Таблица сложения по модулю 2 векторов пространства 4 вершин
<math>\oplus</math> Файл:Vertices are missing.png Файл:Vertex 1.png Файл:Vertex 2.png Файл:Vertex 3.png Файл:Vertex 4.png Файл:Vertices 1-2.png Файл:Vertices 1-3.png Файл:Vertices 1-4.png Файл:Vertices 2-3.png Файл:Vertices 2-4.png Файл:Vertices 3-4.png Файл:Vertices 1-2-3.png Файл:Vertices 1-2-4.png Файл:Vertices 1-3-4.png Файл:Vertices 2-3-4.png Файл:Vertices 1-2-3-4.png
Файл:Vertices are missing.png Файл:Vertices are missing.png Файл:Vertex 1.png Файл:Vertex 2.png Файл:Vertex 3.png Файл:Vertex 4.png Файл:Vertices 1-2.png Файл:Vertices 1-3.png Файл:Vertices 1-4.png Файл:Vertices 2-3.png Файл:Vertices 2-4.png Файл:Vertices 3-4.png Файл:Vertices 1-2-3.png Файл:Vertices 1-2-4.png Файл:Vertices 1-3-4.png Файл:Vertices 2-3-4.png Файл:Vertices 1-2-3-4.png
Файл:Vertex 1.png Файл:Vertex 1.png Файл:Vertices are missing.png Файл:Vertices 1-2.png Файл:Vertices 1-3.png Файл:Vertices 1-4.png Файл:Vertex 2.png Файл:Vertex 3.png Файл:Vertex 4.png Файл:Vertices 1-2-3.png Файл:Vertices 1-2-4.png Файл:Vertices 1-3-4.png Файл:Vertices 2-3.png Файл:Vertices 2-4.png Файл:Vertices 3-4.png Файл:Vertices 1-2-3-4.png Файл:Vertices 2-3-4.png
Файл:Vertex 2.png Файл:Vertex 2.png Файл:Vertices 1-2.png Файл:Vertices are missing.png Файл:Vertices 2-3.png Файл:Vertices 2-4.png Файл:Vertex 1.png Файл:Vertices 1-2-3.png Файл:Vertices 1-2-4.png Файл:Vertex 3.png Файл:Vertex 4.png Файл:Vertices 2-3-4.png Файл:Vertices 1-3.png Файл:Vertices 1-4.png Файл:Vertices 1-2-3-4.png Файл:Vertices 3-4.png Файл:Vertices 1-3-4.png
Файл:Vertex 3.png Файл:Vertex 3.png Файл:Vertices 1-3.png Файл:Vertices 2-3.png Файл:Vertices are missing.png Файл:Vertices 3-4.png Файл:Vertices 1-2-3.png Файл:Vertex 1.png Файл:Vertices 1-3-4.png Файл:Vertex 2.png Файл:Vertices 2-3-4.png Файл:Vertex 4.png Файл:Vertices 1-2.png Файл:Vertices 1-2-3-4.png Файл:Vertices 1-4.png Файл:Vertices 2-4.png Файл:Vertices 1-2-4.png
Файл:Vertex 4.png Файл:Vertex 4.png Файл:Vertices 1-4.png Файл:Vertices 2-4.png Файл:Vertices 3-4.png Файл:Vertices are missing.png Файл:Vertices 1-2-4.png Файл:Vertices 1-3-4.png Файл:Vertex 1.png Файл:Vertices 2-3-4.png Файл:Vertex 2.png Файл:Vertex 3.png Файл:Vertices 1-2-3-4.png Файл:Vertices 1-2.png Файл:Vertices 1-3.png Файл:Vertices 2-3.png Файл:Vertices 1-2-3.png
Файл:Vertices 1-2.png Файл:Vertices 1-2.png Файл:Vertex 2.png Файл:Vertex 1.png Файл:Vertices 1-2-3.png Файл:Vertices 1-2-4.png Файл:Vertices are missing.png Файл:Vertices 2-3.png Файл:Vertices 2-4.png Файл:Vertices 1-3.png Файл:Vertices 1-4.png Файл:Vertices 1-2-3-4.png Файл:Vertex 3.png Файл:Vertex 4.png Файл:Vertices 2-3-4.png Файл:Vertices 1-3-4.png Файл:Vertices 3-4.png
Файл:Vertices 1-3.png Файл:Vertices 1-3.png Файл:Vertex 3.png Файл:Vertices 1-2-3.png Файл:Vertex 1.png Файл:Vertices 1-3-4.png Файл:Vertices 2-3.png Файл:Vertices are missing.png Файл:Vertices 3-4.png Файл:Vertices 1-2.png Файл:Vertices 1-2-3-4.png Файл:Vertices 1-4.png Файл:Vertex 2.png Файл:Vertices 2-3-4.png Файл:Vertex 4.png Файл:Vertices 1-2-4.png Файл:Vertices 2-4.png
Файл:Vertices 1-4.png Файл:Vertices 1-4.png Файл:Vertex 4.png Файл:Vertices 1-2-4.png Файл:Vertices 1-3-4.png Файл:Vertex 1.png Файл:Vertices 2-4.png Файл:Vertices 3-4.png Файл:Vertices are missing.png Файл:Vertices 1-2-3-4.png Файл:Vertices 1-2.png Файл:Vertices 1-3.png Файл:Vertices 2-3-4.png Файл:Vertex 2.png Файл:Vertex 3.png Файл:Vertices 1-2-3.png Файл:Vertices 2-3.png
Файл:Vertices 2-3.png Файл:Vertices 2-3.png Файл:Vertices 1-2-3.png Файл:Vertex 3.png Файл:Vertex 2.png Файл:Vertices 2-3-4.png Файл:Vertices 1-3.png Файл:Vertices 1-2.png Файл:Vertices 1-2-3-4.png Файл:Vertices are missing.png Файл:Vertices 3-4.png Файл:Vertices 2-4.png Файл:Vertex 1.png Файл:Vertices 1-3-4.png Файл:Vertices 1-2-4.png Файл:Vertex 4.png Файл:Vertices 1-4.png
Файл:Vertices 2-4.png Файл:Vertices 2-4.png Файл:Vertices 1-2-4.png Файл:Vertex 4.png Файл:Vertices 2-3-4.png Файл:Vertex 2.png Файл:Vertices 1-4.png Файл:Vertices 1-2-3-4.png Файл:Vertices 1-2.png Файл:Vertices 3-4.png Файл:Vertices are missing.png Файл:Vertices 2-3.png Файл:Vertices 1-3-4.png Файл:Vertex 1.png Файл:Vertices 1-2-3.png Файл:Vertex 3.png Файл:Vertices 1-3.png
Файл:Vertices 3-4.png Файл:Vertices 3-4.png Файл:Vertices 1-3-4.png Файл:Vertices 2-3-4.png Файл:Vertex 4.png Файл:Vertex 3.png Файл:Vertices 1-2-3-4.png Файл:Vertices 1-4.png Файл:Vertices 1-3.png Файл:Vertices 2-4.png Файл:Vertices 2-3.png Файл:Vertices are missing.png Файл:Vertices 1-2-4.png Файл:Vertices 1-2-3.png Файл:Vertex 1.png Файл:Vertex 2.png Файл:Vertices 1-2.png
Файл:Vertices 1-2-3.png Файл:Vertices 1-2-3.png Файл:Vertices 2-3.png Файл:Vertices 1-3.png Файл:Vertices 1-2.png Файл:Vertices 1-2-3-4.png Файл:Vertex 3.png Файл:Vertex 2.png Файл:Vertices 2-3-4.png Файл:Vertex 1.png Файл:Vertices 1-3-4.png Файл:Vertices 1-2-4.png Файл:Vertices are missing.png Файл:Vertices 3-4.png Файл:Vertices 2-4.png Файл:Vertices 1-4.png Файл:Vertex 4.png
Файл:Vertices 1-2-4.png Файл:Vertices 1-2-4.png Файл:Vertices 2-4.png Файл:Vertices 1-4.png Файл:Vertices 1-2-3-4.png Файл:Vertices 1-2.png Файл:Vertex 4.png Файл:Vertices 2-3-4.png Файл:Vertex 2.png Файл:Vertices 1-3-4.png Файл:Vertex 1.png Файл:Vertices 1-2-3.png Файл:Vertices 3-4.png Файл:Vertices are missing.png Файл:Vertices 2-3.png Файл:Vertices 1-3.png Файл:Vertex 3.png
Файл:Vertices 1-3-4.png Файл:Vertices 1-3-4.png Файл:Vertices 3-4.png Файл:Vertices 1-2-3-4.png Файл:Vertices 1-4.png Файл:Vertices 1-3.png Файл:Vertices 2-3-4.png Файл:Vertex 4.png Файл:Vertex 3.png Файл:Vertices 1-2-4.png Файл:Vertices 1-2-3.png Файл:Vertex 1.png Файл:Vertices 2-4.png Файл:Vertices 2-3.png Файл:Vertices are missing.png Файл:Vertices 1-2.png Файл:Vertex 2.png
Файл:Vertices 2-3-4.png Файл:Vertices 2-3-4.png Файл:Vertices 1-2-3-4.png Файл:Vertices 3-4.png Файл:Vertices 2-4.png Файл:Vertices 2-3.png Файл:Vertices 1-3-4.png Файл:Vertices 1-2-4.png Файл:Vertices 1-2-3.png Файл:Vertex 4.png Файл:Vertex 3.png Файл:Vertex 2.png Файл:Vertices 1-4.png Файл:Vertices 1-3.png Файл:Vertices 1-2.png Файл:Vertices are missing.png Файл:Vertex 1.png
Файл:Vertices 1-2-3-4.png Файл:Vertices 1-2-3-4.png Файл:Vertices 2-3-4.png Файл:Vertices 1-3-4.png Файл:Vertices 1-2-4.png Файл:Vertices 1-2-3.png Файл:Vertices 3-4.png Файл:Vertices 2-4.png Файл:Vertices 2-3.png Файл:Vertices 1-4.png Файл:Vertices 1-3.png Файл:Vertices 1-2.png Файл:Vertex 4.png Файл:Vertex 3.png Файл:Vertex 2.png Файл:Vertex 1.png Файл:Vertices are missing.png
Пространство рёбер графа — это множество всех подмножеств множества всех рёбер графа, преобразованное в векторное пространство над 2-элементным полем <math>\{0, 1\}.</math> Обозначение пространства рёбер графа <math>G: \mathcal{E}(G).</math>
Полностью аналогично пространству вершин.
Структуру графа задают его рёбра, поэтому обычно имеют дело с пространством рёбер.
Ниже показана таблица сложения по модулю 2 векторов пространства рёбер <math>\mathcal{E}(C_4)</math> циклического графа <math>C_4</math>. Элементы подпространства разрезов <math>\mathcal{B}(C_4)</math> находятся внутри синих рамок, три элемента одного из базисов этого подпространства выделены синим. Подпространство циклов <math>\mathcal{C}(C_4)</math> в данном случае есть подпространство подпространства разрезов и состоит из двух элементов: пустого множества и графа <math>C_4</math>; его элементы выделены голубым.
Остовное дерево, шесть бондов и цикл графа <math>C_4</math>
Файл:Edges 1-2-3-4 spanning tree 1-2-3.png Файл:Edges 1-2.png Файл:Edges 1-3.png Файл:Edges 1-4.png Файл:Edges 2-3.png Файл:Edges 2-4.png Файл:Edges 3-4.png Файл:Edges 1-2-3-4.png
Синее
остовное
дерево 		Шесть бондов (минимальных разрезов).
Три элемента одного из базисов выделены синим 		Цикл
Таблица сложения по модулю 2 векторов пространства 4 рёбер графа <math>C_4</math>
<math>\oplus</math> Файл:Edges 0.png Файл:Edges 1.png Файл:Edges 2.png Файл:Edges 3.png Файл:Edges 4.png Файл:Edges 1-2.png Файл:Edges 1-3.png Файл:Edges 1-4.png Файл:Edges 2-3.png Файл:Edges 2-4.png Файл:Edges 3-4.png Файл:Edges 1-2-3.png Файл:Edges 1-2-4.png Файл:Edges 1-3-4.png Файл:Edges 2-3-4.png Файл:Edges 1-2-3-4.png
Файл:Edges 0.png Файл:Edges 0.png Файл:Edges 1.png Файл:Edges 2.png Файл:Edges 3.png Файл:Edges 4.png Файл:Edges 1-2.png Файл:Edges 1-3.png Файл:Edges 1-4.png Файл:Edges 2-3.png Файл:Edges 2-4.png Файл:Edges 3-4.png Файл:Edges 1-2-3.png Файл:Edges 1-2-4.png Файл:Edges 1-3-4.png Файл:Edges 2-3-4.png Файл:Edges 1-2-3-4.png
Файл:Edges 1.png Файл:Edges 1.png Файл:Edges 0.png Файл:Edges 1-2.png Файл:Edges 1-3.png Файл:Edges 1-4.png Файл:Edges 2.png Файл:Edges 3.png Файл:Edges 4.png Файл:Edges 1-2-3.png Файл:Edges 1-2-4.png Файл:Edges 1-3-4.png Файл:Edges 2-3.png Файл:Edges 2-4.png Файл:Edges 3-4.png Файл:Edges 1-2-3-4.png Файл:Edges 2-3-4.png
Файл:Edges 2.png Файл:Edges 2.png Файл:Edges 1-2.png Файл:Edges 0.png Файл:Edges 2-3.png Файл:Edges 2-4.png Файл:Edges 1.png Файл:Edges 1-2-3.png Файл:Edges 1-2-4.png Файл:Edges 3.png Файл:Edges 4.png Файл:Edges 2-3-4.png Файл:Edges 1-3.png Файл:Edges 1-4.png Файл:Edges 1-2-3-4.png Файл:Edges 3-4.png Файл:Edges 1-3-4.png
Файл:Edges 3.png Файл:Edges 3.png Файл:Edges 1-3.png Файл:Edges 2-3.png Файл:Edges 0.png Файл:Edges 3-4.png Файл:Edges 1-2-3.png Файл:Edges 1.png Файл:Edges 1-3-4.png Файл:Edges 2.png Файл:Edges 2-3-4.png Файл:Edges 4.png Файл:Edges 1-2.png Файл:Edges 1-2-3-4.png Файл:Edges 1-4.png Файл:Edges 2-4.png Файл:Edges 1-2-4.png
Файл:Edges 4.png Файл:Edges 4.png Файл:Edges 1-4.png Файл:Edges 2-4.png Файл:Edges 3-4.png Файл:Edges 0.png Файл:Edges 1-2-4.png Файл:Edges 1-3-4.png Файл:Edges 1.png Файл:Edges 2-3-4.png Файл:Edges 2.png Файл:Edges 3.png Файл:Edges 1-2-3-4.png Файл:Edges 1-2.png Файл:Edges 1-3.png Файл:Edges 2-3.png Файл:Edges 1-2-3.png
Файл:Edges 1-2.png Файл:Edges 1-2.png Файл:Edges 2.png Файл:Edges 1.png Файл:Edges 1-2-3.png Файл:Edges 1-2-4.png Файл:Edges 0.png Файл:Edges 2-3.png Файл:Edges 2-4.png Файл:Edges 1-3.png Файл:Edges 1-4.png Файл:Edges 1-2-3-4.png Файл:Edges 3.png Файл:Edges 4.png Файл:Edges 2-3-4.png Файл:Edges 1-3-4.png Файл:Edges 3-4.png
Файл:Edges 1-3.png Файл:Edges 1-3.png Файл:Edges 3.png Файл:Edges 1-2-3.png Файл:Edges 1.png Файл:Edges 1-3-4.png Файл:Edges 2-3.png Файл:Edges 0.png Файл:Edges 3-4.png Файл:Edges 1-2.png Файл:Edges 1-2-3-4.png Файл:Edges 1-4.png Файл:Edges 2.png Файл:Edges 2-3-4.png Файл:Edges 4.png Файл:Edges 1-2-4.png Файл:Edges 2-4.png
Файл:Edges 1-4.png Файл:Edges 1-4.png Файл:Edges 4.png Файл:Edges 1-2-4.png Файл:Edges 1-3-4.png Файл:Edges 1.png Файл:Edges 2-4.png Файл:Edges 3-4.png Файл:Edges 0.png Файл:Edges 1-2-3-4.png Файл:Edges 1-2.png Файл:Edges 1-3.png Файл:Edges 2-3-4.png Файл:Edges 2.png Файл:Edges 3.png Файл:Edges 1-2-3.png Файл:Edges 2-3.png
Файл:Edges 2-3.png Файл:Edges 2-3.png Файл:Edges 1-2-3.png Файл:Edges 3.png Файл:Edges 2.png Файл:Edges 2-3-4.png Файл:Edges 1-3.png Файл:Edges 1-2.png Файл:Edges 1-2-3-4.png Файл:Edges 0.png Файл:Edges 3-4.png Файл:Edges 2-4.png Файл:Edges 1.png Файл:Edges 1-3-4.png Файл:Edges 1-2-4.png Файл:Edges 4.png Файл:Edges 1-4.png
Файл:Edges 2-4.png Файл:Edges 2-4.png Файл:Edges 1-2-4.png Файл:Edges 4.png Файл:Edges 2-3-4.png Файл:Edges 2.png Файл:Edges 1-4.png Файл:Edges 1-2-3-4.png Файл:Edges 1-2.png Файл:Edges 3-4.png Файл:Edges 0.png Файл:Edges 2-3.png Файл:Edges 1-3-4.png Файл:Edges 1.png Файл:Edges 1-2-3.png Файл:Edges 3.png Файл:Edges 1-3.png
Файл:Edges 3-4.png Файл:Edges 3-4.png Файл:Edges 1-3-4.png Файл:Edges 2-3-4.png Файл:Edges 4.png Файл:Edges 3.png Файл:Edges 1-2-3-4.png Файл:Edges 1-4.png Файл:Edges 1-3.png Файл:Edges 2-4.png Файл:Edges 2-3.png Файл:Edges 0.png Файл:Edges 1-2-4.png Файл:Edges 1-2-3.png Файл:Edges 1.png Файл:Edges 2.png Файл:Edges 1-2.png
Файл:Edges 1-2-3.png Файл:Edges 1-2-3.png Файл:Edges 2-3.png Файл:Edges 1-3.png Файл:Edges 1-2.png Файл:Edges 1-2-3-4.png Файл:Edges 3.png Файл:Edges 2.png Файл:Edges 2-3-4.png Файл:Edges 1.png Файл:Edges 1-3-4.png Файл:Edges 1-2-4.png Файл:Edges 0.png Файл:Edges 3-4.png Файл:Edges 2-4.png Файл:Edges 1-4.png Файл:Edges 4.png
Файл:Edges 1-2-4.png Файл:Edges 1-2-4.png Файл:Edges 2-4.png Файл:Edges 1-4.png Файл:Edges 1-2-3-4.png Файл:Edges 1-2.png Файл:Edges 4.png Файл:Edges 2-3-4.png Файл:Edges 2.png Файл:Edges 1-3-4.png Файл:Edges 1.png Файл:Edges 1-2-3.png Файл:Edges 3-4.png Файл:Edges 0.png Файл:Edges 2-3.png Файл:Edges 1-3.png Файл:Edges 3.png
Файл:Edges 1-3-4.png Файл:Edges 1-3-4.png Файл:Edges 3-4.png Файл:Edges 1-2-3-4.png Файл:Edges 1-4.png Файл:Edges 1-3.png Файл:Edges 2-3-4.png Файл:Edges 4.png Файл:Edges 3.png Файл:Edges 1-2-4.png Файл:Edges 1-2-3.png Файл:Edges 1.png Файл:Edges 2-4.png Файл:Edges 2-3.png Файл:Edges 0.png Файл:Edges 1-2.png Файл:Edges 2.png
Файл:Edges 2-3-4.png Файл:Edges 2-3-4.png Файл:Edges 1-2-3-4.png Файл:Edges 3-4.png Файл:Edges 2-4.png Файл:Edges 2-3.png Файл:Edges 1-3-4.png Файл:Edges 1-2-4.png Файл:Edges 1-2-3.png Файл:Edges 4.png Файл:Edges 3.png Файл:Edges 2.png Файл:Edges 1-4.png Файл:Edges 1-3.png Файл:Edges 1-2.png Файл:Edges 0.png Файл:Edges 1.png
Файл:Edges 1-2-3-4.png Файл:Edges 1-2-3-4.png Файл:Edges 2-3-4.png Файл:Edges 1-3-4.png Файл:Edges 1-2-4.png Файл:Edges 1-2-3.png Файл:Edges 3-4.png Файл:Edges 2-4.png Файл:Edges 2-3.png Файл:Edges 1-4.png Файл:Edges 1-3.png Файл:Edges 1-2.png Файл:Edges 4.png Файл:Edges 3.png Файл:Edges 2.png Файл:Edges 1.png Файл:Edges 0.png
  • Пространство циклов графа — это подпространство пространства рёбер графа, которое порождается всеми простыми циклами графа. Обозначение пространства циклов графа <math>G: \mathcal{C}(G).</math>
Другими словами, пространство циклов натянуто на простые циклы, то есть состоит из:
  • пустого множества;
  • всех простых циклов графа;
  • всех сумм по модулю 2 простых циклов графа.
Теорема. Пространство циклов порождается также циклами без хорд.
Цикломатическое число, или циклический ранг, графа — это размерность пространства циклов графа.
Теорема. Цикломатическое число связного графа равно числу хорд любого остовного дерева графа, то есть равно <math>m - n + 1</math>, где <math>m</math> — число рёбер графа, <math>n</math> — число вершин.
Ниже показана таблица сложения по модулю 2 векторов пространства циклов <math>\mathcal{C}(G)</math> даного графа <math>G</math>, показанного ниже вместе с остовным деревом. Три элемента одного из базисов этого пространства выделены синим.
Остовное дерево и шесть простых циклов данного графа
Файл:Graph 5 vertices 7 edges - spanning tree.png Файл:Graph 5 vertices 7 edges - C1.png Файл:Graph 5 vertices 7 edges - C2.png Файл:Graph 5 vertices 7 edges - C3.png Файл:Graph 5 vertices 7 edges - C4.png Файл:Graph 5 vertices 7 edges - C5.png Файл:Graph 5 vertices 7 edges - C6.png
Остовное
дерево
графа <math>G</math> 		Шесть простых циклов данного графа.
Три элемента одного из базисов выделены синим
Таблица сложения по модулю 2 векторов пространства циклов
<math>\oplus</math> Файл:Edges 0.png Файл:Graph 5 vertices 7 edges - C1.png Файл:Graph 5 vertices 7 edges - C2.png Файл:Graph 5 vertices 7 edges - C3.png Файл:Graph 5 vertices 7 edges - C4.png Файл:Graph 5 vertices 7 edges - C5.png Файл:Graph 5 vertices 7 edges - C6.png Файл:Graph 5 vertices 7 edges - C1+C3.png
Файл:Edges 0.png Файл:Edges 0.png Файл:Graph 5 vertices 7 edges - C1.png Файл:Graph 5 vertices 7 edges - C2.png Файл:Graph 5 vertices 7 edges - C3.png Файл:Graph 5 vertices 7 edges - C4.png Файл:Graph 5 vertices 7 edges - C5.png Файл:Graph 5 vertices 7 edges - C6.png Файл:Graph 5 vertices 7 edges - C1+C3.png
Файл:Graph 5 vertices 7 edges - C1.png Файл:Graph 5 vertices 7 edges - C1.png Файл:Edges 0.png Файл:Graph 5 vertices 7 edges - C5.png Файл:Graph 5 vertices 7 edges - C1+C3.png Файл:Graph 5 vertices 7 edges - C6.png Файл:Graph 5 vertices 7 edges - C2.png Файл:Graph 5 vertices 7 edges - C4.png Файл:Graph 5 vertices 7 edges - C3.png
Файл:Graph 5 vertices 7 edges - C2.png Файл:Graph 5 vertices 7 edges - C2.png Файл:Graph 5 vertices 7 edges - C5.png Файл:Edges 0.png Файл:Graph 5 vertices 7 edges - C4.png Файл:Graph 5 vertices 7 edges - C3.png Файл:Graph 5 vertices 7 edges - C1.png Файл:Graph 5 vertices 7 edges - C1+C3.png Файл:Graph 5 vertices 7 edges - C6.png
Файл:Graph 5 vertices 7 edges - C3.png Файл:Graph 5 vertices 7 edges - C3.png Файл:Graph 5 vertices 7 edges - C1+C3.png Файл:Graph 5 vertices 7 edges - C4.png Файл:Edges 0.png Файл:Graph 5 vertices 7 edges - C2.png Файл:Graph 5 vertices 7 edges - C6.png Файл:Graph 5 vertices 7 edges - C5.png Файл:Graph 5 vertices 7 edges - C1.png
Файл:Graph 5 vertices 7 edges - C4.png Файл:Graph 5 vertices 7 edges - C4.png Файл:Graph 5 vertices 7 edges - C6.png Файл:Graph 5 vertices 7 edges - C3.png Файл:Graph 5 vertices 7 edges - C2.png Файл:Edges 0.png Файл:Graph 5 vertices 7 edges - C1+C3.png Файл:Graph 5 vertices 7 edges - C1.png Файл:Graph 5 vertices 7 edges - C5.png
Файл:Graph 5 vertices 7 edges - C5.png Файл:Graph 5 vertices 7 edges - C5.png Файл:Graph 5 vertices 7 edges - C2.png Файл:Graph 5 vertices 7 edges - C1.png Файл:Graph 5 vertices 7 edges - C6.png Файл:Graph 5 vertices 7 edges - C1+C3.png Файл:Edges 0.png Файл:Graph 5 vertices 7 edges - C3.png Файл:Graph 5 vertices 7 edges - C4.png
Файл:Graph 5 vertices 7 edges - C6.png Файл:Graph 5 vertices 7 edges - C6.png Файл:Graph 5 vertices 7 edges - C4.png Файл:Graph 5 vertices 7 edges - C1+C3.png Файл:Graph 5 vertices 7 edges - C5.png Файл:Graph 5 vertices 7 edges - C1.png Файл:Graph 5 vertices 7 edges - C3.png Файл:Edges 0.png Файл:Graph 5 vertices 7 edges - C2.png
Файл:Graph 5 vertices 7 edges - C1+C3.png Файл:Graph 5 vertices 7 edges - C1+C3.png Файл:Graph 5 vertices 7 edges - C3.png Файл:Graph 5 vertices 7 edges - C6.png Файл:Graph 5 vertices 7 edges - C1.png Файл:Graph 5 vertices 7 edges - C5.png Файл:Graph 5 vertices 7 edges - C4.png Файл:Graph 5 vertices 7 edges - C2.png Файл:Edges 0.png
Другими словами, пространство разрезов натянуто на минимальные разрезы, то есть состоит из:
  • пустого множества;
  • всех минимальных разрезов графа;
  • всех сумм по модулю 2 минимальных разрезов графа.
Теорема. Пространство разрезов порождается также разрезами, одно из двух множеств разбиения которых — изолированная вершина.
Ранг разрезов графа — это размерность пространства разрезов графа.
Теорема. Ранг разрезов связного графа равен числу рёбер любого остовного дерева графа, то есть равен <math>n - 1</math>, где <math>n</math> — число вершин графа.
Ниже показана таблица сложения по модулю 2 векторов пространства разрезов <math>\mathcal{B}(G)</math> даного графа <math>G</math>, показанного ниже вместе с остовным деревом. Четыре элемента одного из базисов этого пространства выделены синим.
Остовное дерево и десять бондов данного графа <math>G</math>
Файл:Graph 5 vertices 7 edges - spanning tree.png Файл:Graph 5 vertices 7 edges - B1.png Файл:Graph 5 vertices 7 edges - B2.png Файл:Graph 5 vertices 7 edges - B3.png Файл:Graph 5 vertices 7 edges - B4.png Файл:Graph 5 vertices 7 edges - B5.png Файл:Graph 5 vertices 7 edges - B6.png Файл:Graph 5 vertices 7 edges - B7.png Файл:Graph 5 vertices 7 edges - B8.png Файл:Graph 5 vertices 7 edges - B9.png Файл:Graph 5 vertices 7 edges - B10.png
Остовное
дерево
графа <math>G</math> 		Десять бондов (минимальных разрезов) данного графа.
Четыре элемента одного из базисов выделены синим
Таблица сложения по модулю 2 векторов пространства разрезов
<math>\oplus</math> Файл:Edges 0.png Файл:Graph 5 vertices 7 edges - B1.png Файл:Graph 5 vertices 7 edges - B2.png Файл:Graph 5 vertices 7 edges - B3.png Файл:Graph 5 vertices 7 edges - B4.png Файл:Graph 5 vertices 7 edges - B5.png Файл:Graph 5 vertices 7 edges - B6.png Файл:Graph 5 vertices 7 edges - B7.png Файл:Graph 5 vertices 7 edges - B8.png Файл:Graph 5 vertices 7 edges - B9.png Файл:Graph 5 vertices 7 edges - B10.png Файл:Graph 5 vertices 7 edges - B1+B4.png Файл:Graph 5 vertices 7 edges - B1+B5.png Файл:Graph 5 vertices 7 edges - B1+B10.png Файл:Graph 5 vertices 7 edges - B2+B5.png Файл:Graph 5 vertices 7 edges - B3+B4.png
Файл:Edges 0.png Файл:Edges 0.png Файл:Graph 5 vertices 7 edges - B1.png Файл:Graph 5 vertices 7 edges - B2.png Файл:Graph 5 vertices 7 edges - B3.png Файл:Graph 5 vertices 7 edges - B4.png Файл:Graph 5 vertices 7 edges - B5.png Файл:Graph 5 vertices 7 edges - B6.png Файл:Graph 5 vertices 7 edges - B7.png Файл:Graph 5 vertices 7 edges - B8.png Файл:Graph 5 vertices 7 edges - B9.png Файл:Graph 5 vertices 7 edges - B10.png Файл:Graph 5 vertices 7 edges - B1+B4.png Файл:Graph 5 vertices 7 edges - B1+B5.png Файл:Graph 5 vertices 7 edges - B1+B10.png Файл:Graph 5 vertices 7 edges - B2+B5.png Файл:Graph 5 vertices 7 edges - B3+B4.png
Файл:Graph 5 vertices 7 edges - B1.png Файл:Graph 5 vertices 7 edges - B1.png Файл:Edges 0.png Файл:Graph 5 vertices 7 edges - B6.png Файл:Graph 5 vertices 7 edges - B7.png Файл:Graph 5 vertices 7 edges - B1+B4.png Файл:Graph 5 vertices 7 edges - B1+B5.png Файл:Graph 5 vertices 7 edges - B2.png Файл:Graph 5 vertices 7 edges - B3.png Файл:Graph 5 vertices 7 edges - B9.png Файл:Graph 5 vertices 7 edges - B8.png Файл:Graph 5 vertices 7 edges - B1+B10.png Файл:Graph 5 vertices 7 edges - B4.png Файл:Graph 5 vertices 7 edges - B5.png Файл:Graph 5 vertices 7 edges - B10.png Файл:Graph 5 vertices 7 edges - B3+B4.png Файл:Graph 5 vertices 7 edges - B2+B5.png
Файл:Graph 5 vertices 7 edges - B2.png Файл:Graph 5 vertices 7 edges - B2.png Файл:Graph 5 vertices 7 edges - B6.png Файл:Edges 0.png Файл:Graph 5 vertices 7 edges - B1+B10.png Файл:Graph 5 vertices 7 edges - B8.png Файл:Graph 5 vertices 7 edges - B2+B5.png Файл:Graph 5 vertices 7 edges - B1.png Файл:Graph 5 vertices 7 edges - B10.png Файл:Graph 5 vertices 7 edges - B4.png Файл:Graph 5 vertices 7 edges - B1+B4.png Файл:Graph 5 vertices 7 edges - B7.png Файл:Graph 5 vertices 7 edges - B9.png Файл:Graph 5 vertices 7 edges - B3+B4.png Файл:Graph 5 vertices 7 edges - B3.png Файл:Graph 5 vertices 7 edges - B5.png Файл:Graph 5 vertices 7 edges - B1+B5.png
Файл:Graph 5 vertices 7 edges - B3.png Файл:Graph 5 vertices 7 edges - B3.png Файл:Graph 5 vertices 7 edges - B7.png Файл:Graph 5 vertices 7 edges - B1+B10.png Файл:Edges 0.png Файл:Graph 5 vertices 7 edges - B3+B4.png Файл:Graph 5 vertices 7 edges - B9.png Файл:Graph 5 vertices 7 edges - B10.png Файл:Graph 5 vertices 7 edges - B1.png Файл:Graph 5 vertices 7 edges - B1+B5.png Файл:Graph 5 vertices 7 edges - B5.png Файл:Graph 5 vertices 7 edges - B6.png Файл:Graph 5 vertices 7 edges - B2+B5.png Файл:Graph 5 vertices 7 edges - B8.png Файл:Graph 5 vertices 7 edges - B2.png Файл:Graph 5 vertices 7 edges - B1+B4.png Файл:Graph 5 vertices 7 edges - B4.png
Файл:Graph 5 vertices 7 edges - B4.png Файл:Graph 5 vertices 7 edges - B4.png Файл:Graph 5 vertices 7 edges - B1+B4.png Файл:Graph 5 vertices 7 edges - B8.png Файл:Graph 5 vertices 7 edges - B3+B4.png Файл:Edges 0.png Файл:Graph 5 vertices 7 edges - B10.png Файл:Graph 5 vertices 7 edges - B9.png Файл:Graph 5 vertices 7 edges - B2+B5.png Файл:Graph 5 vertices 7 edges - B2.png Файл:Graph 5 vertices 7 edges - B6.png Файл:Graph 5 vertices 7 edges - B5.png Файл:Graph 5 vertices 7 edges - B1.png Файл:Graph 5 vertices 7 edges - B1+B10.png Файл:Graph 5 vertices 7 edges - B1+B5.png Файл:Graph 5 vertices 7 edges - B7.png Файл:Graph 5 vertices 7 edges - B3.png
Файл:Graph 5 vertices 7 edges - B5.png Файл:Graph 5 vertices 7 edges - B5.png Файл:Graph 5 vertices 7 edges - B1+B5.png Файл:Graph 5 vertices 7 edges - B2+B5.png Файл:Graph 5 vertices 7 edges - B9.png Файл:Graph 5 vertices 7 edges - B10.png Файл:Edges 0.png Файл:Graph 5 vertices 7 edges - B3+B4.png Файл:Graph 5 vertices 7 edges - B8.png Файл:Graph 5 vertices 7 edges - B7.png Файл:Graph 5 vertices 7 edges - B3.png Файл:Graph 5 vertices 7 edges - B4.png Файл:Graph 5 vertices 7 edges - B1+B10.png Файл:Graph 5 vertices 7 edges - B1.png Файл:Graph 5 vertices 7 edges - B1+B4.png Файл:Graph 5 vertices 7 edges - B2.png Файл:Graph 5 vertices 7 edges - B6.png
Файл:Graph 5 vertices 7 edges - B6.png Файл:Graph 5 vertices 7 edges - B6.png Файл:Graph 5 vertices 7 edges - B2.png Файл:Graph 5 vertices 7 edges - B1.png Файл:Graph 5 vertices 7 edges - B10.png Файл:Graph 5 vertices 7 edges - B9.png Файл:Graph 5 vertices 7 edges - B3+B4.png Файл:Edges 0.png Файл:Graph 5 vertices 7 edges - B1+B10.png Файл:Graph 5 vertices 7 edges - B1+B4.png Файл:Graph 5 vertices 7 edges - B4.png Файл:Graph 5 vertices 7 edges - B3.png Файл:Graph 5 vertices 7 edges - B8.png Файл:Graph 5 vertices 7 edges - B2+B5.png Файл:Graph 5 vertices 7 edges - B7.png Файл:Graph 5 vertices 7 edges - B1+B5.png Файл:Graph 5 vertices 7 edges - B5.png
Файл:Graph 5 vertices 7 edges - B7.png Файл:Graph 5 vertices 7 edges - B7.png Файл:Graph 5 vertices 7 edges - B3.png Файл:Graph 5 vertices 7 edges - B10.png Файл:Graph 5 vertices 7 edges - B1.png Файл:Graph 5 vertices 7 edges - B2+B5.png Файл:Graph 5 vertices 7 edges - B8.png Файл:Graph 5 vertices 7 edges - B1+B10.png Файл:Edges 0.png Файл:Graph 5 vertices 7 edges - B5.png Файл:Graph 5 vertices 7 edges - B1+B5.png Файл:Graph 5 vertices 7 edges - B2.png Файл:Graph 5 vertices 7 edges - B3+B4.png Файл:Graph 5 vertices 7 edges - B9.png Файл:Graph 5 vertices 7 edges - B6.png Файл:Graph 5 vertices 7 edges - B4.png Файл:Graph 5 vertices 7 edges - B1+B4.png
Файл:Graph 5 vertices 7 edges - B8.png Файл:Graph 5 vertices 7 edges - B8.png Файл:Graph 5 vertices 7 edges - B9.png Файл:Graph 5 vertices 7 edges - B4.png Файл:Graph 5 vertices 7 edges - B1+B5.png Файл:Graph 5 vertices 7 edges - B2.png Файл:Graph 5 vertices 7 edges - B7.png Файл:Graph 5 vertices 7 edges - B1+B4.png Файл:Graph 5 vertices 7 edges - B5.png Файл:Edges 0.png Файл:Graph 5 vertices 7 edges - B1.png Файл:Graph 5 vertices 7 edges - B2+B5.png Файл:Graph 5 vertices 7 edges - B6.png Файл:Graph 5 vertices 7 edges - B3.png Файл:Graph 5 vertices 7 edges - B3+B4.png Файл:Graph 5 vertices 7 edges - B10.png Файл:Graph 5 vertices 7 edges - B1+B10.png
Файл:Graph 5 vertices 7 edges - B9.png Файл:Graph 5 vertices 7 edges - B9.png Файл:Graph 5 vertices 7 edges - B8.png Файл:Graph 5 vertices 7 edges - B1+B4.png Файл:Graph 5 vertices 7 edges - B5.png Файл:Graph 5 vertices 7 edges - B6.png Файл:Graph 5 vertices 7 edges - B3.png Файл:Graph 5 vertices 7 edges - B4.png Файл:Graph 5 vertices 7 edges - B1+B5.png Файл:Graph 5 vertices 7 edges - B1.png Файл:Edges 0.png Файл:Graph 5 vertices 7 edges - B3+B4.png Файл:Graph 5 vertices 7 edges - B2.png Файл:Graph 5 vertices 7 edges - B7.png Файл:Graph 5 vertices 7 edges - B2+B5.png Файл:Graph 5 vertices 7 edges - B1+B10.png Файл:Graph 5 vertices 7 edges - B10.png
Файл:Graph 5 vertices 7 edges - B10.png Файл:Graph 5 vertices 7 edges - B10.png Файл:Graph 5 vertices 7 edges - B1+B10.png Файл:Graph 5 vertices 7 edges - B7.png Файл:Graph 5 vertices 7 edges - B6.png Файл:Graph 5 vertices 7 edges - B5.png Файл:Graph 5 vertices 7 edges - B4.png Файл:Graph 5 vertices 7 edges - B3.png Файл:Graph 5 vertices 7 edges - B2.png Файл:Graph 5 vertices 7 edges - B2+B5.png Файл:Graph 5 vertices 7 edges - B3+B4.png Файл:Edges 0.png Файл:Graph 5 vertices 7 edges - B1+B5.png Файл:Graph 5 vertices 7 edges - B1+B4.png Файл:Graph 5 vertices 7 edges - B1.png Файл:Graph 5 vertices 7 edges - B8.png Файл:Graph 5 vertices 7 edges - B9.png
Файл:Graph 5 vertices 7 edges - B1+B4.png Файл:Graph 5 vertices 7 edges - B1+B4.png Файл:Graph 5 vertices 7 edges - B4.png Файл:Graph 5 vertices 7 edges - B9.png Файл:Graph 5 vertices 7 edges - B2+B5.png Файл:Graph 5 vertices 7 edges - B1.png Файл:Graph 5 vertices 7 edges - B1+B10.png Файл:Graph 5 vertices 7 edges - B8.png Файл:Graph 5 vertices 7 edges - B3+B4.png Файл:Graph 5 vertices 7 edges - B6.png Файл:Graph 5 vertices 7 edges - B2.png Файл:Graph 5 vertices 7 edges - B1+B5.png Файл:Edges 0.png Файл:Graph 5 vertices 7 edges - B10.png Файл:Graph 5 vertices 7 edges - B5.png Файл:Graph 5 vertices 7 edges - B3.png Файл:Graph 5 vertices 7 edges - B7.png
Файл:Graph 5 vertices 7 edges - B1+B5.png Файл:Graph 5 vertices 7 edges - B1+B5.png Файл:Graph 5 vertices 7 edges - B5.png Файл:Graph 5 vertices 7 edges - B3+B4.png Файл:Graph 5 vertices 7 edges - B8.png Файл:Graph 5 vertices 7 edges - B1+B10.png Файл:Graph 5 vertices 7 edges - B1.png Файл:Graph 5 vertices 7 edges - B2+B5.png Файл:Graph 5 vertices 7 edges - B9.png Файл:Graph 5 vertices 7 edges - B3.png Файл:Graph 5 vertices 7 edges - B7.png Файл:Graph 5 vertices 7 edges - B1+B4.png Файл:Graph 5 vertices 7 edges - B10.png Файл:Edges 0.png Файл:Graph 5 vertices 7 edges - B4.png Файл:Graph 5 vertices 7 edges - B6.png Файл:Graph 5 vertices 7 edges - B2.png
Файл:Graph 5 vertices 7 edges - B1+B10.png Файл:Graph 5 vertices 7 edges - B1+B10.png Файл:Graph 5 vertices 7 edges - B10.png Файл:Graph 5 vertices 7 edges - B3.png Файл:Graph 5 vertices 7 edges - B2.png Файл:Graph 5 vertices 7 edges - B1+B5.png Файл:Graph 5 vertices 7 edges - B1+B4.png Файл:Graph 5 vertices 7 edges - B7.png Файл:Graph 5 vertices 7 edges - B6.png Файл:Graph 5 vertices 7 edges - B3+B4.png Файл:Graph 5 vertices 7 edges - B2+B5.png Файл:Graph 5 vertices 7 edges - B1.png Файл:Graph 5 vertices 7 edges - B5.png Файл:Graph 5 vertices 7 edges - B4.png Файл:Edges 0.png Файл:Graph 5 vertices 7 edges - B9.png Файл:Graph 5 vertices 7 edges - B8.png
Файл:Graph 5 vertices 7 edges - B2+B5.png Файл:Graph 5 vertices 7 edges - B2+B5.png Файл:Graph 5 vertices 7 edges - B3+B4.png Файл:Graph 5 vertices 7 edges - B5.png Файл:Graph 5 vertices 7 edges - B1+B4.png Файл:Graph 5 vertices 7 edges - B7.png Файл:Graph 5 vertices 7 edges - B2.png Файл:Graph 5 vertices 7 edges - B1+B5.png Файл:Graph 5 vertices 7 edges - B4.png Файл:Graph 5 vertices 7 edges - B10.png Файл:Graph 5 vertices 7 edges - B1+B10.png Файл:Graph 5 vertices 7 edges - B8.png Файл:Graph 5 vertices 7 edges - B3.png Файл:Graph 5 vertices 7 edges - B6.png Файл:Graph 5 vertices 7 edges - B9.png Файл:Edges 0.png Файл:Graph 5 vertices 7 edges - B1.png
Файл:Graph 5 vertices 7 edges - B3+B4.png Файл:Graph 5 vertices 7 edges - B3+B4.png Файл:Graph 5 vertices 7 edges - B2+B5.png Файл:Graph 5 vertices 7 edges - B1+B5.png Файл:Graph 5 vertices 7 edges - B4.png Файл:Graph 5 vertices 7 edges - B3.png Файл:Graph 5 vertices 7 edges - B6.png Файл:Graph 5 vertices 7 edges - B5.png Файл:Graph 5 vertices 7 edges - B1+B4.png Файл:Graph 5 vertices 7 edges - B1+B10.png Файл:Graph 5 vertices 7 edges - B10.png Файл:Graph 5 vertices 7 edges - B9.png Файл:Graph 5 vertices 7 edges - B7.png Файл:Graph 5 vertices 7 edges - B2.png Файл:Graph 5 vertices 7 edges - B8.png Файл:Graph 5 vertices 7 edges - B1.png Файл:Edges 0.png

Применение теории графов

Шаблон:Основная статья

Уже в XIX веке графы применялись при проектировании электрических цепей и молекулярных схем; математические развлечения и головоломки — тоже часть теории графовШаблон:Sfn.

Иногда эту задачу переносят на систему мостов других городов. Например, была опубликована задача о 17 мостах устья Невы города Ленинграда 1940 годаШаблон:Sfn.
  • Проблема четырёх красок — можно ли любую карту окрасить в четыре цвета так, чтобы смежные страны имели различные цвета? Сформулирована в 1852 году, в 1977 году опубликовано (анонсировано в 1976) первое общепринятое положительное доказательство с использованием компьютераШаблон:SfnШаблон:SfnШаблон:SfnШаблон:SfnШаблон:SfnШаблон:SfnШаблон:Sfn.
  • Задача о домино. Все 28 костей игры в домино должны соединиться в непрерывную (простую) цепь так, чтобы граничащие половинки двух камней имели одно и то же число. Так как наличие дублей задачу не усложняет, задача о домино ставится также для 21 кости (без дублей) без потери общностиШаблон:SfnШаблон:SfnШаблон:Sfn.
  • Задача о лабиринте. Войти в произвольный лабиринт и пройти по всем его коридорамШаблон:SfnШаблон:Sfn.
  • Задача о трёх домах и трёх колодцах. Проложить непересекающиеся дорожки от каждого из трёх домов к каждому из трёх колодцев. Эта задача, как и задача о кёнигсбергских мостах, решения не имеетШаблон:Sfn.
  • Задача о ходе коня. Обойти конём шахматную доску, посетив каждую клетку ровно один раз с возвратом на исходную клеткуШаблон:Sfn.
  • Задача о назначениях. Пусть компании требуется несколько различных видов работ, причём каждый сотрудник подходит только для некоторых из них и может выполнять не более одной работы за раз. Как следует распределять задания, чтобы выполнять максимальное количество заданий одновременно? Решить задачу помогает двудольный граф, в котором вершины одной доли — сотрудники, другой — рабочие места, и каждое ребро — подходящее назначение на работуШаблон:Sfn.

К теории графов также относится целый ряд математических проблем, не решённых на сегодняшний день.

См. также

Примечания

Шаблон:Примечания

Источники

Ссылки

Внешние ссылки


Шаблон:Выбор языка Шаблон:Разделы математики Шаблон:Алгоритмы на графах Шаблон:Алгоритмы поиска на графах

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Теория_графов&oldid=10920508