Граф, ребра и вершины (7 класс)

1. Шестое февраля Классная работа Граф, ребра и вершины

1 из 15

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

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

3. Изображение вершин

3 из 15

4.

Графы
Неориентированные
Ориентированные
- графы, вершины которых
соединены ребрами
- графы, вершины которых
соединены дугами
С помощью таких графов
могут быть представлены
схемы двухсторонних
(симметричных) отношений.
С помощью таких графов
могут быть представлены
схемы односторонних
отношений.
4 из 15

5.

Пример
Неориентированного
графа
Юра
Ориентированного
графа
Юра
Аня
Аня
Маша
Маш
а
Коля
Витя
Граф, отражающий отношение
«переписываются» между
объектами класса «дети»
Коля
Витя
Граф, отражающий
отношение
«пишет письма»
5 из 15

6. - граф, у которого вершины или рёбра (дуги) несут дополнительную информацию (вес).

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

7.

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

8. Семантическая сеть

ИванЦаревич
Стрела
Баба
Яга
Лягушачья
кожа
Лягушка
Лебедь
Кощей
Бессмертный
Василиса
Прекрасная
8 из 15

9. Иерархия

- это расположение частей или элементов
целого в порядке от высшего к низшему
Директор
Заместители директора
Учителя
Ученики
Отношения подчиненности в школе
9 из 15

10. Дерево

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

11.

Корень – главная вершина дерева
Предок – объект верхнего уровня
Потомок – объект нижнего уровня
Листья – вершины, не имеющие потомков
Олимпийская система спортивных соревнований
Чемпион
Финалисты
Участники ½
финала
Участники ¼
финала
Первоначальные игроки
11 из 15

12. Файловая структура

12 из 15

13. Домашнее задание: Ответить на вопросы(письменно): 1. Графом называется… 2. Точки графа называются… 3. Линии графа называются…

4. Ребра называются смежными, если они...
5. Ребро, имеющее совпадающие начало и
конец, называется…
13 из 15