Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Дискретная математика
Содержание
- 1. Дискретная математика
- 2. Задача о мостах КёнигсбергаКарта мостов Кенигсберга во времена Эйлера
- 3. Граф – схема мостовЧасти города – вершины,
- 4. Известные головоломкиСабли Магомеда
- 5. Эйлеров графЭйлеровым циклом в н-графе называется цикл,
- 6. Полуэйлеров графЭйлеровой цепью в н-графе называется цепь,
- 7. Теорема Эйлера (условие эйлеровости графа)Для того,
- 8. Теорема (условие полуэйлеровости графа)Для того, чтобы произвольный
- 9. Эйлеров, полуэйлеров, не эйлеров графыЭйлеров граф
- 10. Алгоритм ФлериПри построении эйлерова цикла начинаем с
- 11. Пример построения эйлерова цикла
- 12. Гамильтонов графГамильтоновым циклом в н-графе называется простой
- 13. Полугамильтонов графГамильтоновой цепью в н-графе называется простая
- 14. Гамильтонов, полугамильтонов графыГамильтонов граф
- 15. Скачать презентанцию
Задача о мостах КёнигсбергаКарта мостов Кенигсберга во времена Эйлера
Слайды и текст этой презентации
Слайд 5Эйлеров граф
Эйлеровым циклом в н-графе называется цикл, обходящий все ребра
графа (ровно по одному разу.
Эйлеров граф – граф, в котором
есть эйлеров цикл
Слайд 6Полуэйлеров граф
Эйлеровой цепью в н-графе называется цепь, обходящая все ребра
графа (ровно по одному разу).
Полуэйлеров граф – граф, в котором
есть эйлерова цепь
Слайд 7Теорема Эйлера
(условие эйлеровости графа)
Для того, чтобы произвольный
н-граф был эйлеровым, необходимо и достаточно, чтобы
он был связен
и локальные степени всех его вершин были четными.
Слайд 8Теорема (условие полуэйлеровости графа)
Для того, чтобы произвольный н-граф был полуэйлеровым,
необходимо и достаточно, чтобы: 1) он был связен и
2)
локальные степени всех его вершин, кроме двух, были четными. Вершины с нечетными степенями являются началом и концом эйлеровой цепи
Слайд 10Алгоритм Флери
При построении эйлерова цикла начинаем с произвольной вершины и
двигаемся в произвольном направлении выполняя два условия:
стираем пройденные ребра и
изолированные вершины, которые при этом появляются;идем по мосту, только если нет другой возможности.
Слайд 12Гамильтонов граф
Гамильтоновым циклом в н-графе называется простой цикл, обходящий все
вершины графа (ровно по одному разу).
Гамильтонов граф – граф, в
котором есть гамильтонов цепь.
Слайд 13Полугамильтонов граф
Гамильтоновой цепью в н-графе называется простая цепь, обходящий все
вершины графа (ровно по одному разу).
Полугамильтонов граф – граф, в
котором есть гамильтонова цикл.
