748
правок
Изменения
Нет описания правки
= Теория графов =
== 1. Основные определения теории графов ==
# [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
# [[Лемма о рукопожатиях]]
# [[Теорема о существовании простого пути в случае существования пути]]
# [[Теорема о существовании простого цикла в случае существования цикла]]
# [[Матрица смежности графа]]
# [[Матрица инцидентности графа]] (4 ''или больше, зависит от свойств'')
## Добавить свойства матрицы инцидентности с доказательствами
## Источники -> Источники информации
## Добавить про списки смежности и их оформить тоже в таблички
# [[Циклическое пространство графа]]
# [[Фундаментальные циклы графа]]
# [[Дерево, эквивалентные определения]]
# [[Алгоритмы на деревьях]]
# [[Дополнительный, самодополнительный граф]]
# [[Теоретико-множественные операции над графами]]
# [[Рёберное ядро]] (2)
## Добавить больше интервики в конспект
## В конце теоремы в доказательстве какая-то лажа
## Источники информации
## Оформить следствия красиво
# [[Факторизация графов]]
== 2. Связность в графах ==
# [[Отношение связности, компоненты связности]]
# [[Отношение реберной двусвязности]]
# [[Отношение вершинной двусвязности]]
# [[Точка сочленения, эквивалентные определения]]
# [[Мост, эквивалентные определения]]
# [[Граф компонент реберной двусвязности]]
# [[Граф блоков-точек сочленения]]
# [[k-связность]]
# [[Теорема Менгера]]
# [[Теорема Менгера, альтернативное доказательство]]
# [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]] (1.5)
## пункт "Определения" не нужен
## Изменить знаки неравенств в tex
## Не надо дублировать определения из другого конспекта
## Отформатировать псевдокод
## find_flow какой-то стрёмный
## Источники информации
## k-связность с маленькой буквы
## Добавить См. также на что-нибудь разумное
## Добавить см. также
== 3. Остовные деревья ==
=== Свойства остовных деревьев ===
<ol>
<li>[[Матрица Кирхгофа]]</li>
<li> [[Связь матрицы Кирхгофа и матрицы инцидентности]] </li>
<li> [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]] </li>
<li> [[Количество помеченных деревьев]] </li>
<li> [[Коды Прюфера]] </li>
</ol>
== 4. Обходы графов ==
=== Эйлеровы графы ===
<ol>
<li value="1"> [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]</li>
<li> [[Покрытие ребер графа путями]] (3)</li>
# Какое-то мутное доказательства
<li> [[Алгоритм построения Эйлерова цикла]] (2) </li>
# Какое-то мутное доказательство леммы про корректность алгоритма
<li> [[Произвольно вычерчиваемые из заданной вершины графы]] </li>
</ol>
=== Гамильтоновы графы ===
<ol>
<li value="5"> [[Гамильтоновы графы]] </li>
<li> [[Теорема Хватала]] </li>
<li> [[Теорема Дирака]] </li>
<li> [[Теорема Оре]] </li>
<li> [[Теорема Поша]]</li>
<li> [[Теорема Гуйя-Ури]] </li>
<li> [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]] </li>
<li> '''!!!''' [[Теорема Гринберга]] (5) </li>
# Пояснить переходы в теореме
# Внести пояснение в определение бонда
# И зачем нужно доказывать отсутствие гамильтонова бонда в графе?
# Картинку сделать красивой
<li> [[Турниры]] </li>
<li> [[Теорема Редеи-Камиона]] </li>
</ol>
== 5. Укладки графов ==
# [[Укладка графа на плоскости]]
# [[Формула Эйлера]]
# [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]]
# [[Укладка дерева]]
# [[Укладка графа с планарными компонентами реберной двусвязности]]
# [[Укладка графа с планарными компонентами вершинной двусвязности]]
# [[Теорема Понтрягина-Куратовского]]
# [[Род, толщина, крупность, число скрещиваний]]
# [[Двойственный граф планарного графа]]
# [[Теорема Фари]]
# [[Гамма-алгоритм]]
== 6. Раскраски графов ==
# [[Раскраска графа]]
# [[Двудольные графы и раскраска в 2 цвета]]
# [[Хроматический многочлен]]
# [[Формула Зыкова]]
# [[Формула Уитни]]
# [[Теорема Брукса]]
# [[Верхние и нижние оценки хроматического числа]]
# [[Хроматическое число планарного графа]]
# [[Многочлен Татта]]
# [[Теория Рамсея]] ('''10''')
## Тут вообще ад какой-то
== 9. Задача о паросочетании ==
# [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]]
# [[Теорема Холла]]
# [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
# [[Связь вершинного покрытия и независимого множества]]
# [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
# [[Теорема Татта о существовании полного паросочетания]]
# [[Декомпозиция Эдмондса-Галлаи]]
# [[Задача об устойчивом паросочетании]] (5)
## паросочетание в интервики
## пару оформить нормально
## Зачем-то списки в доказательствах лемм использованы
## Надо бы доказать все леммы
= Матроиды =
== 1 Основные факты теории матроидов ==
