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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
(Задача о паросочетании)
(не показано 11 промежуточных версий 8 участников)
Строка 18: Строка 18:
 
* [[Гиперграфы]]<tex>^\star</tex>
 
* [[Гиперграфы]]<tex>^\star</tex>
 
* [[Алгебра графов]]<tex>^\star</tex>
 
* [[Алгебра графов]]<tex>^\star</tex>
 +
* [[Барицентр дерева]]
  
 
== Связность в графах ==
 
== Связность в графах ==
Строка 32: Строка 33:
 
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]
 
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]
 
* [[Задача о динамической связности оффлайн]]<tex>^\star</tex>
 
* [[Задача о динамической связности оффлайн]]<tex>^\star</tex>
 +
* [[Задача о динамической связности]]
  
 
== Остовные деревья ==
 
== Остовные деревья ==
Строка 59: Строка 61:
 
* [[Алгоритм построения Эйлерова цикла]]
 
* [[Алгоритм построения Эйлерова цикла]]
 
* [[Произвольно вычерчиваемые из заданной вершины графы]]
 
* [[Произвольно вычерчиваемые из заданной вершины графы]]
 +
* [[Графы де Брюина]]
 
* [[Деревья Эйлерова обхода]]<tex>^\star</tex>
 
* [[Деревья Эйлерова обхода]]<tex>^\star</tex>
  
Строка 95: Строка 98:
 
* [[Формула Уитни]]
 
* [[Формула Уитни]]
 
* [[Теорема Брукса]]
 
* [[Теорема Брукса]]
 +
* [[Хроматическое число планарного графа]]
 
* [[Верхние и нижние оценки хроматического числа]]<tex>^\star</tex>
 
* [[Верхние и нижние оценки хроматического числа]]<tex>^\star</tex>
* [[Хроматическое число планарного графа]]
+
* [[Проблема четырех красок]]<tex>^\star</tex>
 
* [[Многочлен Татта]]<tex>^\star</tex>
 
* [[Многочлен Татта]]<tex>^\star</tex>
 
* [[Теория Рамсея]]<tex>^\star</tex>
 
* [[Теория Рамсея]]<tex>^\star</tex>
 
* [[Рёберная раскраска двудольного графа]]
 
* [[Рёберная раскраска двудольного графа]]
 +
* [[Теорема Турана об экстремальном графе]]
 +
* [[Гипотеза Хивуда]]
  
 
== Обход в глубину ==
 
== Обход в глубину ==
Строка 136: Строка 142:
 
* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]
 
* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]
 
* [[Декомпозиция Эдмондса-Галлаи]]
 
* [[Декомпозиция Эдмондса-Галлаи]]
 +
* [[Лапы и минимальные по включению барьеры в графе]]
 +
* [[Пересечение всех максимальных по включению барьеров]]
 
* [[Задача об устойчивом паросочетании]]<tex>^\star</tex>
 
* [[Задача об устойчивом паросочетании]]<tex>^\star</tex>
 
* [[Совершенное паросочетание в кубическом графе]]<tex>^\star</tex>
 
* [[Совершенное паросочетание в кубическом графе]]<tex>^\star</tex>
 
* [[Теорема о существовании совершенного паросочетания в графе, полученном из регулярного удалением ребёр]]
 
* [[Теорема о существовании совершенного паросочетания в графе, полученном из регулярного удалением ребёр]]
* [[Лапы и минимальные по включению барьеры в графе]]
+
* [[Теорема Самнера — Лас Вергнаса]]
  
 
== Задача о максимальном потоке ==
 
== Задача о максимальном потоке ==
Строка 173: Строка 181:
 
* [[Венгерский алгоритм решения задачи о назначениях]]
 
* [[Венгерский алгоритм решения задачи о назначениях]]
 
* [[Алгоритм отмены цикла минимального среднего веса]]<tex>^\star</tex>
 
* [[Алгоритм отмены цикла минимального среднего веса]]<tex>^\star</tex>
 +
 +
== Случайные графы ==
 +
* [[Случайные графы|Введение: определения, наличие треугольников, связность, диаметр два]]
 +
* [[Теорема о гигантской компоненте. Поиск в ширину в случайном графе|Теорема о гигантской компоненте. Поиск в ширину в случайном графе]]
 +
* [[Теорема о существовании порога для монотонных свойств | Теорема о существовании порога для монотонных свойств]]
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Теория графов]]
 
[[Категория: Теория графов]]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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