Изменения

# '''!!!''' [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]## Правильно оформить англоязычные термины## "Иногда граф, построенный таким образом, называют псевдографом (pseudograph)" {{---}} кривовато написано, надо переписать## Дублируется определение смежных вершин## Добавить ссылок в источники информации## Добавить определение полного графа## Несправедливо забыли дерево в часто используемых графах; добавить другие виды графов

## Увеличить дроби## Взять константы в tex## Заменить умножение на \cdot## Добавить пару слов о графах с петлями и кратными рёбрами# '''!!!'fixed'' [[Теорема о существовании простого пути в случае существования пути]](4)

# '''!!!''' [[Теорема о существовании простого цикла в случае существования цикла]]## На самом деле, конструктивное доказательство тут не очень понятное и не совсем корректное. Сделать неконструктивное и добавить нормальные картинки## Добавить в первую теорему, что граф неориентированный

## "Для графов без петель и кратных рёбер матрица смежности бинарна (состоит из нулей и единиц), причём её главная диагональ целиком состоит из нулей. " — зачем объединять эти свойства, можно разнести на два## Что за помеченный граф?## Добавить про что, в матрице смежности можно хранить веса рёбер# [[Связь степени матрицы смежности и количества путей]]## Это можно внести в прошлый конспект## Добавить что-нибудь про бинарное возведение в степень# '''!!!'взяли'' [[Матрица инцидентности графа]](4 ''или больше, зависит от свойств'')

# '''!!!''' [[Циклическое пространство графа]]# Англоязычные термины## Пункт "Определение" не нужен, см. правила форматированияОформить правильно источники информации## Ker, dim, Rang надо запихать в \operatorname, а Добавить См. также кинуть ссылку на определение ядра оператора (в матане/функате на конспектах точно есть)матрицу смежности## интервикиДобавить про списки смежности и их оформить тоже в таблички#[[Циклическое пространство графа]]# "Литература ''fixed'' [[Фундаментальные циклы графа]] (формулировки другие1) " — "формулировки другие" относится к конкретному источнику, а не ко всей литературе.## Заменить тире на шаблонИсточники информации нормально оформить## Добавить ссылок в источники информацииПодписать получше картинку## Неплохо бы написать, зачем это нужно (позволяет какие-нибудь теоремы про графы доказать или что-то ещё)Заменить многоточия на \ldots# [[Фундаментальные циклы графа]]# [[Дерево, эквивалентные определения]]Отформатировать по правилам# '''!!!'fixed'' [[Диаметр дереваДерево, эквивалентные определения]](1)## Переименовать в Алгоритмы на деревьях## Добавить другие алгоритмы (если будет много содержательных, то можно будет поставить <tex> 10 </tex> баллов за конспект)Англоязычные термины## Отформатировать псевдокодПофиксить знаки неравенств## Добавить категории, ссылки, см. такжеИсточники информации нормально оформить## ИнтервикиОформить красиво доказательства## Исправить tex[[Алгоритмы на деревьях]]# ''fixed'' [[Дополнительный, самодополнительный граф]](1)

## англоязычные термины[[Точка сочленения, эквивалентные определения]]## Добавить ссылок[[Мост, эквивалентные определения]]

## англоязычные термины## Тире заменить на шаблон## Палку вертикальную в множестве заменить на \mid## Странное обозначение {{---}} \smallsetminus# ''fixed'' [[Теорема Менгера]](0.5)

## Заменить тире на шаблон## Обращение к леммам сделать через интервики# [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]](1.5)

=== Построение остовных деревьев ===<ol><li value="1">[[Остовные деревья: определения, лемма о безопасном ребре]]</li><li>[[Алгоритм Прима]]</li><li> [[Алгоритм Краскала]] </li><li> [[Алгоритм Борувки]] </li><li> '''!!!''' [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]] (5) </li># Доказательство красиво оформить# Заменить дефис на шаблон# Зачем там написано про Краскала? Если алгоритм доказывается через критерий, то надо в отдельный пункт# Почему ребро uv {{---}} единственное ребро, пересекающее разрез?# Источники информации# Знаки неравенств# Категория<li> '''!!!''' [[Матрица КирхгофаАлгоритм двух китайцев]](7) </li>#Англоязычные термины оформить правильно# Ссылка на простой граф плохо сделана. Добавить определение в самый первый конспект и сделать покрывающего дерева# Описать реализацию красиво# Дефис заменить на него ссылкутире#Отформатировать псевдокод# Доказать, почему не более V конденсаций# Источники информации и см. также нормально оформитьправильно# Доказать второе замечание# Добавить отступы в описании примера# 5ый пункт в описании алгоритма расписать чуть понятней# Категория</ol> === Свойства остовных деревьев ===<ol><li value="7">[[Матрица Кирхгофа]]</li><li> [[Связь матрицы Кирхгофа и матрицы инцидентности]]</li>## Константы взять в tex## См. также и источники информации# <li> [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]</li><li> [[Количество помеченных деревьев]] </li><li> [[Коды Прюфера]] </li></ol>## Добавить ссылку на формулу Бине-Коши (примечание на википедию или интервики на конспект линала)## Источники и см== 4. такжеОбходы графов ===== Эйлеровы графы ===## Исправить знаки неравенств<ol>## Заменить тире на шаблон<li value="1"> [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]</li># <li> ''взяли'' [[Количество помеченных деревьевПокрытие ребер графа путями]](3)</li>## англоязычные терминыКакое-то мутное доказательства# <li> [[Коды ПрюфераАлгоритм построения Эйлерова цикла]](2) </li>## Не оформлять описание Какое-то мутное доказательство леммы про корректность алгоритма как псевдокод<li> [[Произвольно вычерчиваемые из заданной вершины графы]] </li></ol>

