Просмотр исходного текста страницы Дискретная математика3:Тикеты

Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела (например, конспект Матрица Кирхгофа из раздела Остовные деревья имеет тикет 3-1)

= Теория графов =
== 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> [[Произвольно вычерчиваемые из заданной вершины графы]] </li>
</ol>

=== Гамильтоновы графы ===
<ol>
<li value="5"> [[Гамильтоновы графы]] </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''')
## Тут вообще ад какой-то

== 7. Задача о паросочетании ==
# взяли [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]] 0,5
## см также
# [[Теорема Холла]]
# [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
# [[Связь вершинного покрытия и независимого множества]]
# взяли [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]] 0,5
## см также
# взяли [[Теорема Татта о существовании полного паросочетания]] 0,5
## см также
# [[Декомпозиция Эдмондса-Галлаи]]
# [[Задача об устойчивом паросочетании]]

= Матроиды =
== 10 Основные факты теории матроидов ==
# [[Определение матроида]]
# [[Примеры матроидов]]
# взяли [[Прямая сумма матроидов]] 0,25
## Источники информации
# [[Теорема Радо-Эдмондса (жадный алгоритм)]]
# [[Теорема о базах]]
# [[Аксиоматизация матроида базами]]
# взяли [[Теорема о циклах]] 0,25
## См также
# взяли [[Аксиоматизация матроида циклами]] 0,25
## См также
# [[Ранговая функция, полумодулярность]]
# [[Аксиоматизация матроида рангами]]
# [[Двойственный матроид]]
# [[Оператор замыкания для матроидов]]
# [[Покрытия, закрытые множества]]
# взяли [[Матроид Вамоса]]<tex>^\star</tex>
## См также

== 11 Пересечение матроидов ==
# [[Пересечение матроидов, определение, примеры]]
# [[Граф замен]] 
# [[Алгоритм построения базы в пересечении матроидов]]

== 12 Объединение матроидов ==
# [[Объединение матроидов, проверка множества на независимость]]
# взяли [[Объединение матроидов, доказательство того, что объединение является матроидом]] 3
## Добавить категории
## Добавить интервики
## Отформатировать по правилам
## Помёрджить с предыдущим конспектом
## См также
## Источники информации
## Что такое $f$ и $g$ в определении?
# взяли [[Алгоритм построения базы в объединении матроидов]] 7
## В определение само определение выделить жирным
## Добавить категории
## Добавить псевдокод
## Написать более подробное описание алгоритма поиска базы в объединении