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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «Тикеты нумеруются как "X-Y", где X — номер темы, а Y — номер тикета внутри темы. == 1. Основные ...»)
 
(→‎1. Основные определения теории графов)
Строка 3: Строка 3:
 
== 1. Основные определения теории графов ==
 
== 1. Основные определения теории графов ==
 
# [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
 
# [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
 +
## moar англоязычных терминов
 +
## "Мультиграф с петлями принято называть псевдографом. " — при этом понятие мультиграфа встречается позже. Нехорошо, разобраться все же с правильными порядком и правильными определениями
 +
## Из определения орграфа с beg и end никак не следует, что там не может быть петель (кто мешает сделать beg e = v, end e = v?).
 +
## "некоторые абстрактные множества." — а что такое неабстрактные множества?
 +
## "V — конечное множество вершин" — при этом далее в каком-то конспекте есть пример для бесконечного графа. Не надо заставлять граф быть конечным, лучше написать отдельно, что называется конечным графом.
 +
## запись "<tex> E \subset V \times V(uv \sim vu~\backslash~\{uu~|~u \in V\})</tex>" я вообще не очень понимаю. Если вы понимаете, объясните мне, иначе напишите нормально :)
 +
## альтернативное определение неориентированного графа мне не нравится, потому что прямо перед ним мы говорим, что ребро — неупорядоченная пара, а потом внезапно <tex>ends : E \rightarrow V \times V</tex>, а декартово произведение у нас еще как упорядочено.
 
# [[Лемма о рукопожатиях]]
 
# [[Лемма о рукопожатиях]]
 
# [[Теорема о существовании простого пути в случае существования пути]]
 
# [[Теорема о существовании простого пути в случае существования пути]]
 +
## перенести определения в "Основные определения"
 +
## форматирование в некоторых местах какое-то упоротое, думаю, это видно.
 
# [[Теорема о существовании простого цикла в случае существования цикла]]
 
# [[Теорема о существовании простого цикла в случае существования цикла]]
 +
## добавить интервики
 +
## форматирование в некоторых местах какое-то упоротое
 
# [[Матрица смежности графа]]
 
# [[Матрица смежности графа]]
 +
## "Для графов без петель и кратных рёбер матрица смежности бинарна (состоит из нулей и единиц), причём её главная диагональ целиком состоит из нулей. " — зачем объединять эти свойства, можно разнести на два.
 
# [[Связь степени матрицы смежности и количества путей]]
 
# [[Связь степени матрицы смежности и количества путей]]
 
# [[Матрица инцидентности графа]]
 
# [[Матрица инцидентности графа]]
 +
## Определение инцидентности вроде есть в "Основных определениях", если нет — перенести его туда
 
# [[Циклическое пространство графа]]
 
# [[Циклическое пространство графа]]
 +
## Пункт "Определение" не нужен, см. правила форматирования
 +
## Ker, dim, Rang надо запихать в \operatorname, а также кинуть ссылку на определение ядра оператора (в матане/функате на конспектах точно есть)
 +
## интервики
 +
## "Литература (формулировки другие) " — "формулировки другие" относится к конкретному источнику, а не ко всей литературе.
 
# [[Фундаментальные циклы графа]]
 
# [[Фундаментальные циклы графа]]
 +
 
# [[Дерево, эквивалентные определения]]
 
# [[Дерево, эквивалентные определения]]
 
# [[Дополнительный, самодополнительный граф]]
 
# [[Дополнительный, самодополнительный граф]]

Версия 22:14, 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. Дополнительный, самодополнительный граф

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

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

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

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

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

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

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

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

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

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

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

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

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