Участник:Dgerasimov/Тикеты по конспектам year2012 — различия между версиями
(Новая страница: «Тикеты нумеруются как "X-Y", где X — номер темы, а Y — номер тикета внутри темы. == 1. Основные ...») |
(→1. Основные определения теории графов) |
||
Строка 3: | Строка 3: | ||
== 1. Основные определения теории графов == | == 1. Основные определения теории графов == | ||
# [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]] | # [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]] | ||
+ | ## moar англоязычных терминов | ||
+ | ## "Мультиграф с петлями принято называть псевдографом. " — при этом понятие мультиграфа встречается позже. Нехорошо, разобраться все же с правильными порядком и правильными определениями | ||
+ | ## Из определения орграфа с beg и end никак не следует, что там не может быть петель (кто мешает сделать beg e = v, end e = v?). | ||
+ | ## "некоторые абстрактные множества." — а что такое неабстрактные множества? | ||
+ | ## "V — конечное множество вершин" — при этом далее в каком-то конспекте есть пример для бесконечного графа. Не надо заставлять граф быть конечным, лучше написать отдельно, что называется конечным графом. | ||
+ | ## запись "<tex> E \subset V \times V(uv \sim vu~\backslash~\{uu~|~u \in V\})</tex>" я вообще не очень понимаю. Если вы понимаете, объясните мне, иначе напишите нормально :) | ||
+ | ## альтернативное определение неориентированного графа мне не нравится, потому что прямо перед ним мы говорим, что ребро — неупорядоченная пара, а потом внезапно <tex>ends : E \rightarrow V \times V</tex>, а декартово произведение у нас еще как упорядочено. | ||
# [[Лемма о рукопожатиях]] | # [[Лемма о рукопожатиях]] | ||
# [[Теорема о существовании простого пути в случае существования пути]] | # [[Теорема о существовании простого пути в случае существования пути]] | ||
+ | ## перенести определения в "Основные определения" | ||
+ | ## форматирование в некоторых местах какое-то упоротое, думаю, это видно. | ||
# [[Теорема о существовании простого цикла в случае существования цикла]] | # [[Теорема о существовании простого цикла в случае существования цикла]] | ||
+ | ## добавить интервики | ||
+ | ## форматирование в некоторых местах какое-то упоротое | ||
# [[Матрица смежности графа]] | # [[Матрица смежности графа]] | ||
+ | ## "Для графов без петель и кратных рёбер матрица смежности бинарна (состоит из нулей и единиц), причём её главная диагональ целиком состоит из нулей. " — зачем объединять эти свойства, можно разнести на два. | ||
# [[Связь степени матрицы смежности и количества путей]] | # [[Связь степени матрицы смежности и количества путей]] | ||
# [[Матрица инцидентности графа]] | # [[Матрица инцидентности графа]] | ||
+ | ## Определение инцидентности вроде есть в "Основных определениях", если нет — перенести его туда | ||
# [[Циклическое пространство графа]] | # [[Циклическое пространство графа]] | ||
+ | ## Пункт "Определение" не нужен, см. правила форматирования | ||
+ | ## Ker, dim, Rang надо запихать в \operatorname, а также кинуть ссылку на определение ядра оператора (в матане/функате на конспектах точно есть) | ||
+ | ## интервики | ||
+ | ## "Литература (формулировки другие) " — "формулировки другие" относится к конкретному источнику, а не ко всей литературе. | ||
# [[Фундаментальные циклы графа]] | # [[Фундаментальные циклы графа]] | ||
+ | |||
# [[Дерево, эквивалентные определения]] | # [[Дерево, эквивалентные определения]] | ||
# [[Дополнительный, самодополнительный граф]] | # [[Дополнительный, самодополнительный граф]] |
Версия 22:14, 16 октября 2013
Тикеты нумеруются как "X-Y", где X — номер темы, а Y — номер тикета внутри темы.
Содержание
- 1 1. Основные определения теории графов
- 2 2. Связность в графах
- 3 3. Остовные деревья
- 4 4. Обходы графов
- 5 5. Укладки графов
- 6 6. Раскраски графов
- 7 7. Обход в глубину
- 8 8. Кратчайшие пути в графах
- 9 9. Построение остовных деревьев
- 10 10. Задача о паросочетании
- 11 11. Задача о максимальном потоке
- 12 12. Задача о потоке минимальной стоимости
1. Основные определения теории графов
- Основные определения: граф, ребро, вершина, степень, петля, путь, цикл
- moar англоязычных терминов
- "Мультиграф с петлями принято называть псевдографом. " — при этом понятие мультиграфа встречается позже. Нехорошо, разобраться все же с правильными порядком и правильными определениями
- Из определения орграфа с beg и end никак не следует, что там не может быть петель (кто мешает сделать beg e = v, end e = v?).
- "некоторые абстрактные множества." — а что такое неабстрактные множества?
- "V — конечное множество вершин" — при этом далее в каком-то конспекте есть пример для бесконечного графа. Не надо заставлять граф быть конечным, лучше написать отдельно, что называется конечным графом.
- запись " " я вообще не очень понимаю. Если вы понимаете, объясните мне, иначе напишите нормально :)
- альтернативное определение неориентированного графа мне не нравится, потому что прямо перед ним мы говорим, что ребро — неупорядоченная пара, а потом внезапно , а декартово произведение у нас еще как упорядочено.
- Лемма о рукопожатиях
- Теорема о существовании простого пути в случае существования пути
- перенести определения в "Основные определения"
- форматирование в некоторых местах какое-то упоротое, думаю, это видно.
- Теорема о существовании простого цикла в случае существования цикла
- добавить интервики
- форматирование в некоторых местах какое-то упоротое
- Матрица смежности графа
- "Для графов без петель и кратных рёбер матрица смежности бинарна (состоит из нулей и единиц), причём её главная диагональ целиком состоит из нулей. " — зачем объединять эти свойства, можно разнести на два.
- Связь степени матрицы смежности и количества путей
- Матрица инцидентности графа
- Определение инцидентности вроде есть в "Основных определениях", если нет — перенести его туда
- Циклическое пространство графа
- Пункт "Определение" не нужен, см. правила форматирования
- Ker, dim, Rang надо запихать в \operatorname, а также кинуть ссылку на определение ядра оператора (в матане/функате на конспектах точно есть)
- интервики
- "Литература (формулировки другие) " — "формулировки другие" относится к конкретному источнику, а не ко всей литературе.
- Фундаментальные циклы графа
2. Связность в графах
- Отношение связности, компоненты связности
- Отношение реберной двусвязности
- Отношение вершинной двусвязности
- Граф компонент реберной двусвязности
- Граф блоков-точек сочленения
- Точка сочленения, эквивалентные определения
- Мост, эквивалентные определения
- k-связность
- Теорема Менгера
- Теорема Менгера, альтернативное доказательство
- Вершинная, реберная связность, связь между ними и минимальной степенью вершины
3. Остовные деревья
- Матрица Кирхгофа
- Связь матрицы Кирхгофа и матрицы инцидентности
- Подсчет числа остовных деревьев с помощью матрицы Кирхгофа
- Количество помеченных деревьев
- Коды Прюфера
4. Обходы графов
- Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов
- Покрытие ребер графа путями
- Алгоритм построения Эйлерова цикла
- Произвольно вычерчиваемые из заданной вершины графы
- Гамильтоновы графы
- Теорема Хватала
- Теорема Дирака
- Теорема Оре
- Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре
- Турниры
- Теорема Редеи-Камиона
5. Укладки графов
- Укладка графа на плоскости
- Формула Эйлера
- Непланарность и
- Укладка дерева
- Укладка графа с планарными компонентами реберной двусвязности
- Укладка графа с планарными компонентами вершинной двусвязности
- Теорема Понтрягина-Куратовского
- Двойственный граф планарного графа
6. Раскраски графов
- Раскраска графа
- Двудольные графы и раскраска в 2 цвета
- Хроматический многочлен
- Формула Зыкова
- Формула Уитни
- Теорема Брукса
- Верхние и нижние оценки хроматического числа
7. Обход в глубину
- Обход в глубину, цвета вершин
- Лемма о белых путях
- Использование обхода в глубину для проверки связности
- Использование обхода в глубину для поиска цикла в ориентированном графе
- Использование обхода в глубину для топологической сортировки
- Использование обхода в глубину для поиска компонент сильной связности
- Использование обхода в глубину для поиска точек сочленения
- Построение компонент вершинной двусвязности
- Использование обхода в глубину для поиска мостов
- Построение компонент реберной двусвязности
8. Кратчайшие пути в графах
- Обход в ширину
- Алгоритм Форда-Беллмана
- Алгоритм Дейкстры
- Алгоритм Флойда
- Алгоритм A*
- Алгоритм Джонсона
9. Построение остовных деревьев
- Лемма о безопасном ребре
- Алгоритм Прима
- Алгоритм Краскала
- Алгоритм Борувки
- Теорема Тарьяна (критерий минимальности остовного дерева)
- Алгоритм двух китайцев
10. Задача о паросочетании
- Теорема о максимальном паросочетании и дополняющих цепях
- Алгоритм Форда-Фалкерсона для поиска максимального паросочетания
- Алгоритм Куна для поиска максимального паросочетания
- Теорема Холла
- Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах
- Связь вершинного покрытия и независимого множества
- Матрица Татта и связь с размером максимального паросочетания в двудольном графе
- Паросочетания в недвудольных графах. Алгоритм вырезания соцветий
11. Задача о максимальном потоке
- Определение сети, потока
- Разрез, лемма о потоке через разрез
- Дополняющая сеть, дополняющий путь
- Лемма о сложении потоков
- Теорема Форда-Фалкерсона
- Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину
- Алоритм Эдмондса-Карпа
- Алгоритм масштабирования потока
- Блокирующий поток
- Схема алгоритма Диница
- Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями
- Алгоритм поиска блокирующего потока в ациклической сети
- Метод проталкивания предпотока
- Алгоритм "поднять-в-начало"
- Теорема о декомпозиции
- Теорема о декомпозиционном барьере
- Циркуляция потока
- Алгоритм Каргера для нахождения минимального разреза
12. Задача о потоке минимальной стоимости
- Поток минимальной стоимости
- Теорема Форда-Фалкерсона о потоке минимальной стоимости
- Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети
- Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости
- Использование потенциалов Джонсона при поиске потока минимальной стоимости
- Сведение задачи о назначениях к задаче о потоке минимальной стоимости
- Венгерский алгоритм решения задачи о назначениях