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

Категория: Математика
Нажмите для полного просмотра!
Решение задач с помощью графов, слайд №1Решение задач с помощью графов, слайд №2Решение задач с помощью графов, слайд №3Решение задач с помощью графов, слайд №4Решение задач с помощью графов, слайд №5Решение задач с помощью графов, слайд №6Решение задач с помощью графов, слайд №7Решение задач с помощью графов, слайд №8Решение задач с помощью графов, слайд №9Решение задач с помощью графов, слайд №10Решение задач с помощью графов, слайд №11Решение задач с помощью графов, слайд №12

Вы можете ознакомиться и скачать презентацию на тему Решение задач с помощью графов. Доклад-сообщение содержит 12 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

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


Слайд 1





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

Слайд 2





Граф
Граф
Описание слайда:
Граф Граф

Слайд 3





Кенигсбергские
 мосты
Описание слайда:
Кенигсбергские мосты

Слайд 4





Кенигсбергские мосты
Описание слайда:
Кенигсбергские мосты

Слайд 5





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

Слайд 6





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

Слайд 7





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

Слайд 8





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

Слайд 9





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

Слайд 10





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

Слайд 11





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

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

Слайд 12


Решение задач с помощью графов, слайд №12
Описание слайда:



Похожие презентации
Mypresentation.ru
Загрузить презентацию