Графы. Теория графов

Содержание

Слайд 2

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

Для доказательства того, что задача не имеет решения, Эйлер обозначил каждую часть
суши точкой (вершиной), а каждый мост - линией (ребром), соединяющий соответствующие точки. Получился «граф». Он показан на рис. 1.1.2, где точки отмечены теми же буквами, что и четыре части суши на рис. 1.1.1.
Утверждение о не существовании «положительного» решения у этой задачи эквивалентно утверждению о невозможности обойти специальным образом граф, представленный на рис. 1.1.2

Рис. 1.1.1 Рис. 1.1.2

Слайд 3

Для знакомства с понятием графа рассмотрим несколько наглядных задач.
Задача 1. В государстве

Для знакомства с понятием графа рассмотрим несколько наглядных задач. Задача 1. В
Морляндия находятся 8 крупных островов, некоторые из которых
соединены радиосвязью. Связь есть между следующими островами:
Банановый – Кокосовый;
Кукуру – Рыбный;
Столичный – Акулий;
Птичий – Кукуру;
Одинокий – Столичный;
Акулий – Одинокий;
Столичный – Кокосовый;
Птичий – Рыбий.
Можно ли послать сообщение с острова Банановый на остров Акулий? А с острова Акулий на
Рыбный?

Решение. Нарисуем схему радиосвязи. Острова обозначим точками (вершинами), радиосвязь линиями (ребрами). Из схемы видно, что с острова Банановый на остров Акулий послать сообщение, а с острова Акулий на Рыбный – нет. Отсюда делаем вывод:

Слайд 4

Граф - это множество точек или вершин и множество линий или ребер,

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

Рис. 1. Граф с шестью вершинами и семью ребрами

Понятие графа

Слайд 5

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

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

Элементы графа

Слайд 6

Нулевой граф

Граф, состоящий из «изолированных» вершин, называется нулевым графом

Рис. 2. Нулевой граф

Нулевой граф Граф, состоящий из «изолированных» вершин, называется нулевым графом Рис. 2. Нулевой граф

Слайд 7

Неполный граф

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

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

Рис. 3. Неполный граф

Слайд 8

Степень графа

Количество рёбер, выходящих из вершины графа, называется степенью вершины. Вершина графа,

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

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

Слайд 9

Заметим, что если полный граф имеет n вершин, то количество ребер равно

Заметим, что если полный граф имеет n вершин, то количество ребер равно

n(n-1)/2

Задание 1. Существует ли полный граф с семью ребрами?

Решение: Зная количество ребер, узнаем количество вершин.
n(n-1)/2=7.
n(n-1)=14.
Заметим, что n и (n-1) – это два последовательных натуральных числа. Число 14 нельзя представить
в виде произведения двух последовательных натуральных чисел, значит, данное уравнение не имеет решений. Следовательно, такого графа
не существует.

ОТВЕТ

Слайд 10

Примеры полных графов

Задание 2.Построить полный граф для 5 вершин.

Примеры полных графов Задание 2.Построить полный граф для 5 вершин.

Слайд 11

Ориентированный граф

Граф называется ориентированным (или орграфом), если некоторые ребра имеют направление. Это

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

Рис. 4. Ориентированный граф

Слайд 12

Рис. 5. Примеры неориентированного
и ориентированного графов (А и Б)

Ориентированный и неориентированный

Рис. 5. Примеры неориентированного и ориентированного графов (А и Б) Ориентированный и неориентированный графы
графы

Слайд 13

Задание. Построить граф по заданному условию:

В соревнованиях по футболу участвуют 6 команд.

Задание. Построить граф по заданному условию: В соревнованиях по футболу участвуют 6
Каждую из команд обозначили буквами А, B, C, D, E и F. Через несколько недель некоторые из команд уже сыграли друг с другом:

A с C, D, F; B c C, E, F; С с A, B; D с A, E, F; E с B, D, F; F с A, B, D.

ОТВЕТ

Слайд 14

Не следует путать изображение графа с собственно графом (абстрактной структурой), поскольку одному

Не следует путать изображение графа с собственно графом (абстрактной структурой), поскольку одному
графу можно сопоставить не одно графическое представление. Изображение призвано лишь показать, какие пары вершин соединены рёбрами, а какие — нет.

Запомнить!

Слайд 15

Изображение графа

Один и тот же граф может выглядеть на
рисунках по-разному. На

Изображение графа Один и тот же граф может выглядеть на рисунках по-разному.
рисунке 6 (а, б, в) изображен один и тот же граф.

Рис. 6. Примеры изображения графа

Слайд 16

Задание 4.

Определить изображают ли фигуры на рисунке один и тот же

Задание 4. Определить изображают ли фигуры на рисунке один и тот же
граф или нет.

1)

2)

3)

ОТВЕТ

Рисунок 1 и рисунок 2 являются изображениями одного графа. Рисунок 3 изображением
другого графа

Слайд 17

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

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

Путь в графе

Слайд 18

Задание 5.

(А1 А4); (А4 А5).
(А1 А2); (А2 А4); (А4 А5).
(А1

Задание 5. (А1 А4); (А4 А5). (А1 А2); (А2 А4); (А4 А5).
А4); (А4 А2); (А2 А1); (А1 А4); (А4, А5).
(А1 А4); (А4 А2); (А2 А1); (А1 А3); (А3 А4); (А4, А5).

Определить какая из перечисленных последовательностей путём не является.

ОТВЕТ

Третья последовательность (А1 А4); (А4 А2); (А2 А1); (А1 А4); (А4, А5).

Слайд 19

Путь называется простым, если он не проходит ни через одну из вершин

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

(А1 А4); (А4 А5).
(А1 А2); (А2 А4); (А4 А5).
(А1 А4); (А4 А2); (А2 А1); (А1 А4); (А4, А5).
(А1 А4); (А4 А2); (А2 А1); (А1 А3); (А3 А4); (А4, А5).

Задание 6.

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

Первая, вторая и четвертая последовательности являются путями, а третья нет, т.к. ребро (А1, А4) повторяется. Первая и вторая последовательность являются простыми путями, а четвертая нет, т.к. вершины А1 и А4 повторяются.

ОТВЕТ

Слайд 20

Понятие цикла в графе

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

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

Слайд 21

a) 4 ребра; b) 6 ребер; c) 5 ребер; d) 10 ребер.

a) 4 ребра; b) 6 ребер; c) 5 ребер; d) 10 ребер.
Какие из этих циклов являются простыми?

Задание 7.

Назовите в графе циклы, содержащие

ОТВЕТ

Слайд 22

ОТВЕТ

(AB, BC, CE, EA), (CD, DA, AB, BC), (EB, BC, CD, DE)

ОТВЕТ (AB, BC, CE, EA), (CD, DA, AB, BC), (EB, BC, CD,
и т.д. – простые циклы.
(DB, BE, EA, AB, BC, CD), (EC, CA, AB, BC, CD, DE) и т.д. – циклы.
(AB, BC, CD, DE, EA), (AC, CE, EB, BD, DA) и т.д. – простые циклы.
(AC, CE, EB, BD, DA, AB, BC, CD, DE, EA), (EB, BD, DA, AC, CE, EA, AB, BC, CD, DE) и т.д. – циклы.

Решение:

Слайд 23

Теория графов нашла свое применение и в архитектуре и строительстве.
При составлении

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

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

Имя файла: Графы.-Теория-графов.pptx
Количество просмотров: 37
Количество скачиваний: 0