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

1.

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

2.

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

3.

Основные понятия графа
Направленная линия (со
стрелкой) называется дугой.
Линия ненаправленная (без
стрелки) называется ребром.
дуга
А
ребро
петля
Линия, выходящая из
некоторой вершины и
входящая в неё же,
называется петлей.
В
С

4.

Немного истории
Первая работа по теории графов была
написана еще в 1736 году Леонардом
Эйлером. (>>>)
Впервые понятие «граф» ввел в 1936 году
венгерский математик Денеш Кёниг.

5.

Виды графов

6.

1. Неориентированный граф
Пример: Пятеро друзей пишут письма друг другу.
Отношения двухсторонние, поэтому вершины соединены
ребрами.
Юра
Аня
Маша
Витя
Коля
Граф называется неориентированным, если
его вершины соединены ребрами.

7.

Задача 1
Аркадий, Борис, Владимир, Григорий и
Дмитрий при встрече обменялись
рукопожатиями (каждый пожал руку каждому
по одному разу). Сколько всего рукопожатий
было сделано?

8.

А
Д
Б
Ответ: 10
Г
В

9.

2. Ориентированный граф
Ориентированный граф - граф, вершины которого
соединены дугами.
С помощью таких графов могут быть представлены схемы
односторонних отношений.

10.

3. Взвешенный граф
Взвешенный граф – это граф, у которого вершины или
рёбра (дуги) несут дополнительную информацию (вес).
182
127
158
Москва, 1147
Владимир, 1108
Переславль Залесский, 1152

11.

4. Семантическая сеть
Граф с циклом называют сетью
ИванЦаревич
пусти
л
наше
л
Стрела
прилетела
сжег
Лягушка
превратилась
сбросил
а
указала
Баба Яга
наше
л
победил
Лягушачья
кожа
Василиса
Прекрасная
Кощей
Бессмертный
Лебедь
превратилась
улетела

12.

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

13.

Укажите корневую
вершину, объекты 1го, 2-го и 3-го уровней

14.

Решение задач
с помощью графов

15.

Задача 2

16.

Задача 3
На рисунке — схема дорог, связывающих города А, Б, В,
Г, Д, Е, Ж, К. По каждой дороге можно двигаться только в
одном направлении, указанном стрелкой. Сколько
существует различных путей из города А в город К?
А
Б
В
Г
Е
Ж
Д
К

17.

Задача 3 (решение)
А
Б
В
Г
Б
Е
Ж
2-К
Ж
К
Ответ: 7
К
К
Ж
К
Г
Д
Е
Е
Д
Д
Ж
К
Б
В
Д
Е
А
Е
Ж
К

18.

Задача 4

19.

Задача 4
(решение)
А
F
4
5
В
6
6
4
С
3
ABEF = 15
ABCEF = 19
ABDEF = 14
E
2
Ответ: 14
D

20.

Задача № 5
Для составления цепочек используются бусины,
помеченные буквами: А, В, С, D, Е. На первом месте в
цепочке стоит одна из бусин А, С, Е. На втором — любая
гласная, если первая буква согласная, и любая согласная,
если первая гласная. На третьем месте - одна из бусин С,
D, Е, не стоящая в цепочке на первом месте. Сколько
цепочек можно создать по этому правилу?

21.

Задача 5 (решение)
Для составления цепочек используются бусины, помеченные буквами:
А, В, С, D, Е. На первом месте в цепочке стоит одна из бусин А, С, Е. На
втором — любая гласная, если первая буква согласная, и любая
согласная, если первая гласная. На третьем месте - одна из бусин С,
D, Е, не стоящая в цепочке на первом месте. Сколько цепочек можно
создать по этому правилу?
О
А
B
C
E
Ответ: 19
А
C
D
D
B
D
C
C
E
C
E
C
D
E
E
D
E
C
E
C
C
D
D
D
D
D

22.

Проверь себя

23.

№ 8. На рисунке - схема дорог,
связывающих города А, Б, В, Г, Д, Е, Ж. По
каждой дороге можно двигаться только в
одном направлении, указанном стрелкой.
Сколько существует различных путей из
города А в город Ж?

24.

№ 9. Между населёнными пунктами A, B, C,
D, E построены дороги, протяжённость
которых приведена в таблице. (Отсутствие
числа в таблице означает, что прямой
дороги между пунктами нет).Определите
длину кратчайшего маршрута из А в B.