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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Раскраски графов)
(Задача о паросочетании)
(Метки: правка с мобильного устройства, правка из мобильной версии)
 
(не показано 16 промежуточных версий 13 участников)
Строка 17: Строка 17:
 
* [[Группы графов]]<tex>^\star</tex>
 
* [[Группы графов]]<tex>^\star</tex>
 
* [[Гиперграфы]]<tex>^\star</tex>
 
* [[Гиперграфы]]<tex>^\star</tex>
 +
* [[Алгебра графов]]<tex>^\star</tex>
 +
* [[Барицентр дерева]]
  
 
== Связность в графах ==
 
== Связность в графах ==
Строка 31: Строка 33:
 
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]
 
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]
 
* [[Задача о динамической связности оффлайн]]<tex>^\star</tex>
 
* [[Задача о динамической связности оффлайн]]<tex>^\star</tex>
 +
* [[Задача о динамической связности]]
  
 
== Остовные деревья ==
 
== Остовные деревья ==
Строка 42: Строка 45:
 
* [[Минимально узкое остовное дерево]]
 
* [[Минимально узкое остовное дерево]]
 
* [[Остовное дерево в планарном графе]]
 
* [[Остовное дерево в планарном графе]]
 +
* [[Максимальное количество попарно непересекающихся остовных деревьев в графе с n вершинами]]
  
 
=== Свойства остовных деревьев ===
 
=== Свойства остовных деревьев ===
Строка 57: Строка 61:
 
* [[Алгоритм построения Эйлерова цикла]]
 
* [[Алгоритм построения Эйлерова цикла]]
 
* [[Произвольно вычерчиваемые из заданной вершины графы]]
 
* [[Произвольно вычерчиваемые из заданной вершины графы]]
 +
* [[Графы де Брюина]]
 
* [[Деревья Эйлерова обхода]]<tex>^\star</tex>
 
* [[Деревья Эйлерова обхода]]<tex>^\star</tex>
  
Строка 93: Строка 98:
 
* [[Формула Уитни]]
 
* [[Формула Уитни]]
 
* [[Теорема Брукса]]
 
* [[Теорема Брукса]]
 +
* [[Хроматическое число планарного графа]]
 
* [[Верхние и нижние оценки хроматического числа]]<tex>^\star</tex>
 
* [[Верхние и нижние оценки хроматического числа]]<tex>^\star</tex>
* [[Хроматическое число планарного графа]]
+
* [[Проблема четырех красок]]<tex>^\star</tex>
 
* [[Многочлен Татта]]<tex>^\star</tex>
 
* [[Многочлен Татта]]<tex>^\star</tex>
 
* [[Теория Рамсея]]<tex>^\star</tex>
 
* [[Теория Рамсея]]<tex>^\star</tex>
 
* [[Рёберная раскраска двудольного графа]]
 
* [[Рёберная раскраска двудольного графа]]
 +
* [[Теорема Турана об экстремальном графе]]
 +
* [[Гипотеза Хивуда]]
  
 
== Обход в глубину ==
 
== Обход в глубину ==
Строка 133: Строка 141:
 
* [[Теорема Татта о существовании полного паросочетания]]
 
* [[Теорема Татта о существовании полного паросочетания]]
 
* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]
 
* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]
* [[Декомпозиция Эдмондса-Галлаи]]
+
* [[Декомпозиция Эдмондса-Галлаи | Декомпозиция Эдмондса-Галлаи. Формула Бержа]]
 +
* [[Лапы и минимальные по включению барьеры в графе]]
 +
* [[Пересечение всех максимальных по включению барьеров]]
 
* [[Задача об устойчивом паросочетании]]<tex>^\star</tex>
 
* [[Задача об устойчивом паросочетании]]<tex>^\star</tex>
 
* [[Совершенное паросочетание в кубическом графе]]<tex>^\star</tex>
 
* [[Совершенное паросочетание в кубическом графе]]<tex>^\star</tex>
 +
* [[Теорема о существовании совершенного паросочетания в графе, полученном из регулярного удалением ребёр]]
 +
* [[Теорема Самнера — Лас Вергнаса]]
  
 
== Задача о максимальном потоке ==
 
== Задача о максимальном потоке ==
Строка 169: Строка 181:
 
* [[Венгерский алгоритм решения задачи о назначениях]]
 
* [[Венгерский алгоритм решения задачи о назначениях]]
 
* [[Алгоритм отмены цикла минимального среднего веса]]<tex>^\star</tex>
 
* [[Алгоритм отмены цикла минимального среднего веса]]<tex>^\star</tex>
 +
 +
== Случайные графы ==
 +
* [[Случайные графы|Введение: определения, наличие треугольников, связность, диаметр два]]
 +
* [[Теорема о гигантской компоненте. Поиск в ширину в случайном графе|Теорема о гигантской компоненте. Поиск в ширину в случайном графе]]
 +
* [[Теорема о существовании порога для монотонных свойств | Теорема о существовании порога для монотонных свойств]]
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Теория графов]]
 
[[Категория: Теория графов]]

Текущая версия на 14:16, 14 июня 2021

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

Связность в графах[править]

Остовные деревья[править]

Построение остовных деревьев[править]

Свойства остовных деревьев[править]

Обходы графов[править]

Эйлеровы графы[править]

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

Укладки графов[править]

Раскраски графов[править]

Обход в глубину[править]

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

Задача о паросочетании[править]

Задача о максимальном потоке[править]

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

Случайные графы[править]