Дискретная математика3:Тикеты — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «= Матроиды = == 1 Основные факты теории матроидов == # Определение матроида # [[Примеры матр...»)
 
м (rollbackEdits.php mass rollback)
 
(не показаны 22 промежуточные версии 4 участников)
Строка 1: Строка 1:
 +
Тикеты индексируются как "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
 +
## см также
 +
# [[Декомпозиция Эдмондса-Галлаи]]
 +
# [[Задача об устойчивом паросочетании]]
 +
 
= Матроиды =
 
= Матроиды =
−
== 1 Основные факты теории матроидов ==
+
== 8 Основные факты теории матроидов ==
 
# [[Определение матроида]]
 
# [[Определение матроида]]
 
# [[Примеры матроидов]]
 
# [[Примеры матроидов]]
−
# [[Прямая сумма матроидов]] 0,25
+
# взяли [[Прямая сумма матроидов]] 0,25
 
## Источники информации
 
## Источники информации
 
# [[Теорема Радо-Эдмондса (жадный алгоритм)]]
 
# [[Теорема Радо-Эдмондса (жадный алгоритм)]]
 
# [[Теорема о базах]]
 
# [[Теорема о базах]]
 
# [[Аксиоматизация матроида базами]]
 
# [[Аксиоматизация матроида базами]]
−
# [[Теорема о циклах]] 0,25
+
# взяли [[Теорема о циклах]] 0,25
 
## См также
 
## См также
−
# [[Аксиоматизация матроида циклами]] 0,25
+
# взяли [[Аксиоматизация матроида циклами]] 0,25
 
## См также
 
## См также
 
# [[Ранговая функция, полумодулярность]]
 
# [[Ранговая функция, полумодулярность]]
Строка 17: Строка 141:
 
# [[Оператор замыкания для матроидов]]
 
# [[Оператор замыкания для матроидов]]
 
# [[Покрытия, закрытые множества]]
 
# [[Покрытия, закрытые множества]]
−
# [[Матроид Вамоса]]<tex>^\star</tex>
+
# взяли [[Матроид Вамоса]]<tex>^\star</tex>
 
## См также
 
## См также
  
−
== 2 Пересечение матроидов ==
+
== 9 Пересечение матроидов ==
 
# [[Пересечение матроидов, определение, примеры]]
 
# [[Пересечение матроидов, определение, примеры]]
 
# [[Граф замен]]  
 
# [[Граф замен]]  
 
# [[Алгоритм построения базы в пересечении матроидов]]
 
# [[Алгоритм построения базы в пересечении матроидов]]
  
−
== 3 Объединение матроидов ==
+
== 10 Объединение матроидов ==
 
# [[Объединение матроидов, проверка множества на независимость]]
 
# [[Объединение матроидов, проверка множества на независимость]]
−
# [[Объединение матроидов, доказательство того, что объединение является матроидом]] 1
+
# взяли [[Объединение матроидов, доказательство того, что объединение является матроидом]] 3
 
## Добавить категории
 
## Добавить категории
 
## Добавить интервики
 
## Добавить интервики
Строка 34: Строка 158:
 
## См также
 
## См также
 
## Источники информации
 
## Источники информации
−
# [[Алгоритм построения базы в объединении матроидов]] 7
+
## Что такое $f$ и $g$ в определении?
 +
# взяли [[Алгоритм построения базы в объединении матроидов]] 7
 
## В определение само определение выделить жирным
 
## В определение само определение выделить жирным
 
## Добавить категории
 
## Добавить категории
 
## Добавить псевдокод
 
## Добавить псевдокод
 
## Написать более подробное описание алгоритма поиска базы в объединении
 
## Написать более подробное описание алгоритма поиска базы в объединении

Текущая версия на 19:11, 4 сентября 2022

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

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

1. Основные определения теории графов

  1. Основные определения: граф, ребро, вершина, степень, петля, путь, цикл
  2. Лемма о рукопожатиях
  3. Теорема о существовании простого пути в случае существования пути
  4. Теорема о существовании простого цикла в случае существования цикла
  5. Матрица смежности графа
  6. Матрица инцидентности графа (4 или больше, зависит от свойств)
    1. Добавить свойства матрицы инцидентности с доказательствами
    2. Источники -> Источники информации
    3. Добавить про списки смежности и их оформить тоже в таблички
  7. Циклическое пространство графа
  8. Фундаментальные циклы графа
  9. Дерево, эквивалентные определения
  10. Алгоритмы на деревьях
  11. Дополнительный, самодополнительный граф
  12. Теоретико-множественные операции над графами
  13. Рёберное ядро (2)
    1. Добавить больше интервики в конспект
    2. В конце теоремы в доказательстве какая-то лажа
    3. Источники информации
    4. Оформить следствия красиво
  14. Факторизация графов

