Презентация На тему решение задач с помощью графов онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему На тему решение задач с помощью графов абсолютно бесплатно. Урок-презентация на эту тему содержит всего 11 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:11 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:1.24 MB
- Просмотров:89
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда:
№2 слайд
Содержание слайда: Граф
№3 слайд
Содержание слайда: Кенигсбергские
мосты
№4 слайд
Содержание слайда: Кенигсбергские мосты
№5 слайд
Содержание слайда: Представим задачу в виде графа,где вершины – острова и берега (A,B,C,D), а ребра – мосты
№6 слайд
Содержание слайда: Какие вершины четные, а какие нечетные? Подпишем степени вершин в кружочках.
Какие вершины четные, а какие нечетные? Подпишем степени вершин в кружочках.
Нечетные вершины: А, B, C, D.
№7 слайд
Содержание слайда: Если граф имеет цикл, содержащий все ребра графа по одному разу (Эйлерова линия),то такой граф называется эйлеровым графом
Если граф имеет цикл, содержащий все ребра графа по одному разу (Эйлерова линия),то такой граф называется эйлеровым графом
Условия существования Эйлеровой линии:
-граф связный
-все вершины четные
Другими словами, эйлеров граф – это граф,который можно нарисовать одним росчерком
№8 слайд
Содержание слайда: Алгоритм решения задач
1. Нарисовать граф, где вершины – острова и берега, а ребра – мосты.
2. Определить степень каждой вершины и подписать возле нее.
3. Посчитать количество нечетных вершин.
4. Обход возможен:
a. ЕСЛИ все вершины – четные, и его можно начать с любого участка.
b. ЕСЛИ 2 вершины – нечетные, но его нужно начать с одной из нечетных местностей.
5. Обход невозможен, если нечетных вершин больше 2.
6. Сделать ВЫВОД.
7. Указать Начало и Конец пути.
№9 слайд
Содержание слайда: Достроить графы до Эйлеровых
№10 слайд
Содержание слайда: Задача о 15 мостах
В некоторой местности через протоки переброшено 15 мостов.
№11 слайд
Содержание слайда: Построим граф, где вершины – острова и берега, а ребра – мосты.
Нечетные вершины: D, E.
ВЫВОД: Так как количество нечетных вершин = 2, то обход возможен.
Его Начало может быть в местности D, а Конец в местности E.
Скачать все slide презентации На тему решение задач с помощью графов одним архивом:
