Graphs

Question 1

Граф

Answer 1

Графом называется упорядоченная пара (V, E), где V — непустое множество вершин, E — множество рёбер (множество парных связей.

(n, m)-графом называется граф, содержащий n вершин и m рёбер.

Порядок графа — число его вершин.

Question 2

Смежные вершины и рёбра графа

Answer 2

Две вершины u и v называются смежными ( u ~ v ), если uv является ребром.
Рёбра e1, e2 называются смежными, если они имеют общий конец, то есть их пересечение не пусто.

Question 3

Инцидентные вершина и ребро

Answer 3

Вершина v и ребро e называются инцидентными, если вершина принадлежит ребру

Question 4

Окружение вершины v

Answer 4

Множество вершин х из V, таких, что vx — ребро.
Окружение — множество вершин, смежных с заданной.

Question 5

Степень вершины

Answer 5

Степенью вершины v называется мощность множества ее окружения.
deg(v) = | N(v) |

Question 6

Изолированная, концевая, доминирующая вершина

Answer 6

Вершина называется изолированной, если её степень равна 0. Вершина называется концевой, если её степень равна 1. Вершина называется доминирующей, если она смежна си всеми остальными вершинами.

Question 7

Лемма о рукопожатиях и её следствие

Answer 7

Лемма: Сумма степеней вершин произвольного графа является четным числом и равна удвоенному числу рёбер графа.
Следствие: в произвольном графе число вершин с нечётными степенями является чётным числом

Question 8

Полный, пустой, помеченный граф

Answer 8

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

Question 9

Равные графы

Answer 9

Если граф G = H, то E(G) = E(H) и они помечены одинаковыми метками.

Question 10

Изоморфные графы

Answer 10

Графы G и H называются изоморфными, если существует биекция Y : V(G) — V(H) и для любых смежных вершин u,v эта биекция сохраняет их смежность

Question 11

Связный граф

Answer 11

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

Question 12

Связная компонента графа

Answer 12

Связной компонентой графа называется всякий максимальный относительно включения связный подграф

Question 13

Маршрут в графе

Answer 13

Чередующаяся последовательность вершин и рёбер (v1, e1, v2, e2…), в которой любые два соседних элемента инцидентны.

Question 14

Цикл

Answer 14

Замкнутая цепь

Question 15

Свойства маршрутов

Answer 15

1) Если вершины u != v, то любой (u,v) маршрут содержит в себе простую (u,v) цепь
2) Всякий цикл содержит с себе простой цикл
3) Объединение двух несовпадающих простых цепей содержит простой цикл

Question 16

Подграф

Answer 16

Граф H называется подграфом G, если V(H) содержится в V(G) и E(H) содержится в E(G)

Question 17

Разновидности маршрутов

Answer 17

1) Цепь (маршрут, который не содержит повторяющихся рёбер)
2) Простая цепь (маршрут, который не содержит повторяющихся вершин, кроме крайних)
3) Замкнутый маршрут (начало и конец совпадают)

Question 18

Теорема 2 о числе компонент

Answer 18

Пусть | G | = n, k(G) = k — число компонент, тогда выполняется неравенство:
n - k не превосходит (n-k+1)(n-k)/2

Question 19

Двудольный граф

Answer 19

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

Question 20

Расстояние между вершинами графа

Answer 20

Пусть G — связный граф, тогда расстоянием между его вершинами u и v называется величина d(u,v), равная минимальной длине из (u,v)-маршрутов

Question 21

Теорема 3 (о волновом алгоритме)

Answer 21

Пусть G — связный граф, обработанный волновым алгоритмом с начальной вершиной uo. Тогда метка l(u) = d(uo, v) для любого v из V

Question 22

Полный двудольный граф

Answer 22

Граф G(A,B) называется полным двудольным, если каждая вершина из A смежна с каждой вершиной из B.

Question 23

Самодополнительный граф

Answer 23

Граф называется самодополнительным, если он изоморфен своему дополнению

Question 24

Теорема Кёненга

Answer 24

Граф является двудольным тогда и только тогда, когда он не содержит циклов нечётной длины

Question 25

Следствие (критерий двудольности)

Answer 25

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

Question 26

Дерево, лес

Answer 26

Деревом называется связный граф, не содержащий циклов. Лес — неориентированный граф без циклов. Компонентами связности леса являются деревья

Question 27

Остовное дерево

Answer 27

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

Неформально говоря, остовное дерево получается из исходного графа удалением максимального числа рёбер, входящих в циклы, но без нарушения связности графа. Остовное дерево включает в себя все n вершин исходного графа и содержит n-1 ребро.

Question 28

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

Answer 28

m - n + k, где n = | G |, m = | E(G) |, k = k(G)

Question 29

Теорема Кирхгофа

Answer 29

Число остовных деревьев в связном помеченном графе порядка n >= 2 равно алгебраическому дополнению произвольного элемента матрицы Кирхгофа

Question 30

Абстрактные графы

Answer 30

Графы, которые различаются в точности до изоморфизма