Участник:Dgerasimov/Тикеты по конспектам year2012 — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎6. Раскраски графов)
(→‎1. Основные определения теории графов)
Строка 2: Строка 2:
  
 
== 1. Основные определения теории графов ==
 
== 1. Основные определения теории графов ==
−
# [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
+
# '''!!!''' [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
 
## moar англоязычных терминов
 
## moar англоязычных терминов
 
## "Мультиграф с петлями принято называть псевдографом. " — при этом понятие мультиграфа встречается позже. Нехорошо, разобраться все же с правильными порядком и правильными определениями
 
## "Мультиграф с петлями принято называть псевдографом. " — при этом понятие мультиграфа встречается позже. Нехорошо, разобраться все же с правильными порядком и правильными определениями

Версия 11:31, 17 октября 2013

Тикеты нумеруются как "X-Y", где X — номер темы, а Y — номер тикета внутри темы.

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

  1. !!! Основные определения: граф, ребро, вершина, степень, петля, путь, цикл
    1. moar англоязычных терминов
    2. "Мультиграф с петлями принято называть псевдографом. " — при этом понятие мультиграфа встречается позже. Нехорошо, разобраться все же с правильными порядком и правильными определениями
    3. Из определения орграфа с beg и end никак не следует, что там не может быть петель (кто мешает сделать beg e = v, end e = v?).
    4. "некоторые абстрактные множества." — а что такое неабстрактные множества?
    5. "V — конечное множество вершин" — при этом далее в каком-то конспекте есть пример для бесконечного графа. Не надо заставлять граф быть конечным, лучше написать отдельно, что называется конечным графом.
    6. запись "[math] E \subset V \times V(uv \sim vu~\backslash~\{uu~|~u \in V\})[/math]" я вообще не очень понимаю. Если вы понимаете, объясните мне, иначе напишите нормально :)
    7. альтернативное определение неориентированного графа мне не нравится, потому что прямо перед ним мы говорим, что ребро — неупорядоченная пара, а потом внезапно [math]ends : E \rightarrow V \times V[/math], а декартово произведение у нас еще как упорядочено.
  2. Лемма о рукопожатиях
  3. Теорема о существовании простого пути в случае существования пути
    1. перенести определения в "Основные определения"
    2. форматирование в некоторых местах какое-то упоротое, думаю, это видно.
  4. Теорема о существовании простого цикла в случае существования цикла
    1. добавить интервики
    2. форматирование в некоторых местах какое-то упоротое
  5. Матрица смежности графа
    1. "Для графов без петель и кратных рёбер матрица смежности бинарна (состоит из нулей и единиц), причём её главная диагональ целиком состоит из нулей. " — зачем объединять эти свойства, можно разнести на два.
  6. Связь степени матрицы смежности и количества путей
  7. Матрица инцидентности графа
    1. Определение инцидентности вроде есть в "Основных определениях", если нет — перенести его туда
  8. Циклическое пространство графа
    1. Пункт "Определение" не нужен, см. правила форматирования
    2. Ker, dim, Rang надо запихать в \operatorname, а также кинуть ссылку на определение ядра оператора (в матане/функате на конспектах точно есть)
    3. интервики
    4. "Литература (формулировки другие) " — "формулировки другие" относится к конкретному источнику, а не ко всей литературе.
  9. Фундаментальные циклы графа
    1. определения "каркаса", кажется, до этого не было, а вообще это вроде то же самое, что "остов", который используется во всем остальном курсе, так что если это так, заменить.
    2. Раздел "Определение" не нужен.
  10. Дерево, эквивалентные определения
    1. Кажется, ранее не было определний [math]K_n[/math], если нет, то надо куда-нибудь их добавить и сделать на них ссылку.
  11. Дополнительный, самодополнительный граф
    1. Оформить нормально определение изоморфности графов (видимо, его надо в "Основные опредения"), и добавить на него ссылку
    2. англоязычные термины

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

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

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

  1. Матрица Кирхгофа
    1. Пункт "Определение" не нужен, вынести в начало статьи
    2. "простого графа" — а простой — это какой? Кинуть ссылку на определение простого графа.
    3. 0, else — так не говорят, говорят "0, otherwise"
  2. Связь матрицы Кирхгофа и матрицы инцидентности
  3. Подсчет числа остовных деревьев с помощью матрицы Кирхгофа
  4. Количество помеченных деревьев
    1. англоязычные термины
  5. Коды Прюфера

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

  1. Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов
    1. англоязычные термины
    2. не нужно по параграфу для каждого определения, либо сделать "Основные определения", либо вообще все в заголовок вынести
    3. "См. Также" — зачем "также" с большой буквы?
  2. Покрытие ребер графа путями
  3. Алгоритм построения Эйлерова цикла
  4. Произвольно вычерчиваемые из заданной вершины графы
  5. Гамильтоновы графы
    1. англоязычные термины
  6. Теорема Хватала
  7. Теорема Дирака
  8. Теорема Оре
  9. Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре
  10. Турниры
  11. Теорема Редеи-Камиона

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

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

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

  1. Раскраска графа
    1. пункт "Раскраска графа" не нужен, перенести в заголовок
    2. англоязычные термины
    3. "Хроматическим многочлен"
  2. Двудольные графы и раскраска в 2 цвета
  3. Хроматический многочлен
  4. Формула Зыкова
  5. Формула Уитни
  6. Теорема Брукса
  7. Верхние и нижние оценки хроматического числа

7. Обход в глубину

8. Кратчайшие пути в графах

9. Построение остовных деревьев

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

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

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Участник:Dgerasimov/Тикеты_по_конспектам_year2012&oldid=33141»