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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «== Основные определения теории графов == * [[Основные определения теории графов|Основные о...»)
 
м (rollbackEdits.php mass rollback)
 
(не показаны 22 промежуточные версии 18 участников)
Строка 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 вершинами]]
  
 
=== Свойства остовных деревьев ===
 
=== Свойства остовных деревьев ===
Строка 51: Строка 55:
  
 
== Обходы графов ==
 
== Обходы графов ==
 +
* [[Теорема Татта о существовании регулярного графа заданного размера с заданным обхватом]]
 
=== Эйлеровы графы ===
 
=== Эйлеровы графы ===
 
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
 
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
Строка 56: Строка 61:
 
* [[Алгоритм построения Эйлерова цикла]]
 
* [[Алгоритм построения Эйлерова цикла]]
 
* [[Произвольно вычерчиваемые из заданной вершины графы]]
 
* [[Произвольно вычерчиваемые из заданной вершины графы]]
 +
* [[Графы де Брюина]]
 
* [[Деревья Эйлерова обхода]]<tex>^\star</tex>
 
* [[Деревья Эйлерова обхода]]<tex>^\star</tex>
  
Строка 92: Строка 98:
 
* [[Формула Уитни]]
 
* [[Формула Уитни]]
 
* [[Теорема Брукса]]
 
* [[Теорема Брукса]]
 +
* [[Хроматическое число планарного графа]]
 
* [[Верхние и нижние оценки хроматического числа]]<tex>^\star</tex>
 
* [[Верхние и нижние оценки хроматического числа]]<tex>^\star</tex>
* [[Хроматическое число планарного графа]]
+
* [[Проблема четырех красок]]<tex>^\star</tex>
 
* [[Многочлен Татта]]<tex>^\star</tex>
 
* [[Многочлен Татта]]<tex>^\star</tex>
 
* [[Теория Рамсея]]<tex>^\star</tex>
 
* [[Теория Рамсея]]<tex>^\star</tex>
 +
* [[Рёберная раскраска двудольного графа]]
 +
* [[Теорема Турана об экстремальном графе]]
 +
* [[Гипотеза Хивуда]]
  
 
== Обход в глубину ==
 
== Обход в глубину ==
Строка 131: Строка 141:
 
* [[Теорема Татта о существовании полного паросочетания]]
 
* [[Теорема Татта о существовании полного паросочетания]]
 
* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]
 
* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]
* [[Декомпозиция Эдмондса-Галлаи]]
+
* [[Декомпозиция Эдмондса-Галлаи | Декомпозиция Эдмондса-Галлаи. Формула Бержа]]
 +
* [[Лапы и минимальные по включению барьеры в графе]]
 +
* [[Пересечение всех максимальных по включению барьеров]]
 
* [[Задача об устойчивом паросочетании]]<tex>^\star</tex>
 
* [[Задача об устойчивом паросочетании]]<tex>^\star</tex>
 
* [[Совершенное паросочетание в кубическом графе]]<tex>^\star</tex>
 
* [[Совершенное паросочетание в кубическом графе]]<tex>^\star</tex>
 +
* [[Теорема о существовании совершенного паросочетания в графе, полученном из регулярного удалением ребёр]]
 +
* [[Теорема Самнера — Лас Вергнаса]]
  
 
== Задача о максимальном потоке ==
 
== Задача о максимальном потоке ==
Строка 154: Строка 168:
 
* [[Теорема о декомпозиционном барьере]]
 
* [[Теорема о декомпозиционном барьере]]
 
* [[Циркуляция потока]]
 
* [[Циркуляция потока]]
 +
* [[Алгоритм Штор-Вагнера нахождения минимального разреза]]
 
* [[Алгоритм Каргера для нахождения минимального разреза]]<tex>^\star</tex>
 
* [[Алгоритм Каргера для нахождения минимального разреза]]<tex>^\star</tex>
 
* [[Примеры сведения к задачам поиска потока]]
 
* [[Примеры сведения к задачам поиска потока]]
Строка 166: Строка 181:
 
* [[Венгерский алгоритм решения задачи о назначениях]]
 
* [[Венгерский алгоритм решения задачи о назначениях]]
 
* [[Алгоритм отмены цикла минимального среднего веса]]<tex>^\star</tex>
 
* [[Алгоритм отмены цикла минимального среднего веса]]<tex>^\star</tex>
 +
 +
== Случайные графы ==
 +
* [[Случайные графы|Введение: определения, наличие треугольников, связность, диаметр два]]
 +
* [[Теорема о гигантской компоненте. Поиск в ширину в случайном графе|Теорема о гигантской компоненте. Поиск в ширину в случайном графе]]
 +
* [[Теорема о существовании порога для монотонных свойств | Теорема о существовании порога для монотонных свойств]]
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Теория графов]]
 
[[Категория: Теория графов]]

Текущая версия на 19:34, 4 сентября 2022

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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