Презентация на тему: Понятие графа Простейшие свойства графа

Понятие графа Простейшие свойства графа
Теория графов
Задача о Кенигсбергских мостах
Что такое граф
Мультиграф
Степень вершин
Свойства графа
Маршрут на графике
Цепь, цикл
Цепь, цикл
Связный граф
Изображение графа
Задачи (выполнить во время урока)
Домашнее задание 1. Задача
Понятие графа Простейшие свойства графа
1/15
Средняя оценка: 4.9/5 (всего оценок: 6)
Код скопирован в буфер обмена
Скачать (769 Кб)
1

Первый слайд презентации: Понятие графа Простейшие свойства графа

11 класс

Изображение слайда
2

Слайд 2: Теория графов

Теория графов – одна из немногих математических теорий, для которых точно известен ее создатель, время и место создания: Леонард Эйлер, 1736 год, г. Петербург. Именно в этом году Л.Эйлером в «Записках Петербургской академии наук» была опубликована статья, в которой приводилось решение широко теперь известной задачи о Кенигсбергских мостах. В ней великий математик сформулировал и обосновал критерий, позволяющий отвечать на данный вопрос для любого графа.

Изображение слайда
3

Слайд 3: Задача о Кенигсбергских мостах

Философ Иммануил Кант, гуляя по городу Кенигсбергу (сейчас этот город называется Калининград), поставил задачу (1736), известную в математике как задача о семи кенигсбергских мостах: можно ли пройти по всем этим мостам и при этом вернуться в исходную точку так, чтобы по каждому мосту пройти только один раз.

Изображение слайда
4

Слайд 4: Что такое граф

Граф – это мощное средство моделирования Граф – это конечная совокупность вершин, некоторые из которых соединены ребрами A, B, C, D, E – вершина А В С D E ребро

Изображение слайда
5

Слайд 5: Мультиграф

Мультиграф – граф, в котором пара вершин соединена несколькими ребрами. Ребра, соединяющие одну и ту же пару вершин, называются кратными. Две разные вершины графа, соединенные ребром, называются смежными.

Изображение слайда
6

Слайд 6: Степень вершин

Количество ребер, выходящих из одной вершины, называют степенью вершины. Число ребер в графе ровно в 2 раза меньше, чем в сумме степеней вершины Сумма степеней вершин графа четна Число нечетных вершин графа че т но С А В D E F Нечетная вершина A – 3 ; B – 2 ; C – 4 ; D – 2 ; E – 2 ; F – 1 Сумма степеней вершин равна 14  =3+2+4+2+2+1=14 Количество ребер – 7 14:2=7

Изображение слайда
7

Слайд 7: Свойства графа

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

Изображение слайда
8

Слайд 8: Маршрут на графике

— это последовательность ребер a1,a2,...,an, в которой конец одного ребра служит началом другого. Циклическим маршрут называется в том случае, если конец последнего ребра последовательности совпал с началом первого ребра. Для графа, изображенном на рисунке a1,a2,a3, a5, a7, — маршрут, a2,a5, a6,a7 — циклический маршрут, а последовательность a1, a2,a4, a6, a7 — маршрутом не является.

Изображение слайда
9

Слайд 9: Цепь, цикл

— это маршрут, в котором каждое ребро содержится не более одного раза. Цепь, являющаяся циклическим маршрутом, называется циклом. Для графа, изображенном на рисун ке a1,a2,a6,a7,a4,a5,a7 — цепь, a2,a6,a7,a8,a4,a2,a6 — цикл.

Изображение слайда
10

Слайд 10: Цепь, цикл

Цепь называется простой, если проходит через каждую свою вершину ровно один раз. Цикл называется простым, если является простой цепью. Для графа, изображенном на рисунке, a1,a2,a6,a7,a4 — простая цепь, a2,a6,a7,a8,a4 — простой цикл.

Изображение слайда
11

Слайд 11: Связный граф

Связанные вершины — это вершины a и b, для которых существует цепь, начинающаяся в a и заканчивающаяся в b. Связный граф — это граф, у которого любые две вершины связанны. Если граф несвязен, то в нем можно выделить так называемые связанные компоненты (т.е. множества вершин, соединенных ребрами исходного графа, каждое из которых является связным графом).

Изображение слайда
12

Слайд 12: Изображение графа

Один и тот же граф может быть изображен по-разному.

Изображение слайда
13

Слайд 13: Задачи (выполнить во время урока)

В графе 30 вершин и 80 ребер, каждая вершина имеет степень 5 или 6. Сколько в нем вершин степени 5? В графе каждая вершина имеет степень 3, а число ребер заключено между 16 и 20. Сколько вершин в этом графе?

Изображение слайда
14

Слайд 14: Домашнее задание 1. Задача

Существует ли граф с пятью вершинами и следующим набором степеней вершин а) 0, 1, 2,3,4; б) 1, 1, 2, 3, 4; в) 1, 1, 2, 2, 4; г) 1, 1, 2, 3, 3? При ответе «Да» надо предъявить соответствующий граф, ответ «Нет» надо обосновать.

Изображение слайда
15

Последний слайд презентации: Понятие графа Простейшие свойства графа

2. Задача о Кенигсбергских мостах

Изображение слайда