Изменения

Теория графов

642 байта добавлено, 14:16, 14 июня 2021

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

* [[Рёберная раскраска двудольного графа]]

* [[Теорема Турана об экстремальном графе]]

* [[Гипотеза Хивуда]]

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

* [[Теорема Татта о существовании полного паросочетания]]

* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]

* [[Декомпозиция Эдмондса-Галлаи| Декомпозиция Эдмондса-Галлаи. Формула Бержа]]

* [[Лапы и минимальные по включению барьеры в графе]]

* [[Пересечение всех максимальных по включению барьеров]]

* [[Совершенное паросочетание в кубическом графе]]<tex>^\star</tex>

* [[Теорема о существовании совершенного паросочетания в графе, полученном из регулярного удалением ребёр]]

* [[Теорема Самнера — Лас Вергнаса]]

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

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

* [[Случайные графы|Введение: определения, наличие треугольников, связность, диаметр два]]

* [[Теорема о гигантской компоненте. Поиск в ширину в случайном графе|Теорема о гигантской компоненте. Поиск в ширину в случайном графе]]

* [[Теорема о существовании порога для монотонных свойств | Теорема о существовании порога для монотонных свойств]]

[[Категория: Алгоритмы и структуры данных]]

[[Категория: Теория графов]]

Анонимный участник