Что такое findtheslide.com?

FindTheSlide.com - это сайт презентаций, докладов, шаблонов в формате PowerPoint.


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

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

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

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

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

ГрафПростейшая модель системы.Отображает элементарный состав системы и структуру связейСетьГраф с возможностью множества различных путей перемещения по ребрам между некоторыми парами вершинГраф называется связнымесли любая пара его вершин — связная.Ребро соединяет две вершины графаэлемент (точка) графа, обозначающий
Решение задач с помощью графов ГрафПростейшая модель системы.Отображает элементарный состав системы и структуру связейСетьГраф с возможностью множества Кенигсбергские  мосты Кенигсбергские мостыМожно ли обойти все Кенигсбергские мосты, проходя только один раз через каждый из этих мостов? Представим задачу в виде графа,где вершины – острова и берега (A,B,C,D), а Какие вершины четные, а какие нечетные? Подпишем степени вершин в кружочках.Нечетные вершины: А, B, C, D.3335 Если граф имеет цикл, содержащий все ребра графа по одному разу (Эйлерова Алгоритм решения задач1. Нарисовать граф, где вершины – острова и берега, а Достроить графы до Эйлеровых Задача о 15 мостахВ некоторой местности через протоки переброшено 15 мостов. Построим граф, где вершины – острова и берега, а ребра – мосты.
Слайды презентации

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

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

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

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

Сеть

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

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

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

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

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

Вершина

Ребро

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

Дуга

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

Петля

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

Дерево


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

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

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

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

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

Представим задачу в виде графа,где вершины – острова и берега (A,B,C,D), – острова и берега (A,B,C,D), а ребра – мосты

Важно, является ли число мостов, ведущих к этим отдельным участкам, четным или нечетным.
Так, в нашем случае к участку A ведут пять мостов, а к остальным – по три моста.










Слайд 6 Какие вершины четные, а какие нечетные?

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

3

3

3

5


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

Если граф имеет цикл, содержащий все ребра графа по одному разу ребра графа по одному разу (Эйлерова линия),то такой граф называется эйлеровым графом
Условия существования Эйлеровой линии:
-граф связный
-все вершины четные
Другими словами, эйлеров граф – это граф,который можно нарисовать одним росчерком

Эйлеров граф


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

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

Слайд 9






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

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

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

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

















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

Построим граф, где вершины – острова и берега, а ребра – и берега, а ребра – мосты.

Нечетные вершины: D, E. 
ВЫВОД: Так как количество нечетных вершин = 2, то обход возможен.
Его Начало может быть в местности D, а Конец в местности E.

4

4

6

3

5

8