Графы. 8 класс

1.

2.

Графы
• Граф отображает элементный состав
системы и структуры связей.

3.

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

4.

Неориентированный граф
граф, вершины которого соединены ребрами.
С помощью таких графов могут быть
представлены
схемы
двухсторонних
(симметричных) отношений.
По графу определите кто с кем переписывается:
Юра
Аня
Маша
Коля
Витя

5.

Ориентированный граф
граф, вершины которого соединены дугами. С
помощью
таких
графов
могут
быть
представлены
схемы
односторонних
отношений.
В чем отличие данного графа от предыдущего
Юра
Аня
Маша
Коля
Витя

6. Графы

Цепь, цикл, сеть
Цепь – путь по вершинам и ребрам,
включающий любое ребро графа не более
одного раза..
Цикл – цепь, начальная и конечная вершины
которой совпадают
Сеть - граф с циклом
Укажите на графе цепь и цикл:
Аня – Юра-Маша
Юра
Аня
Маша
Аня-Витя-Коля-Аня
Коля
Витя

7. Состав графа

Взвешенный граф
граф, у которого вершины или рёбра (дуги) несут
дополнительную информацию (вес).
3
Юра
10а
1
Маша
10в
Аня
10а
5
4
2
Коля
10в
3
Витя
10б

8. Неориентированный граф

Пример 1
• Информация о
некотором реальном
объекте может быть
представлена по
разному. В разговорной
речи мы используем
словесное описание
некоторой местности
• Наш город состоит
из 6 районов:
• Фрунзенский
• Кировский
• Ленинский
• Красноперекопский
• Дзержинский
• Заволжский.

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

• Прямые дороги расположены следующим
образом:
• Кировский – Заволжский;
• Фрунзенский – Красноперекопский;
• Кировский – Заволжский;
• Дзержинский – Ленинский;
• Фрунзенский – Кировский;
• Дзержинский – Заволжский;
• Ленинский – Кировский.

10. Цепь, цикл, сеть

Такая схема называется - ГРАФОМ
Дз
л
З
Ки
Кр
Ф

11. Взвешенный граф

Пример 2
Ярославль
Дзержинский
Кировский
Красноперекопский
Заволжский
Ленинский
Фрунзенский

12. Пример 1

Неориентированный граф
Цикл: Дз-З-Ки-Л-Дз
Цепь: Ф-Ки-З-Дз-Кр
Дз
л
Ки
Кр
Ф
З

13.

Ориентированный граф
Цикл: З-Ки-Л-Дз
Цепь: Ф-Ки-Л-Дз-Кр
Найти наименьшее расстояние на участке У-П
а) З-Ки-Л-Дз-Кр б) З-Дз-Кр
Дз
25
4
15
л
1
З
Ки
12
Кр
7
Ф

14. Такая схема называется - ГРАФОМ

Пример 3
Смысловая структура фраз
• Определим структуру фразы
«С утра на улице шёл тёплый грибной дождь»
с утра
Когда?
шёл
Где?
на улице
Кто?\Что?
Что делал?
дождь
Какой?
тёплый
Какой?
грибной
Если в вершинах графа заменить члены на другие
родственные слова, то снова может получится
осмысленная фраза.

15. Пример 2

Пример 4
Смысловая структура фраз
• Представьте в виде графа связи в следующих
предложениях:
«Однажды в студеную зимнюю пору я из лесу вышел….»
Однажды в пору
Когда?
Какую?
студёную
Какую?
зимнюю
Кто?\Что?
вышел
я
Что делал?
Откуда?
из лесу

16. Неориентированный граф

Смысловая структура фраз
• Представьте в виде графа связи в следующих
предложениях:
«Четыре чёрненьких чумазеньких чертёнка чертили
чёрными чернилами чертёж черепа человека чрезвычайно
чётко на чердаке в четверг.

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

Смысловая структура фраз
человека
Кого?
черепа
Чего?
четыре
чёрных
Сколько?
чертёнка
чертёж
Каких?
Кто?
Что делали?
Как?
чрезвычайно
Что?
Как?
чётко
Когда?
чертили
Чем?
чернилами
в четверг
Где?
на чердаке

18. Пример 3

Решение задач
Между населенными пунктами A,B, C,D, Е построены
дороги, протяженность которых указана в таблице.
Определите длину кратчайшего пути между пунктами
AиD
A
A
B
B
C
3
D
4
3
2
C
D
E
E
1
4
2
4
1
4
Варианты
ответов:
1. 9
2. 8
3. 12
4. 15

19. Пример 4

Для решения задачи построим граф:
Возможны 2 пути: 1) А – В – Д - Е; 2)А – Д - Е
В
А
3
2
D
4
4
С
1
E