Участник:Dgerasimov/Тикеты по конспектам year2012

Материал из Викиконспекты
< Участник:Dgerasimov
Версия от 22:22, 16 октября 2013; Dgerasimov (обсуждение | вклад) (→‎1. Основные определения теории графов)
Перейти к: навигация, поиск

Тикеты нумеруются как "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. Связность в графах

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

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

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

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

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

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

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

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

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

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

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