== в процессе проверки 4. Обходы графов = Гамильтоновы графы ===# '''fixed''' [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]## англоязычные термины<ol>## не нужно по параграфу для каждого определения, либо сделать "Основные определения", либо вообще все в заголовок вынести## <li value="См. Также5" — зачем "также" с большой буквы?# > [[Покрытие ребер графа путямиГамильтоновы графы]]</li># <li> [[Алгоритм построения Эйлерова циклаТеорема Хватала]]</li># <li> [[Произвольно вычерчиваемые из заданной вершины графыТеорема Дирака]]</li># '''fixed''' [[Гамильтоновы графы]]## англоязычные термины# <li> [[Теорема ХваталаОре]]</li># <li> [[Теорема ДиракаПоша]]</li># <li> [[Теорема ОреГуйя-Ури]]</li># <li> [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]]</li><li> '''!!!''' [[Теорема Гринберга]] (5) </li># Пояснить переходы в теореме# Внести пояснение в определение бонда# И зачем нужно доказывать отсутствие гамильтонова бонда в графе?# Картинку сделать красивой<li> '''взяли''' [[Турниры]](6) </li># Доказательства всех утверждений из конспекта (эквивалентность утверждений и конденсация)<li> [[Теорема Редеи-Камиона]]</li></ol>

== в процессе проверки 5. Укладки графов ==# ''fixed'' [[Укладка графа на плоскости]]## англоязычные термины## думаю, здесь же можно написать, что в 3D любой граф укладывается

# ''fixed'' [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]](0.5)## Дать ссылку на определения K5 и K3,3Исправить знаки неравенств## Источники информации## Константы в Tex

# ''fixed'' [[Теорема Понтрягина-Куратовского]]## Определение гомеоморфизма есть в "Укладка графа на плоскости"[[Род, толщина, на него и сослаться.## Формулировку теоермы надо вынести в заголовоккрупность, например.число скрещиваний]]# ''fixed'' [[Двойственный граф планарного графа]]#[[Теорема Фари]]# англоязычные термины[[Гамма-алгоритм]]

== в процессе проверки 6. Раскраски графов ==Во всем разделе — надо англоязычные термины (их по 1-2 в каждом конспекте)# [[Раскраска графа]]# ''fixed'' [[Раскраска графаДвудольные графы и раскраска в 2 цвета]](3)## Англоязычные термины## пункт "Раскраска Убрать определение двудольного графа" не нужен, перенести в заголовоки сделать интервики на основной конспект## англоязычные терминыКартинку двудольного графа перенести ниже, а то плохо смотрится## "Хроматическим многочлен"Интервики## надо бы написатьДобавить, почему нам вообще интересно раскрашивать графычто можно ещё за проход в ширину проверить# [[Двудольные графы # Оформить правильно источники информации и раскраска в 2 цвета]]См. также## Перенести см. также до источников информации, а ссылку заменить на интервики

== '''в процессе проверки''' 7. Обход в глубину ==# '''fixed''' [[Обход в глубину, цвета вершин]](5)## Англоязычные термины правильно оформить## Отформатировать псевдокод## Красивую картинку с цветными вершинами

# ''fixed'' [[Использование обхода в глубину для поиска точек сочленения]](4)## Что-то картинки неудачно расположены## Кривая структура у доказательства## Отформатировать псевдокод## Источники информации красиво оформить

== '''в процессе проверки''' 8. Кратчайшие пути в графах ==

== '''в процессе проверки''' 9. Построение остовных деревьев ==# [[Лемма о безопасном ребре]]# [[Алгоритм Прима]]# [[Алгоритм Краскала]]# [[Алгоритм Борувки]]# [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]]# [[Алгоритм двух китайцев]] == '''в процессе проверки''' 10. Задача о паросочетании ==# [[Теорема Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]]## англоязычные термины

