8SiTV_B_20_prezentatsia

1.

Дерево

2.

Что объединяет эти изображения?

3.

Граф
Графом называется множество точек, некоторые из которых
могут быть соединены линиями. Точки называются
вершинами графа, а линии, которые их соединяют –
ребрами. Например, В и Е – это вершины, а ВС и АВ – это
ребра. Заметим, что ВС и СВ это одно и то же ребро, если
граф неориентированный.

4.

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

5.

Граф
Два графа считаются одинаковыми, если они имеют
одинаковое множество вершин и одинаковое множество
рёбер, и эти рёбра соединяют те же самые вершины в обоих
графах.

6.

Пример 1
Рассмотрим знакомую нам ситуацию – турнир по шахматам.
Каждый шахматист, должен провести игру с остальными 4
игроками. Сколько всего матчей будет сыграно? При помощи
графа можно изобразить пары игроков и легко определить
количество матчей.
Всего будет 11 матчей, так как вершины графа изображают
игроков, а ребра – партии между ними.

7.

Пример 2
Деревни соединены реками следующим образом: Малиновка
– Поповка, Березовка – Сосновка, Громово – Поповка,
Тимуровка – Кедрово, Березовка – Малиновка, Зайцево –
Тимуровка, Громово – Березовка. Других реки не соединяют
эти деревни. Можно ли добравться вплавь из Малиновки в
Громово? Если да, то сколько
для этого есть способов?
Можно ли добраться вплавь из
Громово в Кедрово? Если да,
то сколько для этого есть
способов?

8.

Примеры
Базы данных
Обобщенная структура
телекоммуникационной
сети
Транспортные сети региона

9.

Задание 1
На рисунке изображен граф. Перечислите его
вершины и ребра. Назовите две пары
смежных вершин и две пары смежных ребер.

10.

Задание 2
На рисунке изображен граф. Перечислите все
пары смежных вершин. Перечислите все
пары
смежных
ребер.
Назовите
изолированные точки.

11.

Задание 3
Среди графов, изображенных на рисунке,
найдите пары одинаковых.

12.

Задание 4
На рисунке изображена
карта районов Петрограда
в период с 1917 по 1919 гг.
Изобразите
граф,
обозначив
районы
вершинами, а сухопутные
границы между районами –
ребрами. Считайте, что
мосты
не
считаются
сухопутными границами.
Каково в этом графе
количество изолированных
вершин?

13.

Путь
Путем в графе от вершины А до вершины F
называется последовательность ребер графа и его
вершин, такие, что каждые два последовательных
ребра имеют общую вершину, и никакое ребро не
встречается более одного раза. А называется началом
пути, F – концом. Вершины повторяться могут.
Например, ABCDECF
и ABCEDCF – пути
от точки А к точке F.

14.

Цепь и цикл
Если в пути не повторяются вершины, то такой путь
называется цепью (простым путем).
Циклом в графе называется путь, у которого начало и
конец совпадают.
Простым циклом в графе называется цепь, у которой
начало и конец совпадают.
Например, ABCF – цепь
от точки А к точке F;
CGDCEBC
–
цикл;
EBCDE – простой цикл.

15.

Путь, цепь и цикл
То есть отличие цикла от простого цикла в том, что цикл – это
путь, в котором вершины могут повторяться, а простой цикл –
это путь, в котором вершины не повторяются.
Составим схему для упрощения запоминания новых терминов:
Путь
Вершины не
повторяются
Начало и конец
совпадают
Цепь
Цикл
Вершины не
повторяются
Начало и конец
совпадают
Простой цикл

16.

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

17.

Задание 5
Назовите 3 пути (не простых)
изображенного на рисунке.
графа,

18.

Задание 6
Назовите 3 цикла (не простых) графа,
изображенного на рисунке.

19.

Задание 7
Среди графов, изображенных на рисунке,
найдите те, которые являются:
а) цепью; б) простым циклом.

20.

Задание 8
На рисунке изображен граф. Назовите:
а) Какой-нибудь
б) Какую-нибудь цепь;
путь;
в) Какой-нибудь
г) Какой-нибудь простой
цикл;
цикл.
Определите, есть ли здесь путь от вершины А
к вершине Е.

21.

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

22.

Задание 9
На рисунке изображены графы. Назовите те из них, которые:
а) являются связными; б) не являются связными.

23.

Задание 10
Изобразите связный граф с девятью
вершинами, чтобы наибольшая длина его
цепей была равна двум.
Задание 11
Изобразите связный граф с шестью
вершинами, который имеет два простых
цикла, длина которых равна 5.
Задание 12
Изобразите
связный
граф
с
семью
вершинами, который имеет цикл, длина
которого равна 9.

24.

Задание 13
На рисунке изображен граф. Какова
наибольшая длина его простого цикла?

25.

Деревом называется всякий связный граф, не
имеющий циклов.
Граф, состоящий из одной изолированной
вершины также является деревом.

26.

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

27.

Задание 15
Постройте деревья с 3; 7; 9 вершинами.
Задание 16
Миша связывает шарики. Каждый из шариков
соединен тремя нитками с тремя другими
шариками. Может ли всего у Миши оказаться
4 шарика? Ответ обоснуйте.

28.

Задание 17
Миша связывает шарики. Каждый из шариков
соединен тремя нитками с тремя другими
шариками. Может ли всего у Миши оказаться
10 ниток? Ответ обоснуйте.
Задание 18
Миша связывает шарики. Каждый из шариков
соединен тремя нитками с тремя другими
шариками. Может ли всего у Миши оказаться
10 шариков? Ответ обоснуйте.

29.

Задание 19
На рисунке изображен граф. Назовите по 2 в
каждом пункте a-d:
a. Путь;
b. Цепь;
c. Цикл;
d. Простой цикл;
e. Постройте дерево с таким
же количеством ребер.

30.

Источники изображений
https://triptonkosti.ru/18-foto/shema-dannyh-bd.html
https://studopedia.ru/9_89562_obobshchennaya-strukturatelekommunikatsionnoy-seti.html
https://www.printfriendly.com/p/g/DGDfFA
https://triptonkosti.ru/26-foto/shema-upravleniya-gosudarstvom-vdrevnem-egipte.html
http://metro.spb.ru/map.html?v=1
https://gas-kvas.com/risunki-zhivotnyh/print:page,1,26110-risunkipischevoj-cepochki-zhivotnyh-46-foto.html
https://zelengarden.ru/1-foto/rodoslovnaya-ryurika-shema.html
http://www.kupsilla.ru/district.htm