Разделы презентаций


Решение задач с помощью графов

ГрафПростейшая модель системы.Отображает элементарный состав системы и структуру связейСетьГраф с возможностью множества различных путей перемещения по ребрам между некоторыми парами вершинГраф называется связнымесли любая пара его вершин — связная.Ребро соединяет две

Слайды и текст этой презентации

Слайд 1Решение задач с помощью графов

Решение задач с помощью графов

Слайд 2Граф
Простейшая модель системы.Отображает элементарный состав системы и структуру связей
Сеть
Граф с

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

вершин

Граф называется связным

если любая пара его вершин — связная.

Ребро соединяет две вершины графа

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

Вершина

Ребро

это ориентированное ребро.

Дуга

ребро, начало и конец которого находятся в одной и той же вершине

Петля

любой связный граф, не имеющий циклов.

Дерево

ГрафПростейшая модель системы.Отображает элементарный состав системы и структуру связейСетьГраф с возможностью множества различных путей перемещения по ребрам

Слайд 3Кенигсбергские мосты

Кенигсбергские  мосты

Слайд 4Кенигсбергские мосты
Можно ли обойти все Кенигсбергские мосты, проходя только один

раз через каждый из этих мостов?

Кенигсбергские мостыМожно ли обойти все Кенигсбергские мосты, проходя только один раз через каждый из этих мостов?

Слайд 5Представим задачу в виде графа,где вершины – острова и берега

(A,B,C,D), а ребра – мосты
Важно, является ли число мостов, ведущих

к этим отдельным участкам, четным или нечетным.
Так, в нашем случае к участку A ведут пять мостов, а к остальным – по три моста.
Представим задачу в виде графа,где вершины – острова и берега (A,B,C,D), а ребра – мостыВажно, является ли

Слайд 6Какие вершины четные, а какие нечетные? Подпишем степени вершин в

кружочках.
Нечетные вершины: А, B, C, D.
3
3
3
5

Какие вершины четные, а какие нечетные? Подпишем степени вершин в кружочках.Нечетные вершины: А, B, C, D.3335

Слайд 7Если граф имеет цикл, содержащий все ребра графа по одному

разу (Эйлерова линия),то такой граф называется эйлеровым графом
Условия существования Эйлеровой

линии:
-граф связный
-все вершины четные
Другими словами, эйлеров граф – это граф,который можно нарисовать одним росчерком

Эйлеров граф

Если граф имеет цикл, содержащий все ребра графа по одному разу (Эйлерова линия),то такой граф называется эйлеровым

Слайд 8Алгоритм решения задач
1. Нарисовать граф, где вершины – острова и

берега, а ребра – мосты.
2. Определить степень каждой вершины

и подписать возле нее.
3. Посчитать количество нечетных вершин.
4. Обход возможен:
a. ЕСЛИ все вершины – четные, и его можно начать с любого участка.
b. ЕСЛИ 2 вершины – нечетные, но его нужно начать с одной из нечетных местностей.
5. Обход невозможен, если нечетных вершин больше 2.
6. Сделать ВЫВОД.
7. Указать Начало и Конец пути.
Алгоритм решения задач1. Нарисовать граф, где вершины – острова и берега, а ребра – мосты. 2. Определить

Слайд 9Достроить графы до Эйлеровых

Достроить графы до Эйлеровых

Слайд 10Задача о 15 мостах
В некоторой местности через протоки переброшено 15

мостов.

Задача о 15 мостахВ некоторой местности через протоки переброшено 15 мостов.

Слайд 11Построим граф, где вершины – острова и берега, а ребра

– мосты.
Нечетные вершины: D, E. 
ВЫВОД: Так как количество нечетных вершин

= 2, то обход возможен.
Его Начало может быть в местности D, а Конец в местности E.

4

4

6

3

5

8

Построим граф, где вершины – острова и берега, а ребра – мосты. Нечетные вершины: D, E. ВЫВОД: Так

Обратная связь

Если не удалось найти и скачать доклад-презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое TheSlide.ru?

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно  хранить и делиться своими презентациями с другими пользователями.


Для правообладателей

Яндекс.Метрика