Дискретная математика3:Тикеты
Версия от 19:11, 4 сентября 2022; Maintenance script (обсуждение | вклад) (rollbackEdits.php mass rollback)
Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела (например, конспект Матрица Кирхгофа из раздела Остовные деревья имеет тикет 3-1)
Теория графов
1. Основные определения теории графов
- Основные определения: граф, ребро, вершина, степень, петля, путь, цикл
- Лемма о рукопожатиях
- Теорема о существовании простого пути в случае существования пути
- Теорема о существовании простого цикла в случае существования цикла
- Матрица смежности графа
- Матрица инцидентности графа (4 или больше, зависит от свойств)
- Добавить свойства матрицы инцидентности с доказательствами
- Источники -> Источники информации
- Добавить про списки смежности и их оформить тоже в таблички
- Циклическое пространство графа
- Фундаментальные циклы графа
- Дерево, эквивалентные определения
- Алгоритмы на деревьях
- Дополнительный, самодополнительный граф
- Теоретико-множественные операции над графами
- Рёберное ядро (2)
- Добавить больше интервики в конспект
- В конце теоремы в доказательстве какая-то лажа
- Источники информации
- Оформить следствия красиво
- Факторизация графов
2. Связность в графах
- Отношение связности, компоненты связности
- Отношение реберной двусвязности
- Отношение вершинной двусвязности
- Точка сочленения, эквивалентные определения
- Мост, эквивалентные определения
- Граф компонент реберной двусвязности
- Граф блоков-точек сочленения
- k-связность
- Теорема Менгера
- Теорема Менгера, альтернативное доказательство
- Вершинная, реберная связность, связь между ними и минимальной степенью вершины (1.5)
- пункт "Определения" не нужен
- Изменить знаки неравенств в tex
- Не надо дублировать определения из другого конспекта
- Отформатировать псевдокод
- find_flow какой-то стрёмный
- Источники информации
- k-связность с маленькой буквы
- Добавить См. также на что-нибудь разумное
3. Остовные деревья
Свойства остовных деревьев
- Матрица Кирхгофа
- Связь матрицы Кирхгофа и матрицы инцидентности
- Подсчет числа остовных деревьев с помощью матрицы Кирхгофа
- Количество помеченных деревьев
- Коды Прюфера
4. Обходы графов
Эйлеровы графы
- Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов
- взяли Покрытие ребер графа путями (3)
- Какое-то мутное доказательства
- Произвольно вычерчиваемые из заданной вершины графы
Гамильтоновы графы
- Гамильтоновы графы
- Теорема Хватала
- Теорема Дирака
- Теорема Оре
- Теорема Поша
- Теорема Гуйя-Ури
- взяли Теорема Гринберга (5)
- Пояснить переходы в теореме
- Внести пояснение в определение бонда
- И зачем нужно доказывать отсутствие гамильтонова бонда в графе?
- Картинку сделать красивой
- Турниры
- Теорема Редеи-Камиона
5. Укладки графов
- Укладка графа на плоскости
- Формула Эйлера
- Непланарность и
- Укладка дерева
- Укладка графа с планарными компонентами реберной двусвязности
- Укладка графа с планарными компонентами вершинной двусвязности
- Теорема Понтрягина-Куратовского
- Род, толщина, крупность, число скрещиваний
- Двойственный граф планарного графа
- Теорема Фари
- Гамма-алгоритм
6. Раскраски графов
- Раскраска графа
- Двудольные графы и раскраска в 2 цвета
- Хроматический многочлен
- Формула Зыкова
- Формула Уитни
- Теорема Брукса
- Верхние и нижние оценки хроматического числа
- Хроматическое число планарного графа
- Многочлен Татта
- Теория Рамсея (10)
- Тут вообще ад какой-то
7. Задача о паросочетании
- взяли Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях 0,5
- см также
- Теорема Холла
- Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах
- Связь вершинного покрытия и независимого множества
- взяли Матрица Татта и связь с размером максимального паросочетания в двудольном графе 0,5
- см также
- взяли Теорема Татта о существовании полного паросочетания 0,5
- см также
- Декомпозиция Эдмондса-Галлаи
- Задача об устойчивом паросочетании
Матроиды
8 Основные факты теории матроидов
- Определение матроида
- Примеры матроидов
- взяли Прямая сумма матроидов 0,25
- Источники информации
- Теорема Радо-Эдмондса (жадный алгоритм)
- Теорема о базах
- Аксиоматизация матроида базами
- взяли Теорема о циклах 0,25
- См также
- взяли Аксиоматизация матроида циклами 0,25
- См также
- Ранговая функция, полумодулярность
- Аксиоматизация матроида рангами
- Двойственный матроид
- Оператор замыкания для матроидов
- Покрытия, закрытые множества
- взяли Матроид Вамоса
- См также
9 Пересечение матроидов
- Пересечение матроидов, определение, примеры
- Граф замен
- Алгоритм построения базы в пересечении матроидов
10 Объединение матроидов
- Объединение матроидов, проверка множества на независимость
- взяли Объединение матроидов, доказательство того, что объединение является матроидом 3
- Добавить категории
- Добавить интервики
- Отформатировать по правилам
- Помёрджить с предыдущим конспектом
- См также
- Источники информации
- Что такое $f$ и $g$ в определении?
- взяли Алгоритм построения базы в объединении матроидов 7
- В определение само определение выделить жирным
- Добавить категории
- Добавить псевдокод
- Написать более подробное описание алгоритма поиска базы в объединении