## что-то тут какие-то по мелочи баги, предлоги иногда пропущены и все такое# '''!!!''' [[Алгоритм Куна для поиска максимального паросочетания]]## зачем-то в разделах "алгоритм" и "время работы" какие-то дурацкие отступы## код -- копипаста с емакса## источники перечислять с помощью *, а не :

# [[Теорема Татта о существовании полного паросочетания]]# '''!!!''' [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]](7)## как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести примерс картинками# [[Декомпозиция Эдмондса-Галлаи]]# '''взяли''' [[Задача об устойчивом паросочетании]] ''(все правки стоят 10 баллов)''## Переменные и константы в Tex## Добавить сначала постановку задачи## Кривая ссылка на паросочетание## Дефисы на тире## Определения выделять жирным## Отформатировать псевдокоды## Зачем-то списки в доказательствах лемм использованы## Битая ссылка на соседей## Надо бы доказать все леммы## Оформить правильно источники информации## И вообще всё оформить надо

== 1110. Задача о максимальном потоке ==# ''fixed'' [[Определение сети, потока]]## ссылки на русскую и английскую википедию# ''fixed'' [[Разрез, лемма о потоке через разрез]]## англоязычные термины## добавить определение минимального разреза## ссылки на русскую и английскую википедию# ''fixed'' [[Дополняющая сеть, дополняющий путь]]## Дополняющую сеть также называют остаточной, указать это## ссылки на русскую и английскую википедию# ''fixed'' [[Лемма о сложении потоков]]## добавить внутренних ссылок

## гм, и зачем "дельта" русским словом в псевдокоде?## псевдокод сейчас не вполне понятен — какой-то Cmin, какой-то dfs, который непонятно как использовать. Обернуть это в полноценную функцию, которая считает значение потока.# '''взяли''' [[Алоритм Эдмондса-Карпа]](5)## а описание алгоритма где?## везде упоминается кратчайший путь, но не указывается, какой конкретно — по ребрам, пропускным способностям, или чему?## ссылки на русскую/английскую википедиюПолностью описать пример про грибок с картинками в конспекте

## ссылки на русскую/английскую википедию## ссылка на "Андрей Станкевич: Задача о максимальном потоке" на работает, а жаль, интересно даже, что там было. Если есть, найдите другой источник этой же статьи.# ''взяли'' [[Блокирующий поток]](1)

## "динамические деревья Слетора и Тарьяна" — ссылку внешнюю хотя бы сделайте## "makeGl" назвать как-нибудь нормально## "algorithmDinica" тоже назвать нормально# '''fixed''' [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]](6)## может, назвать остаточную сеть $<tex>G_f$</tex>, как в предыдущих конспектах?## "сети с текущим потоком, равным 0, и максимальным потоком, равным F" — в какой сети? (бывает исходная, остаточная и слистая слоистая еще как минимум) Тут имеется в виду, что расстояние измерили до того, как пускать поток, чтоличто ли?## В лемме в утверждении фигурирует поток $<tex>f$</tex>, но дальше про него ничего нет. Зачем он?

# '''!!!''' # Дефисы на тире## Знаки неравенств## Источники информации# [[Алгоритм поиска блокирующего потока в ациклической сети]]## "Жадный Алгоритм" — зачем с большой буквы алгоритм?## Не нравится мне dfs без аргументов в удаляющем обходе, вообще он какой-то херовый, переписать псевдокод для этого алгоритма польностью, чтобы было приближено к реальной реализации## '''!!! (10)''' алгоритм МКМ плохо и непонятно написан, желательно переписать описание, сделать псевдокод чуть менее абстрактным, добавить доказательство, возможно, добавить картиночку, а может даже вынести в отдельную статью, ссылка на оригинальную статью есть в обсуждении# '''!!!''' [[Метод проталкивания предпотока]](7)## Картиночки с резервуарами!## Источники информации## зачем какие-то кванторы в for?Добавить см. также## initialaze -> initializeДефисы заменить на тире## названия функций в тексте оборачиваются в \mathrmОтформатировать псевдокоды

## кванторы в псевдокоде не нужну, написать просто not exists# ''fixed'' [[Теорема о декомпозиционном барьере]](3)## Источники информации## Пояснить,почему такие константы используются## Увеличить дроби## А что из этой теоремы следует?

== 1211. Задача о потоке минимальной стоимости ==

# ''fixed'' [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]](0.5)## Интервики на декомпозицию## Знаки неравенств## Источники информации

# '''!!!''' [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]](5)# # Написать и оформить так, чтобы не было чуши# ''взяли'' [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]](0.5)## Взять задачи в шаблон## Оформить покрасивей и правильней# '''!!!''' [[Венгерский алгоритм решения задачи о назначениях]]## написать более подробный псевдокод