2. Связность в графах

  1. Отношение связности, компоненты связности
  2. Отношение реберной двусвязности
  3. Отношение вершинной двусвязности
  4. Точка сочленения, эквивалентные определения
  5. Мост, эквивалентные определения
  6. Граф компонент реберной двусвязности
  7. Граф блоков-точек сочленения
  8. k-связность
  9. Теорема Менгера
  10. Теорема Менгера, альтернативное доказательство
  11. Вершинная, реберная связность, связь между ними и минимальной степенью вершины (1.5)
    1. пункт "Определения" не нужен
    2. Изменить знаки неравенств в tex
    3. Не надо дублировать определения из другого конспекта
    4. Отформатировать псевдокод
    5. find_flow какой-то стрёмный
    6. Источники информации
    7. k-связность с маленькой буквы
    8. Добавить См. также на что-нибудь разумное

3. Остовные деревья

Свойства остовных деревьев

  1. Матрица Кирхгофа
  2. Связь матрицы Кирхгофа и матрицы инцидентности
  3. Подсчет числа остовных деревьев с помощью матрицы Кирхгофа
  4. Количество помеченных деревьев
  5. Коды Прюфера


4. Обходы графов

Эйлеровы графы

  1. Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов
  2. взяли Покрытие ребер графа путями (3)
    1. Какое-то мутное доказательства
  3. Произвольно вычерчиваемые из заданной вершины графы

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

  1. Гамильтоновы графы
  2. Теорема Хватала
  3. Теорема Дирака
  4. Теорема Оре
  5. Теорема Поша
  6. Теорема Гуйя-Ури
  7. взяли Теорема Гринберга (5)
    1. Пояснить переходы в теореме
    2. Внести пояснение в определение бонда
    3. И зачем нужно доказывать отсутствие гамильтонова бонда в графе?
    4. Картинку сделать красивой
  8. Турниры
  9. Теорема Редеи-Камиона

5. Укладки графов

  1. Укладка графа на плоскости
  2. Формула Эйлера
  3. Непланарность [math]K_5[/math] и [math]K_{3,3}[/math]
  4. Укладка дерева
  5. Укладка графа с планарными компонентами реберной двусвязности
  6. Укладка графа с планарными компонентами вершинной двусвязности
  7. Теорема Понтрягина-Куратовского
  8. Род, толщина, крупность, число скрещиваний
  9. Двойственный граф планарного графа
  10. Теорема Фари
  11. Гамма-алгоритм


6. Раскраски графов

  1. Раскраска графа
  2. Двудольные графы и раскраска в 2 цвета
  3. Хроматический многочлен
  4. Формула Зыкова
  5. Формула Уитни
  6. Теорема Брукса
  7. Верхние и нижние оценки хроматического числа
  8. Хроматическое число планарного графа
  9. Многочлен Татта
  10. Теория Рамсея (10)
    1. Тут вообще ад какой-то

7. Задача о паросочетании

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

Матроиды

8 Основные факты теории матроидов

  1. Определение матроида
  2. Примеры матроидов
  3. взяли Прямая сумма матроидов 0,25
    1. Источники информации
  4. Теорема Радо-Эдмондса (жадный алгоритм)
  5. Теорема о базах
  6. Аксиоматизация матроида базами
  7. взяли Теорема о циклах 0,25
    1. См также
  8. взяли Аксиоматизация матроида циклами 0,25
    1. См также
  9. Ранговая функция, полумодулярность
  10. Аксиоматизация матроида рангами
  11. Двойственный матроид
  12. Оператор замыкания для матроидов
  13. Покрытия, закрытые множества
  14. взяли Матроид Вамоса[math]^\star[/math]
    1. См также

9 Пересечение матроидов

  1. Пересечение матроидов, определение, примеры
  2. Граф замен
  3. Алгоритм построения базы в пересечении матроидов

10 Объединение матроидов

  1. Объединение матроидов, проверка множества на независимость
  2. взяли Объединение матроидов, доказательство того, что объединение является матроидом 3
    1. Добавить категории
    2. Добавить интервики
    3. Отформатировать по правилам
    4. Помёрджить с предыдущим конспектом
    5. См также
    6. Источники информации
    7. Что такое $f$ и $g$ в определении?
  3. взяли Алгоритм построения базы в объединении матроидов 7
    1. В определение само определение выделить жирным
    2. Добавить категории
    3. Добавить псевдокод
    4. Написать более подробное описание алгоритма поиска базы в объединении
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Дискретная_математика3:Тикеты&oldid=84578»