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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Задача о паросочетании)
(Метки: правка с мобильного устройства, правка из мобильной версии)
 
(не показаны 4 промежуточные версии 4 участников)
Строка 105: Строка 105:
 
* [[Рёберная раскраска двудольного графа]]
 
* [[Рёберная раскраска двудольного графа]]
 
* [[Теорема Турана об экстремальном графе]]
 
* [[Теорема Турана об экстремальном графе]]
 +
* [[Гипотеза Хивуда]]
  
 
== Обход в глубину ==
 
== Обход в глубину ==
Строка 140: Строка 141:
 
* [[Теорема Татта о существовании полного паросочетания]]
 
* [[Теорема Татта о существовании полного паросочетания]]
 
* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]
 
* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]
* [[Декомпозиция Эдмондса-Галлаи]]
+
* [[Декомпозиция Эдмондса-Галлаи | Декомпозиция Эдмондса-Галлаи. Формула Бержа]]
 
* [[Лапы и минимальные по включению барьеры в графе]]
 
* [[Лапы и минимальные по включению барьеры в графе]]
 
* [[Пересечение всех максимальных по включению барьеров]]
 
* [[Пересечение всех максимальных по включению барьеров]]
Строка 146: Строка 147:
 
* [[Совершенное паросочетание в кубическом графе]]<tex>^\star</tex>
 
* [[Совершенное паросочетание в кубическом графе]]<tex>^\star</tex>
 
* [[Теорема о существовании совершенного паросочетания в графе, полученном из регулярного удалением ребёр]]
 
* [[Теорема о существовании совершенного паросочетания в графе, полученном из регулярного удалением ребёр]]
 +
* [[Теорема Самнера — Лас Вергнаса]]
  
 
== Задача о максимальном потоке ==
 
== Задача о максимальном потоке ==
Строка 182: Строка 184:
 
== Случайные графы ==
 
== Случайные графы ==
 
* [[Случайные графы|Введение: определения, наличие треугольников, связность, диаметр два]]
 
* [[Случайные графы|Введение: определения, наличие треугольников, связность, диаметр два]]
 +
* [[Теорема о гигантской компоненте. Поиск в ширину в случайном графе|Теорема о гигантской компоненте. Поиск в ширину в случайном графе]]
 +
* [[Теорема о существовании порога для монотонных свойств | Теорема о существовании порога для монотонных свойств]]
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Теория графов]]
 
[[Категория: Теория графов]]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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