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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎1. Основные определения теории графов)
(→‎2. Связность в графах)
Строка 38: Строка 38:
 
== 2. Связность в графах ==
 
== 2. Связность в графах ==
 
# [[Отношение связности, компоненты связности]]
 
# [[Отношение связности, компоненты связности]]
 +
## англоязычные термины
 +
## интервики
 
# [[Отношение реберной двусвязности]]
 
# [[Отношение реберной двусвязности]]
 +
## англоязычные термины
 
# [[Отношение вершинной двусвязности]]
 
# [[Отношение вершинной двусвязности]]
 +
## англоязычные термины
 
# [[Граф компонент реберной двусвязности]]
 
# [[Граф компонент реберной двусвязности]]
 
# [[Граф блоков-точек сочленения]]
 
# [[Граф блоков-точек сочленения]]
 +
## Капс какой-то зачем-то
 
# [[Точка сочленения, эквивалентные определения]]
 
# [[Точка сочленения, эквивалентные определения]]
 +
## Цифры в начале определений не нужны, их можно в хедер определения
 
# [[Мост, эквивалентные определения]]
 
# [[Мост, эквивалентные определения]]
 +
## англоязычные термины
 +
## Цифры в начале определений не нужны, их можно в хедер определения
 
# [[k-связность]]
 
# [[k-связность]]
 +
## англоязычные термины
 
# [[Теорема Менгера]]
 
# [[Теорема Менгера]]
 +
## убрать кванторы там, где они не нужны (в формулировках теорем) и заменить словами
 
# [[Теорема Менгера, альтернативное доказательство]]
 
# [[Теорема Менгера, альтернативное доказательство]]
 
# [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]
 
# [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]

Версия 22:37, 16 октября 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. Вершинная, реберная связность, связь между ними и минимальной степенью вершины

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

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

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

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

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

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

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

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

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

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

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