Изменения

Перейти к: навигация, поиск

Дискретная математика3:Тикеты

29 байт убрано, 15:15, 7 декабря 2018
10 Объединение матроидов
# [[Теорема о существовании простого цикла в случае существования цикла]]
# [[Матрица смежности графа]]
# '''взяли''' [[Матрица инцидентности графа]] (4 ''или больше, зависит от свойств'')
## Добавить свойства матрицы инцидентности с доказательствами
## Источники -> Источники информации
<ol>
<li value="1"> [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]</li>
<li> взяли [[Покрытие ребер графа путями]] (3)</li>
# Какое-то мутное доказательства
<li> [[Произвольно вычерчиваемые из заданной вершины графы]] </li>
<li> [[Теорема Поша]]</li>
<li> [[Теорема Гуйя-Ури]] </li>
<li> '''!!!взяли''' [[Теорема Гринберга]] (5) </li>
# Пояснить переходы в теореме
# Внести пояснение в определение бонда
== 7. Задача о паросочетании ==
# взяли [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]] 0,5## см также
# [[Теорема Холла]]
# [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
# [[Связь вершинного покрытия и независимого множества]]
# взяли [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]0,5# # см также# взяли [[Теорема Татта о существовании полного паросочетания]]0,5## см также
# [[Декомпозиция Эдмондса-Галлаи]]
# [[Задача об устойчивом паросочетании]] (5)## паросочетание в интервики## пару оформить нормально## Зачем-то списки в доказательствах лемм использованы## Надо бы доказать все леммы
= Матроиды =
# [[Определение матроида]]
# [[Примеры матроидов]]
# взяли [[Прямая сумма матроидов]] 0,25
## Источники информации
# [[Теорема Радо-Эдмондса (жадный алгоритм)]]
# [[Теорема о базах]]
# [[Аксиоматизация матроида базами]]
# взяли [[Теорема о циклах]] 0,25
## См также
# взяли [[Аксиоматизация матроида циклами]] 0,25
## См также
# [[Ранговая функция, полумодулярность]]
# [[Оператор замыкания для матроидов]]
# [[Покрытия, закрытые множества]]
# взяли [[Матроид Вамоса]]<tex>^\star</tex>
## См также
== 10 Объединение матроидов ==
# [[Объединение матроидов, проверка множества на независимость]]
# взяли [[Объединение матроидов, доказательство того, что объединение является матроидом]] 13
## Добавить категории
## Добавить интервики
## См также
## Источники информации
# # Что такое $f$ и $g$ в определении?# взяли [[Алгоритм построения базы в объединении матроидов]] 7
## В определение само определение выделить жирным
## Добавить категории
## Добавить псевдокод
## Написать более подробное описание алгоритма поиска базы в объединении

Навигация