Kolloc

Question 1

1. Дерево(два определения)

Answer 1

• связный ациклический граф
• граф, любые две вершины которого соединены единственным простым путём
• связный граф, у которого вершин на одну меньше, чем рёбер
  …

Question 2

2. Граф блоков-точек сочленения

Answer 2

двудольный граф, к одной доли которого относятся блоки графа, каждый из которых стянут в одну вершину, а к другой доли относятся все точки сочленения графа, при этом между точкой сочленения и стянутым блоком есть ребро, если точка сочленения принадлежала этому блоку

Question 3

3. Граф компонент рёберной двусвязности

Answer 3

граф, вершинами которого являются компоненты рёберной двусвязности исходного графа, соединённые мостами исходного графа

Question 4

4. Остов графа

Answer 4

частичный граф данного графа, являющийся деревом

Question 5

5. Цикломатическое число

Answer 5

число, показывающее, сколько рёбер надо удалить из графа, чтобы получился остов

Question 6

6. Фундаментальная система циклов

Answer 6

множество циклов графа, ассоциированное с остовом

Question 7

7. Минимальное остовное дерево графа

Answer 7

остов этого графа, обладающий минимальным суммарным весом рёбер

Question 8

8. Безопасное ребро

Answer 8

ребро, при добавлении которого к подграфу некого МСТ графа, граф остаётся подграфом некого МСТ этого графа, причём данное ребро не должно принадлежать изначальному подграфу МСТ

Question 9

9. Разрез, Ребро, пересекающее разрез

Answer 9

Разрез – разбиение множества вершин графа на два не пересекающихся подмножества.
Ребро, пересекающее разрез – ребро, один конец которого при разрезе принадлежит одному подмножеству вершин, а второй конец другому подмножеству

Question 10

10. Лемма о безопасном ребре

Answer 10

если взять такой разрез, что все вершины подграфа некоторого мст принадлежат одной части, то минимальное ребро, пересекающее этот разрез будет безопасным ребром

Question 11

11. Диаметр графа

Answer 11

максимальный эксцентриситет среди всех вершин графа, где эксцентриситет вершины – это кратчайшее расстояние в рёбрах до вершины, наиболее удалённой от данной

Question 12

12. Центр графа

Answer 12

множество всех вершин с минимальным эксцентриситетом

Question 13

13. Радиус графа

Answer 13

минимальный эксцентриситет среди всех вершин графа, где эксцентриситет вершины – это кратчайшее расстояние в рёбрах до вершины, наиболее удалённой от данной

Question 14

14. Теорема о поиске числа путей заданной длины по матрице смежности орграфа

Answer 14

число путей из iой вершины в jую длины L равно значению в ij ячейке матрицы смежности, возведённой в степень L

Question 15

15. Лемма о белых путях

Answer 15

запустим дфс на графе, назовём первым моментом времени, момент когда дфс выполнялся от некоторой вершины v, когда она окрашена в серый цвет, вторым моментом времени назовём момент, когда вершина v стала чёрной, тогда вершины графа кроме вершины v, которые были серые и чёрные к 1му моменту не изменят цвет ко второму моменту, а белые вершины либо останутся белыми, либо станут чёрными, причём Чёрными станут те, что были достижимы из v по белым путям

Question 16

16. Эйлеров путь

Answer 16

путь, единожды проходящий по каждому ребру графа

Question 17

17. Эквивалентные определения эйлерова графа

Answer 17

• граф, содержащий Эйлеров цикл
• граф, любая вершина которого имеет чётную степень
• граф, множество всех рёбер которого можно разбить на циклы

Question 18

18. Теорема о покрытии рёбер графа путями

Answer 18

если в графе 2N вершин имеют нечётную степень, то этот граф можно покрыть N рёберно-простыми путями

Question 19

19. Критерий эйлеровости

Answer 19

граф Эйлеров тогда и только тогда, когда:

• все вершины графа имеют чётную степень
• все компоненты связности кроме, (может быть)? одной, не содержат рёбер

Question 20

20. Произвольно вычерчиваемый граф

Answer 20

20. Граф называется произвольно вычерчиваемым из вершины v, если любая цепь с началом в v может быть продлена до эйлерова цикла данного графа

Question 21

21. Гамильтонов путь

Answer 21

путь, единожды проходящий через каждую вершину графа

Question 22

22. Теорема Оре

Answer 22

если в неориентированном графе не меньше 3 вершин и для любых двух различных несмежных вершин выполняется то, что сумма их степеней не меньше количества вершин, то данный граф гамильтонов

Question 23

23. Теорема Дирака

Answer 23

если в неориентированном графе не меньше 3 вершин и минимальная степень его вершин не меньше количества вершин, делённого на два, то граф гамильтонов

Question 24

24. Теорема Гуйя-Ури

Answer 24

если в сильно связанном ориентированном графе для каждой вершины её степени входа и выхода не меньше числа вершин, делённого на два, то граф гамильтонов

Question 25

25. Сочетание

Answer 25

Сочетание из n по m – набор размера m из n элементов

Question 26

26. Размещение

Answer 26

Размещение из n по m – упорядоченная последовательность длины m из n элементов

Question 27

27. Перестановка

Answer 27

Перестановка - переупорядочение набора объектов или функция его задающая

Question 28

28. Отличие перестановок и размещений

Answer 28

размещения кроме порядка объектов, могут отличаться набором этих объектов

Question 29

29. Принцип Дирихле

Answer 29

если поместить n + 1 объект в n контейнеров, то по крайней мере в одном контейнере будет более одного объекта

Question 30

30. Кратчайший путь

Answer 30

путь с наименьшей возможной суммой весов рёбер

Question 31

31. Транспортная сеть

Answer 31

ориентированный граф, где каждое ребро данного графа имеет пропускную способность, большую нуля, и нет антипараллельных рёбер; если данное ребро не входит в граф, его пропускная способность полагается равной 0

Question 32

32. Поток

Answer 32

функция, которая возвращает рациональное значение для пары вершин сети и удовлетворяет условиям:

• Ограничение пропускной способности, т.е. для любой пары вершин в сети поток между ними не меньше 0 и не больше пропускной способности
• Сохранение потока, т.е. для любой вершины, кроме начальной и конечной, суммарный поток выходящий из неё будет равен суммарному потоку в неё входящему

Question 33

33. Величина потока

Answer 33

разность суммарного потока, который вытекает из стартовой вершины и суммарного потока, который в неё втекает

Question 34

34. Остаточная сеть

Answer 34

сеть, состоящая из тех же вершин, что и исходная сеть и из рёбер, через которые можно допустить поток

Question 35

35. Увеличивающий путь

Answer 35

простой путь из истока в сток в остаточной сети

Question 36

36. Минимальный разрез сети

Answer 36

разрез с минимально возможной пропускной способностью

Question 37

37. Паросочетание в двудольном графе

Answer 37

произвольное подмножество рёбер двудольного графа, такое что никакие два ребра не смежны

Question 38

38. Конденсация графа

Answer 38

орграф граф, вершинами которого служат компоненты сильной связности исходного графа, а дуга между ними присутствуют только когда в исходном графе существует хотя бы одна дуга между вершинами, входящими в эти компоненты связности

Question 39

39. Топологическая сортировка

Answer 39

упорядочивание вершин ориентированного ацикличного графа такое, что если есть дуга из v в u, то номер вершины v меньше номера вершины u

Question 40

40. Префикс-функция

Answer 40

максимальный по длине собственный префикс строки, являющийся её суффиксом