Изменения

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

Участник:Shersh/Тикеты к 3ему терму

27 733 байта убрано, 19:15, 23 февраля 2017
м
Изменён уровень защиты страницы «Участник:Shersh/Тикеты к 3ему терму» ([edit=autoconfirmed] (бессрочно) [move=autoconfirmed] (бессрочно))
== 1. Основные определения теории графов ==
# [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
# ''fixed'' [[Лемма о рукопожатиях]] (1)## Увеличить дроби## Взять константы в tex## Заменить умножение на \cdot## Добавить пару слов о графах с петлями и кратными рёбрами## Заменить источники на источники информации# ''взялиfixed'' [[Теорема о существовании простого пути в случае существования пути]] (4)
## Алгоритм и предположение зря оформлены как псевдокод
## Добавить ссылок
## Добавить в формулировку теоремы, что вершинно-простой путь
# [[Теорема о существовании простого цикла в случае существования цикла]]
# ''fixed'' [[Матрица смежности графа]] (3) ''вместе со следующим''## "Для графов без петель и кратных рёбер матрица смежности бинарна (состоит из нулей и единиц), причём её главная диагональ целиком состоит из нулей. " — зачем объединять эти свойства, можно разнести на два## Что за помеченный граф?## Добавить про что, в матрице смежности можно хранить веса рёбер## Оформить правильно источники информации## Добавить оценку на память матрицы смежности и привести примеры, когда эффективно её использовать, а когда нет# ''взяли'' [[Связь степени матрицы смежности и количества путей]] ''вместе с предыдущим''## Это можно внести в прошлый конспект## Добавить что-нибудь про бинарное возведение в степень
# ''взяли'' [[Матрица инцидентности графа]] (4 ''или больше, зависит от свойств'')
## Добавить свойства матрицы инцидентности с доказательствами
## Добавить про списки смежности и их оформить тоже в таблички
# [[Циклическое пространство графа]]
# ''взялиfixed'' [[Фундаментальные циклы графа]] (0.51)
## Источники информации нормально оформить
## Подписать получше картинку
## Заменить многоточия на \ldots
## Отформатировать по правилам# ''взялиfixed'' [[Дерево, эквивалентные определения]] (0.51)
## Англоязычные термины
## Пофиксить знаки неравенств
## Источники информации нормально оформить
## Оформить красиво доказательства
# [[Алгоритмы на деревьях]]
# ''взялиfixed'' [[Дополнительный, самодополнительный граф]] (1)
## Англоязычные термины оформить правильно
## Заменить угловые скобки на \langle и \rangle
## Шаблоном заменить тире
# [[Теоретико-множественные операции над графами]]
# [[Рёберное ядро]] (2)
## Добавить больше интервики в конспект
## В конце теоремы в доказательстве какая-то лажа
## Источники информации
## Оформить следствия красиво
# [[Факторизация графов]]
== 2. Связность в графах ==
# ''fixed'' [[Отношение связности, компоненты связности]] (0.5)## англоязычные термины## интервики## Заменить тире на шаблон## Добавить См. также# ''fixed'' [[Отношение реберной двусвязности]] (0.5)## англоязычные термины## Оформить правильно источники информации## Перенести из См. также визуализатор в источники информации# ''взяли'' [[Отношение вершинной двусвязности]] (0.5)## англоязычные термины## Добавить ссылок## Оформить правильно источники информации# ''взяли'' [[Точка сочленения, эквивалентные определения]] (0.5)## Англоязычные термины## Цифры в начале определений не нужны, их можно в хедер определения## Оформить пункты в теореме маркированным списком через ### Источники информации# [[Мост, эквивалентные определения]] (0.5)## См. выше# [[Граф компонент реберной двусвязности]] (0.5)## Нормально оформить источники информации и см. также## Англоязычные термины## Избавить от a) и б) в доказательстве# [[Граф блоков-точек сочленения]] (0.5)## См. выше## Капс какой-то зачем-то# ''взяли'' [[k-связность]] (0.5)## англоязычные термины## Тире заменить на шаблон## Дефисы в определениях ровно поставить## Палку вертикальную в множестве заменить на \mid## Странное обозначение {{---}} \smallsetminus## Источники информации# ''взялиfixed'' [[Теорема Менгера]] (0.5)
## убрать кванторы там, где они не нужны (в формулировках теорем) и заменить словами
## Тире заменить на шаблон
## Можно добавить ссылок, оформить см. также по-другому
## Источники информации
# [[Теорема Менгера, альтернативное доказательство]] (0.5)## Заменить тире на шаблон## Обращение к леммам сделать через интервики## См. также на оригинальное доказательство## Источники информации
# [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]] (1.5)
## пункт "Определения" не нужен
<li>[[Алгоритм Прима]]</li>
<li> [[Алгоритм Краскала]] </li>
<li> '''fixed''' [[Алгоритм Борувки]] (5) </li># Описание алгоритма оформить красиво и чуточку понятней# Доказательство теоремы оформить красиво# Переделать доказательства с учётом возможного равенства рёбер# Отформатировать псевдокод# Пример как-то кривовато описан (особенно это разделение на компоненты связности)# Заменить дефис на шаблон# Источники информации правильно оформить# Категория
<li> '''!!!''' [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]] (5) </li>
# Доказательство красиво оформить
# Знаки неравенств
# Категория
<li> '''!!!''' [[Алгоритм двух китайцев]] (67) </li>
# Англоязычные термины оформить правильно
# Добавить определение покрывающего дерева
<ol>
<li value="7">[[Матрица Кирхгофа]]</li>
<li> ''взяли'' [[Связь матрицы Кирхгофа и матрицы инцидентности]] (0.5)</li># Англоязычные термины# Константы взять в Tex# См. также и источники информации# Категория<li> ''взяли'' [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]] (0.5)</li># Добавить ссылку на формулу Бине-Коши (примечание на википедию или интервики на конспект линала)# Источники и см. также# Исправить знаки неравенств# Заменить тире на шаблон# Категория<li> ''взяли'' [[Количество помеченных деревьев]] (0.5)</li># Англоязычные термины# Первый пункт не нужен# Категория# Оформить доказательство красиво# См. также и источники информации# = в Tex<li> ''взяли'' [[Коды Прюфера]] (0.5)</li># Не оформлять описание алгоритма как псевдокод# Англоязычные термины# Категория# См. также и Источники информации
</ol>
<ol>
<li value="1"> [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]</li>
<li> '''!!!'взяли'' [[Покрытие ребер графа путями]] (53)</li># Так и не надо определение почти связного графа {{---}} надо внести в предыдущий конспект, а здесь сделать интервики# Знак "не принадлежит" оформить в Tex# Что-то доказательство какоеКакое-то неочевидное. Надо пояснить, почему Эйлеров цикл распадётся на N путей# То же самое в достаточности# Оформить правильно источники информации# Категориямутное доказательства<li> ''fixed'' [[Алгоритм построения Эйлерова цикла]] (32) </li># Отформатировать псевдокод# Довести до ума. Начиная с представления уже тяжко. До этого момента надо подытожить текущие доказательство, а то там много разных фактов и надо их какКакое-то в одну пачку собрать, сказав, чего хочется достичь дальше.# Категориямутное доказательство леммы про корректность алгоритма<li> '''!!!''' [[Произвольно вычерчиваемые из заданной вершины графы]] (6) </li># Англоязычные термины оформить правильно# Что значит неодноэелементный?# Стрелки слишком длинные# На картинке ошибка {{---}} почему-то не соединена средняя вершина в дереве, хотя она имеет нечётную степень# Источники информации правильно оформить# Хотелось бы больше пояснений в доказательстве# В строении не очевидно, что каждый произвольно вычерчиваемый граф можно построить, используя в основе какой-то лес# Категория
</ol>
=== Гамильтоновы графы ===
<ol>
<li value="5"> '''взяли''' [[Гамильтоновы графы]] (6.5) </li># Заменить дефисы на тире# Исправить знаки неравенств# Отформатировать псевдокод# Помёрджить с конспектом динамического программирования и пофиксить ошибки в обоих, если есть (должны остаться алгоритмы поиска пути/цикла, пути, минимизирующего какой-то критерий)# Источники информации# Категория<li> ''взяли'' [[Теорема Хватала]] (0.5) </li># Исправить знаки неравенств# Поставить \mid в множествах# Лишние кавычки в доказательствах вокруг стрелок# Убрать q.e.d# Оформить правильно источники информации# Категория<li>[[Теорема Поша]]</li>
<li> [[Теорема Дирака]] </li>
<li> [[Теорема Оре]] </li>
<li> '''fixed''' [[Теорема Поша]]</li><li> [[Теорема Гуйя-Ури]] </li><li> [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]] (5) </li># Странные обозначения для графа и множеств вершин и рёбер# Убрать умножение звёздочкой# Заменить дефис на тире# Отформатировать псевдокод# Источники информации# Исправить знаки неравенств# Категория
<li> '''!!!''' [[Теорема Гринберга]] (5) </li>
# Англоязычные термины оформить правильно# Дефис заменить на тире# Картинки криво расположеныПояснить переходы в теореме# Ссылки поехали Внести пояснение в примере# Добавить подзаголовок "Пример" или "Использование теоремы", а лучше что-то поудачнейопределение бонда# Почему необходимое условие? А И зачем нужно доказывать отсутствие гамильтонова бонда в обратную сторонуграфе?# Пояснить, что такое R и R'. Иначе непонятно в теореме, почему область R разбита на e + 1 грань# КатегорияКартинку сделать красивой<li> '''fixedвзяли''' [[Турниры]] (56) </li># Англоязычные термины# Добавить оценку на число турниров в графе из n вершин# Убрать лишние определения# Оформить правильно источники информации# Немного неправильно сформулировано утверждение про полустепени вершин# Категория12' '''!!!''' [[Турниры]] (5)# Доказательства всех утверждений из конспекта (эквивалентность определений утверждений и конденсация)<li> ''взяли'' [[Теорема Редеи-Камиона]] (0.5) </li># Исправить знаки неравенств# Правильно оформить источники информации# Категория
</ol>
== 5. Укладки графов ==
# ''взяли'' [[Укладка графа на плоскости]] (0.5)## Англоязычные термины правильно оформить## Добавить пару ссылок на конспекты вычгеома о том, чем хороши планарные графы## Источники информации# ''fixed'' [[Формула Эйлера]] (0.5)## Исправить знаки неравенств## Заменить литературу на источники информации## Добавить ссылок# ''fixed'' [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]] (0.5)
## Исправить знаки неравенств
## Источники информации
## Константы в Tex
# ''взяли'' [[Укладка дерева]] (1)## Заменить sup и inf на \sup и \inf## Заменить дефисы на тире## Картинки адекватно расположить## Англоязычные термины правильно оформить## Зачем в начале замечание про грань?## Увеличить дроби# ''взяли'' [[Укладка графа с планарными компонентами реберной двусвязности]] (0.5)## Заменить источники на источники информации## Взять все переменные в Tex## Добавить См. также## Интервики на мост# ''взяли'' [[Укладка графа с планарными компонентами вершинной двусвязности]] (0.5)## Исправить знаки неравенств## Заменить источники на источники информации## deg заменить на \deg
# [[Теорема Понтрягина-Куратовского]]
# ''взяли'' [[Род, толщина, крупность, число скрещиваний]]# [[Двойственный граф планарного графа]] (1)## Добавить пробел после "двойственным" в определении## Интервики## Убрать neat из определения самодвойственного графа## Увеличить дроби## Добавить источники информации## Интервики на мост, планарные графы## Добавить См. также
# [[Теорема Фари]]
# [[Гамма-алгоритм]]
== 6. Раскраски графов ==
# '''fixed''' [[Раскраска графа]] (6)## Правильно оформить англоязычные термины## Заменить \phi на \varphi## Пункт "Хроматическое число" не нужен## Заменить дефисы на тире## Пояснить, что такое нулевой граф## Список хроматических чисел нормально оформить## Четвёртый пример заменить на двудольные графы (дерево, в частности, является таким)## Оформить правильно источники информации## Примечания перенести выше## Кинуть интервики на неразрешимость задачи о раскраске графа## Написать о связи хроматического числа и хроматического многочлена, и почему нельзя найти хроматическое число, если у нас есть такая замечательная штука, как хроматический многочлен?# ''fixed'' [[Двудольные графы и раскраска в 2 цвета]] (3)
## Англоязычные термины
## Убрать определение двудольного графа и сделать интервики на основной конспект
## Перенести см. также до источников информации, а ссылку заменить на интервики
# [[Хроматический многочлен]]
# '''fixed''' [[Формула Зыкова]] (6)## Определения выделить жирным## Англоязычные термины правильно оформить## Написать более подробное, понятное и корректное доказательство## Исправить знаки неравенств## Правильно оформить источники информации## Добавить см. также# '''!!!''' [[Формула Уитни]] (6)## Заменить дефисы на тире## Исправить знаки неравенств## Заменить \phi на \varphi## Правильно оформить источники информации## А что такое собственные и несобственный раскраски?## Пояснить непонятные места в доказательстве вцелом## Добавить см. также# [[Теорема Брукса]] (0.5)## Заменить дефисы на тире## Интервики## "на iом шаге" {{---}} пропущен дефис## Исправить знаки неравенств## Оформить правильно источники информации## Добавить см. также# ''взяли'' [[Верхние и нижние оценки хроматического числа]] (1)## Заменить дефисы на тире## Исправить знаки неравенств## Интервики## Англоязычные термины## Заменить max на \max## Все переменные взять в Tex## Увеличить дроби## Оформить правильно источники информации и см. также# ''взяли'' [[Хроматическое число планарного графа]] (3)## Все константы взять в Tex## Доказательство по индукции красиво оформить## Заменить дефисы на тире## Исправить знаки неравенств## Теорема о 5-раскраске планарного графа именная {{---}} Хивуд {{---}} дать ей название## Оформить правильно источники информации## Заменить многоточия на \ldots## Разместить картинки друг под другом# ''взяли'' [[Многочлен Татта]] (0.5)## Англоязычные термины## Заменить дефисы на тире## " Уитни (Whiney rank polynomial)." {{---}} кажется, пропущено t## "Показатели в формуле раногового" {{---}} зачем это в определение вносить?## Интервики## Оформить правильно источники информации# [[Теория Рамсея]] ('''??10''')
## Тут вообще ад какой-то
== 7. Обход в глубину ==
# '''взялиfixed''' [[Обход в глубину, цвета вершин]] (5)
## Англоязычные термины правильно оформить
## Отформатировать псевдокод
## Переименовать конспект в Обход в глубину, DFS
## Красивую картинку с цветными вершинами
# [[Лемма о белых путях]]
# '''fixed''' [[Использование обхода в глубину для проверки связности]] (5)## Отформатировать псевдокод## Задачу в шаблон## Добавить примеров задач, например, как по двум вершинам определять, являются ли они связанными в режиме online при добавлении рёбер## Добавить источники информации, см. также## Tex внутри конспекта сделать красивым
# [[Использование обхода в глубину для поиска цикла в ориентированном графе]]
# [[Использование обхода в глубину для топологической сортировки]]
# ''взяли'' [[Использование обхода в глубину для поиска компонент сильной связности]] (3)## Некрасивый список в доказательстве теоремы## Отформатировать псевдокод## Добавить ссылок# '''взяли'fixed'' [[Использование обхода в глубину для поиска точек сочленения]] (64)## Убрать отступ в теоремеЧто-то картинки неудачно расположены## Кривая структура у доказательства
## Отформатировать псевдокод
## Источники информации красиво оформить
## Добавить примеры того, когда и почему становится плохо, если функция up будет определена по-другому# ''fixed'' [[Построение компонент вершинной двусвязности]] (3)## Отформатировать псевдокод## Красиво оформить источники# ''взяли'' [[Использование обхода в глубину для поиска мостов]] (3)## Заменить min на \min## Отформатировать псевдокод## Некрасиво оформлено утверждение маркированным списком, да и у тело утверждения тоже некрасивое## Нормально оформить источники информации, добавить см. также# ''fixed'' [[Построение компонент реберной двусвязности]] (3)## Отформатировать псевдокод## Визуализатор внести в источники информации
== 8. Кратчайшие пути в графах ==
# [[Обход в ширину]]
# ''взяли'' [[Алгоритм Форда-Беллмана]] (3)## Получшение введение, задачу в шаблон## Интервики## Отформатировать псевдокоды## for в тексте взять в mathrm## Заменить дефисы на тире## Исправить знаки неравенств## Оформить правильно источники информации# ''взяли'' [[Алгоритм Дейкстры]] (3)## Псевдокод вообще криво оформлен## Исправить знаки неравенств## Оформить правильно источники информации## Табличку сделать красивой# '''взяли''' [[Алгоритм Флойда]] (6)## Оформить правильно источники информации## Заменить min на \min## Отформатировать правильно псевдокод## Вспомнить алгоритм построение транзитивного замыкания на первом курсе## Исправить в тексте знаки равенства и неравенства## Оформить правильно источники информации## Добавить оптимизацию с битовыми масками# '''!!!''' [[Алгоритм Джонсона]] (7)## Англоязычные термины## Заменить дефисы на тире## Зачем-то в шаблоне определение написано не определение## Исправить знаки неравенств## Отформатировать псевдокоды## Доказательство со стрелочками красиво оформить## Оформить правильно источники информации## Расписать сложность других реализаций# '''fixed''' [[Алгоритм Левита]] (7)## Оформить правильно англоязычные термины## Отформатировать псевдокод## Оформить правильно источники информации## Добавить пример графа, на котором алгоритм работает экспоненциальное время## Категории# '''!!!''' [[Алгоритм A*]] (8)## что-то со второй картиночкой, там гифка, а почему-то не отображается## псевдокод — практически копипаста из википедии, правда непонятно, что с этим делать. Я уверен, например, что никто (я тоже) не знает, что такое tentative.## какая-то тут муть написана, что в корректности, что в оптимальности## а еще можно написать про случай с монотонной эвристикой## Оформить правильно англоязычные термины## Оформить правильно ссылки примечаниями и источники информации
# [[Алгоритм D*]]
# ''взяли'' [[Эвристики для поиска кратчайших путей]] (2)## "Дано" криво оформлено## Заменить дефисы на тире## Оформить правильно источники информации и англоязычные термины## Оформить правильно списки, заглавные буквы корректно расставить## Ссылку на основную статью оформить правильно## Таблички сделать красивыми
== 9. Задача о паросочетании ==
# [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]] (2-3)## Добавить картинок паросочетаний различных красивых (две-три хватит)# [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]] (2)## что-то тут какие-то по мелочи баги, предлоги иногда пропущены и все такое## Интервики## Отформатировать псевдокод## Картинки заползают на заголовки, придумать что-нибудь с этим## == в тексте заменить на =## Оформить правильно источники информации
# [[Алгоритм Куна для поиска максимального паросочетания]]
# [[Теорема Холла]] (1.5)## добавить ссылку на английскую википедию## Англоязычные термины## Дефисы на тире## Оформить доказательство правильно и красиво## Исправить знаки неравенств## Константы в Tex## Примечания маленькие## Добавить больше ссылок, заменить на источники информации# [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]] (1)## Оформить правильно источники информации## Убрать neat в определении## Убрать <br> ## Англоязычные термины оформить правильно## Пункт Определения не нужен## Оформить красиво списки
# [[Связь вершинного покрытия и независимого множества]]
## См. предыдущее# ''fixed'' [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]] (2)## Англоязычные термины оформить правильно## Дублируется определение совершенного паросочетания## Пояснить про независимые переменные## И что за детерминант от элемента матрицы, а не самой матрицы?## - -> {{---}}## Источники информации# [[Теорема Татта о существовании полного паросочетания]] (0.5)## Оформить правильно англоязычные термины## Оформить правильно и красиво доказательства## Убрать граф из mathbb## Сделать ссылку примечанием## Источники информации
# '''!!!''' [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]] (7)
## как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример с картинками
# '''!!!''' [[Декомпозиция Эдмондса-Галлаи]] (5)## Много пустых строк## Пробелы перед открывающей круглой скобкой## Определение нечётных компонент дублируется с конспектом из теоремы Татта## Переменные в Tex## Дефисы на тире## Добавить доказательства теорем (хотя бы одной (ну или хотя бы ссылки примечаниями))## Убрать заголовки первого уровня# '''!!!взяли''' [[Задача об устойчивом паросочетании]] ''(все правки стоят 10 баллов)''
## Переменные и константы в Tex
## Добавить сначала постановку задачи
== 10. Задача о максимальном потоке ==
# [[Определение сети, потока]]
# ''fixed'' [[Разрез, лемма о потоке через разрез]] (4)## Оформить правильно англоязычные термины## Списки кривые## Определения выделить жирным## Дефисы превратить в тире## Убрать ; из леммы, сделать маркированный список## Исправить знаки неравенств## Скобки в тексте кое-где лишние## Источники информации ## Нарисовать красивую картинку вместо текущей
# [[Дополняющая сеть, дополняющий путь]]
# [[Лемма о сложении потоков]] (0.5)## Переименовать конспект## Убрать "Также есть..."## Вынести названия лемм в заголовки шаблонов# [[Теорема Форда-Фалкерсона]] (0.5)## Знаки неравенств## Источники информации# '''!!!''' [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]] (5)## гм, и зачем "дельта" русским словом в псевдокоде?## псевдокод сейчас не вполне понятен — какой-то Cmin, какой-то dfs, который непонятно как использовать. Обернуть это в полноценную функцию, которая считает значение потока и отрефакторить псевдокод## Константы взять в Tex## Источники информации## Знаки неравенств## Подробней пояснить пример несходимости# '''fixedвзяли''' [[Алоритм Эдмондса-Карпа]] (75)## а описание алгоритма где?## везде упоминается кратчайший путь, но не указывается, какой конкретно — по ребрам, пропускным способностям, или чему?## ссылки на русскую/английскую википедию## Отформатировать псевдокод## while в тексте обернуть в \mathrm## Знаки неравенств## Добавить Полностью описать пример про грибок с картинками в конспектконспекте# ''взяли'' [[Алгоритм масштабирования потока]] (3)## ссылки на русскую/английскую википедию## ссылка на "Андрей Станкевич: Задача о максимальном потоке" на работает, а жаль, интересно даже, что там было. Если есть, найдите другой источник этой же статьи.## Отформатировать псевдокод## Источники информации## См. также## Увеличить картинки# ''взяли'' [[Блокирующий поток]] (1)
## англоязычные термины
## ссылки на русскую и английскую википедию
## Добавить немного общей информации
## Расположить красиво картинки, чтобы не наезжали
# '''fixed''' [[Схема алгоритма Диница]] (6)## "динамические деревья Слетора и Тарьяна" — ссылку внешнюю хотя бы сделайте## "makeGl" назвать как-нибудь нормально## "algorithmDinica" тоже назвать нормально## Интервики## Написать более подробный псевдокод# '''!!!fixed''' [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]] (6)
## может, назвать остаточную сеть <tex>G_f</tex>, как в предыдущих конспектах?
## "сети с текущим потоком, равным 0, и максимальным потоком, равным F" — в какой сети? (бывает исходная, остаточная и слоистая еще как минимум) Тут имеется в виду, что расстояние измерили до того, как пускать поток, что ли?
## Знаки неравенств
## Источники информации
# '''!!!''' [[Алгоритм поиска блокирующего потока в ациклической сети]] (5)## "Жадный Алгоритм" — зачем с большой буквы алгоритм?## Не нравится мне dfs без аргументов в удаляющем обходе, вообще он какой-то плохой, переписать псевдокод для этого алгоритма полностью, чтобы было приближено к реальной реализации
## '''!!! (10)''' алгоритм МКМ плохо и непонятно написан, желательно переписать описание, сделать псевдокод чуть менее абстрактным, добавить доказательство, добавить картиночку, вынести в отдельную статью, ссылка на оригинальную статью есть в обсуждении
# '''!!!''' [[Метод проталкивания предпотока]] (7)
## зачем какие-то кванторы в for?## initialaze -> initialize## названия функций в тексте оборачиваются в \mathrm или \mathtt## Англоязычные термины## Отформатировать псевдокоды## Больше неформальных описаний, чтобы было понятно## За картиночки Картиночки с резервуарами {{---}} отдельные большие бонусы!# '''!!!''' [[Алгоритм "поднять-в-начало"]] (5, но сначала лучше сделать предыдущий) ## названия функций в тексте оборачиваются в \mathrm или \mathttИсточники информации## relable -> relabelДобавить см. также## Англоязычные термины оформить правильноДефисы заменить на тире
## Отформатировать псевдокоды
# ''взяли'' [[Алгоритм "поднять-в-начало"]]# [[Теорема о декомпозиции]] (3)## Дефисы на тире## Переписать формулировку теоремы## Отформатировать псевдокод## Оформить правильно источники информации# ''fixed'' [[Теорема о декомпозиционном барьере]] (3)
## Источники информации
## Пояснить,почему такие константы используются
## Увеличить дроби
## А что из этой теоремы следует?
# ''взяли'' [[Циркуляция потока]] (3)## англоязычные термины## ссылки на русскую и английскую википедию## раздел постановка задачи не нужен, перенести в заголовок, задачу можно в шаблон взять## сделать псевдокод чуть менее абстрактным и оформленным в соответствии с правилами## Источники информации# ''fixed'' [[Алгоритм Каргера для нахождения минимального разреза]] (2)## внутреннюю ссылку на мультиграф## названия функций в тексте оборачиваются в \mathrm или \mathtt## Англоязычные термины## Отформартировать псевдокод
== 11. Задача о потоке минимальной стоимости ==
# '''!!!''' [[Поток минимальной стоимости]] (5)## "Найти любой поток величины..." -- а почему так получится поток минимальной стоимости? (видимо, надо сослаться на лемму)## Убрать "Определение задачи", из-под определения вынести формулировку в шаблон задача## Оформить правильно источники информации (и вообще всё оформить правильно)## Добавить определений стоимости, свойства стоимости на обратных рёбрах, картинки нарисовать# '''!!!''' [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]] (0.5, вместе с алгоритмом)## Исправить знаки неравенств## Источники информации# ''fixed'' [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]] (0.5)
## Интервики на декомпозицию
## Знаки неравенств
## Источники информации
# '''!!!''' [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]] (4.5, вместе с теоремой)## Помёрджить с теоремой Ф-Ф## Отформатировать псевдокод
# '''!!!''' [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]] (5)
## Написать и оформить так, чтобы не было чуши
# ''взяли'' [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]] (0.5)
## Взять задачи в шаблон
## Оформить покрасивей и правильней
# '''!!!''' [[Венгерский алгоритм решения задачи о назначениях]] (5)## написать более подробный псевдокод## Интервики## Источники информации

Навигация