Презентация, доклад на тему Кратчайший путь в графе

Какой метод объединяет данные задачи?

Задачи:

рассмотреть основные определения;
сформулировать и доказать основные теоремы, в т.ч. лемму «о рукопожатиях» , теоремы Кёнига, Оре, Холла

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

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 - висячие вершины

Определения

Пример:

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

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

Следствие

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

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

Ответ: не может

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

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

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

L

U

B

O

V

Виды графов

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

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

Орграф

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

B

C

D

связный граф

не связный граф

Определения

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

Пример:

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

Рассмотрим вершины A и B, не соединенные путем.
Вершина А соединена не менее чем с вершинами,
Вершина B также соединена не менее чем с (по условию)
Вершина А отлична от В ( иначе между ними существует путь)
Тогда в графе 1+1+ + вершин, то есть n+1.
Но по условию всего n вершин. Мы пришли к противоречию |=>
вершины соединены путем => граф связен. ч.т.д.

Решение:

Пример:

1

1

A

B

Подграфом графа G называется граф, у которого все вершины и ребра принадлежат 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

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

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

Пример:

Пример:

X1

X2

X3

X4

X5

X6

Y5

Y4

Y3

Y2

Y1

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

Если граф 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

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

Решение:

Пример:

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

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

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

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

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

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