Теория графов — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Раскраски графов)
(Задача о паросочетании)
(не показано 7 промежуточных версий 5 участников)
Строка 33: Строка 33:
 
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]
 
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]
 
* [[Задача о динамической связности оффлайн]]<tex>^\star</tex>
 
* [[Задача о динамической связности оффлайн]]<tex>^\star</tex>
 +
* [[Задача о динамической связности]]
  
 
== Остовные деревья ==
 
== Остовные деревья ==
Строка 97: Строка 98:
 
* [[Формула Уитни]]
 
* [[Формула Уитни]]
 
* [[Теорема Брукса]]
 
* [[Теорема Брукса]]
 +
* [[Хроматическое число планарного графа]]
 
* [[Верхние и нижние оценки хроматического числа]]<tex>^\star</tex>
 
* [[Верхние и нижние оценки хроматического числа]]<tex>^\star</tex>
* [[Хроматическое число планарного графа]]
+
* [[Проблема четырех красок]]<tex>^\star</tex>
 
* [[Многочлен Татта]]<tex>^\star</tex>
 
* [[Многочлен Татта]]<tex>^\star</tex>
 
* [[Теория Рамсея]]<tex>^\star</tex>
 
* [[Теория Рамсея]]<tex>^\star</tex>
 
* [[Рёберная раскраска двудольного графа]]
 
* [[Рёберная раскраска двудольного графа]]
 
* [[Теорема Турана об экстремальном графе]]
 
* [[Теорема Турана об экстремальном графе]]
 +
* [[Гипотеза Хивуда]]
  
 
== Обход в глубину ==
 
== Обход в глубину ==
Строка 144: Строка 147:
 
* [[Совершенное паросочетание в кубическом графе]]<tex>^\star</tex>
 
* [[Совершенное паросочетание в кубическом графе]]<tex>^\star</tex>
 
* [[Теорема о существовании совершенного паросочетания в графе, полученном из регулярного удалением ребёр]]
 
* [[Теорема о существовании совершенного паросочетания в графе, полученном из регулярного удалением ребёр]]
 +
* [[Теорема Самнера — Лас Вергнаса]]
  
 
== Задача о максимальном потоке ==
 
== Задача о максимальном потоке ==
Строка 177: Строка 181:
 
* [[Венгерский алгоритм решения задачи о назначениях]]
 
* [[Венгерский алгоритм решения задачи о назначениях]]
 
* [[Алгоритм отмены цикла минимального среднего веса]]<tex>^\star</tex>
 
* [[Алгоритм отмены цикла минимального среднего веса]]<tex>^\star</tex>
 +
 +
== Случайные графы ==
 +
* [[Случайные графы|Введение: определения, наличие треугольников, связность, диаметр два]]
 +
* [[Теорема о гигантской компоненте. Поиск в ширину в случайном графе|Теорема о гигантской компоненте. Поиск в ширину в случайном графе]]
 +
* [[Теорема о существовании порога для монотонных свойств | Теорема о существовании порога для монотонных свойств]]
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Теория графов]]
 
[[Категория: Теория графов]]

Версия 19:29, 9 февраля 2021

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

Связность в графах

Остовные деревья

Построение остовных деревьев

Свойства остовных деревьев

Обходы графов

Эйлеровы графы

Гамильтоновы графы

Укладки графов

Раскраски графов

Обход в глубину

Кратчайшие пути в графах

Задача о паросочетании

Задача о максимальном потоке

Задача о потоке минимальной стоимости

Случайные графы