Теория графов

его применения
Задачи:
рассмотреть основные определения;
сформулировать и доказать основные теоремы,

2) виды графов;
II. Основные леммы и

точек и соединяющих их линий. Точки называются вершинами. Стороны -

DС и CA, CD и DB, DB и BA, BA

вершина называется изолированной, если она не является концом ни для одного ребра

является концевой (петли считать дважды)
Обозначение: deg(A).
deg(E) = 0
deg(C) = 2
E

deg(G) = 1
deg(H) = 1
deg(E) = 1
deg(B) = 1
deg(A) = 1
deg(C) = 4
deg (D) = 2

G, H, E, B, A - висячие вершины

Определения

Пример:

вершин равна удвоенному числу ребер

В любом графе число вершин нечетной степени четно

Следствие

степенью вершины называют количество ребер, для которых она является концевой (петли считать дважды)

|=>
(по определению степени вершины)
ч.т.д

каждое ребро инцидентно двум вершинам, в сумму степеней вершин графа

из каждого города выходит 3 дороги быть ровно 100 дорог

Ответ:

Решение:
Города – вершины графа (k, kєN ). Степень кратности каждой вершины 3 =>

Дороги – ребра графа (p = 100)
По Лемме 3k = 2p. Если р = 100, то k =
Но kєN => p ≠ 100

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

Граф, в которых не построены все возможные ребра, называют неполным графом.

L

U

B

O

V

если степени всех вершин графа равны, то граф называется

Виды графов

направление. Это означает, что в орграфе некоторая вершина может быть

Граф называется неориентированным, если ни одно из ребер не имеет направление.

ребер, для которых эта вершина является концом (началом)
Степень входа вершин

Орграф

Степень выхода вершин графа:

такой граф называется связным
B
C
D
связный граф
не связный граф

любой вершины этого множества есть путь в любую другую вершину

Определения

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

Пример:

граф с 10 компонентами

не менее , связен.
Рассмотрим вершины

Решение:

Пример:

1

1

A

B

степень 1
Подграфом графа G называется граф, у которого все вершины

Определения

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

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

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

которой каждые два соседних ребра имеют общую вершину и никакое

Пример:
1) (А1 А4); (А4 А5)
2) (А1 А2); (А2 А4); (А4 А5).
3) (А1 А4); (А4 А2); (А2 А1); (А1 А3); (А3 А4); (А4, А5).
4) (А1 А4); (А4 А2); (А2 А1); (А1 А3); (А3 А5);

путь

Определения

1

2

3

4

5

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

Определения

Пример:

Циклы состоящие из 4 ребер:
(AB, BC, CE, EA), (CD, DA, AB, BC)
(DA,AB,BE, EC, CA, AE, ED)

Простые циклы: (EB, BC, CD, DE) и т.д.

можно разбить на множества Х и У таких, что каждое

Определения

Х

Y

содержит более одной вершины и все его циклы имеют четную

Задача о деревенских свадьбах
Назначение на должность: имеются вакантные

Выбор представителей: в парламенте есть несколько комиссий, член парламенты может заседать в нескольких комиссиях; нужно выбрать председателя каждой комиссии

Пример:

юношей. Некоторые юноши знакомы с некоторым девушками. Требуется поженить максимально

Пример:

G можно рассмотреть как функцию, отображающую каждую вершину из Х

X1

X2

X3

X4

X5

X6

Y5

Y4

Y3

Y2

Y1

Дан двудольный граф с долями X и Y. Совершенное паросочетание существует тогда и только тогда когда |Х| = |Y| и |O(M)| ≥ |M| для всякого M X

|Y| = n и выполнено условие (1). Докажем что в

связный граф, имеющий все четные вершины

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

Если граф G(V,E) обладает эйлеровым циклом, то он связный и все его вершины четные.

Теорема №1

Теорема №2 (Эйлер)

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

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

Пример:
гамильтонов путь:
(C, D, A, B, M);
(B, A, D, C, F)

не является гамильтоновым графом. Будем добавлять к нему новые ребра

Теорема (Оре)

Доказательство:

Пусть дан обыкновенный связный граф, содержащий n > 2 вершин, такой что сумма степеней любых двух несмежных вершин не меньше, чем n. Тогда граф гамильтонов.

его можно изобразить так, чтобы все пересечения его ребер являются

первоначальный
граф

изображенный иначе

Грань в плоском представлении графа называется часть плоскости, ограниченная простым циклом и не содержащая внутри других циклов.
Пример: (BAC), (CAE), (CDE)

ребрами. Для ориентированного мультиграфа вершины могут соединятся несколькими ребрами в

Мультиграф

A

B

C

Псевдографом называется граф, в котором есть и петли и кратные ребра

A

C

B

менее, чем с 68 другими. Докажите, что среди них найдутся

1) пусть верно обратное.
2) тогда для каждого числа от 68 до 101 имеется не более трех человек, имеющих такое же число знакомых.
3) имеется ровно 34 натуральных числа, начиная с 68 и заканчивая 101, а 102 = 3 ∙ 4. Это означает что для каждого числа от 68 до 101 есть ровно три человека, имеющие такое число знакомых
4) Но тогда количество людей, имеющих нечетное количество знакомых нечетно. (Л) | => верно обратное, т.е. среди учеников найдутся четверо, имеющие одинаковое число знакомых

Решение:

Пример:

и двух островах на этой реке. Части города соединены мостами.

Задача о кёнигсберских мостах

граф пройдя по каждому ребру ровно один раз и вернуться

любые два соседних ребра имеют общую вершину;

последнее ребро имеет общую вершину с первым;

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

G2
Объединением графов

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

V и отображение Е множества V в V. Отображение Е

Способы задания графов