PPt4Web Хостинг презентаций

X Код для использования на сайте:

Скопируйте этот код и вставьте его на свой сайт

X

Чтобы скачать данную презентацию, порекомендуйте, пожалуйста, её своим друзьям в любой соц. сети.

После чего скачивание начнётся автоматически!

Кнопки:

Презентация на тему: Графы


Скачать эту презентацию

Презентация на тему: Графы


Скачать эту презентацию

№ слайда 1 ГРАФЫ Презентация создана учителем математики и информатики Ковалевой Анной Леон
Описание слайда:

ГРАФЫ Презентация создана учителем математики и информатики Ковалевой Анной Леонидовной ГБОУ СОШ №341 г.СПб 2013-2014

№ слайда 2 Граф – это конечная совокупность вершин, некоторые из которых соединены ребрами
Описание слайда:

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

№ слайда 3 Виды (примеры) графов: Обычный (неориентированный) граф 2 вершины могут быть сое
Описание слайда:

Виды (примеры) графов: Обычный (неориентированный) граф 2 вершины могут быть соединены только одним ребром. Соединяющие линии называются ребрами. (смежные вершины – это 2 вершины, соединенные ребром)

№ слайда 4 Ориентированный граф (орграф) - это граф, у которого на линиях, соединяющих верш
Описание слайда:

Ориентированный граф (орграф) - это граф, у которого на линиях, соединяющих вершины, указано направление (соединяющие линии называются дугами)

№ слайда 5 Нагруженный граф - это граф, у которого около каждого ребра проставлено число, х
Описание слайда:

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

№ слайда 6 Сеть- это орграф, у которого около каждого ребра проставлено число, характеризую
Описание слайда:

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

№ слайда 7 Решение задачи, моделируемой нагруженным графом или сетью, сводится, как правило
Описание слайда:

Решение задачи, моделируемой нагруженным графом или сетью, сводится, как правило, к нахождению оптимального в том или ином смысле маршрута, ведущего от одной вершины к другой

№ слайда 8 Семантический граф- это граф или орграф, у которого около каждого ребра проставл
Описание слайда:

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

№ слайда 9 Мультиграф 2 вершины соединены 2 ребрами и более (кратные ребра)
Описание слайда:

Мультиграф 2 вершины соединены 2 ребрами и более (кратные ребра)

№ слайда 10 Петля в графе (ребро соединяет вершину саму с собой)
Описание слайда:

Петля в графе (ребро соединяет вершину саму с собой)

№ слайда 11 Понятие степени вершины графа – это количество ребер, выходящих из одной вершины
Описание слайда:

Понятие степени вершины графа – это количество ребер, выходящих из одной вершины

№ слайда 12 СВОЙСТВА ГРАФОВ: 1) Для любого графа сумма степеней вершин равна удвоенному коли
Описание слайда:

СВОЙСТВА ГРАФОВ: 1) Для любого графа сумма степеней вершин равна удвоенному количеству ребер 2) Для любого графа количество вершин нечетной степени всегда четно (аналог задачи: в любой момент времени количество людей, сделавших нечетное количество рукопожатий, четно) 3) В любом графе есть по крайней мере 2 вершины, имеющие одинаковую степень.

№ слайда 13 1) Маршрут на графе – это последовательность ребер, в которой конец одного ребра
Описание слайда:

1) Маршрут на графе – это последовательность ребер, в которой конец одного ребра служит началом следующего (циклический маршрут – если конец последнего ребра последовательности совпадает с началом 1-го ребра) 2) Цепь – это маршрут, в котором каждое ребро содержится не более одного раза 3) Цикл – это цепь, являющаяся циклическим маршрутом 4) Простая цепь – это цепь, проходящая через каждую свою вершину ровно 1 раз 5) Простой цикл – это цикл, являющийся простой цепью 6) Связанные вершины – это вершины (например, А и B), для которых существует цепь, начинающаяся в А и заканчивающаяся в B 7) Связный граф – это граф, у которого любые 2 вершины связанны. Если граф несвязен, то в нем можно выделить так называемые связанные компоненты (т.е. множества вершин, соединенных ребрами исходного графа, каждое из которых является связным графом) Один и тот же граф может быть изображен по-разному.

№ слайда 14 Пример 1 V={1,2,3,4,5,6,7,8,9,10}-это множество вершин графа. Для каждого из пер
Описание слайда:

Пример 1 V={1,2,3,4,5,6,7,8,9,10}-это множество вершин графа. Для каждого из перечисленных ниже случаев изобразите граф и определите все степени вершин а) вершины x y соединены ребром тогда и только тогда, когда (x-y)/3 целое число б) вершины x y соединены ребром тогда и только тогда, когда x+y=9 в) вершины x y соединены ребром тогда и только тогда, когда x+y содержится в множестве V={1,2,3,4,5,6,7,8,9,10} г) вершины x y соединены ребром тогда и только тогда, когда |x-y|

№ слайда 15 а)
Описание слайда:

а)

№ слайда 16 б)
Описание слайда:

б)

№ слайда 17 в)
Описание слайда:

в)

№ слайда 18 Пример 2: Решение логических задач 1) Может ли в государстве, в котором из каждо
Описание слайда:

Пример 2: Решение логических задач 1) Может ли в государстве, в котором из каждого города выходят ровно 3 дороги, быть ровно 100 дорог? Ответ: Нет (по формуле 3n=2*100, откуда n-количество городов- не целое) 2) – Наша шпионская сеть была хорошо законспирирована, - признался на допросе агент 007. – В ней было 77 агентов, но каждый знал только семерых. Почему наверняка можно утверждать, что агент врет? Ответ: По условию задачи 7*77=2*n, откуда n - не целое.

№ слайда 19 Способы представления графов: 1) графический 2) табличный (таблица смежности)
Описание слайда:

Способы представления графов: 1) графический 2) табличный (таблица смежности)

№ слайда 20 Пример 3 Дан граф. Выбрать его табличное представление Выбрать его табличное пре
Описание слайда:

Пример 3 Дан граф. Выбрать его табличное представление Выбрать его табличное представление:

№ слайда 21 Пример 4 Сколько различных путей существует из А в К. 1 СПОСОБ РЕШЕНИЯ: РУЧНОЙ (
Описание слайда:

Пример 4 Сколько различных путей существует из А в К. 1 СПОСОБ РЕШЕНИЯ: РУЧНОЙ (ВРУЧНУЮ СЧИТАЕМ КОЛИЧЕСТВО ПУТЕЙ ИЗ А В К) ОТВЕТ: 17 2 СПОСОБ РЕШЕНИЯ: ПОСТРОЕНИЕ ДЕРЕВА РЕШЕНИЯ ОТВЕТ: 17

№ слайда 22 3 СПОСОБ РЕШЕНИЯ: с помощью построения таблицы (вершина, куда идем, количество п
Описание слайда:

3 СПОСОБ РЕШЕНИЯ: с помощью построения таблицы (вершина, куда идем, количество путей) № просмотра 1 2 3 4 5 6 7 8 9 10 Вершина К И Ж Л Е Д В Г Б А Куда идем - К К К Ж,Л, К И,Ж Д,Е,Ж В,Е В,Д Б,Г К-во путей  1 1 1 1 3 2 6 9 8 17

Скачать эту презентацию

Презентации по предмету
Презентации из категории
Лучшее на fresher.ru