Ейлерів й гамільтонів цикл - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

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

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

Слайд 1

Описание слайда:

Лекція-2.2. Тема: «Ейлерів й гамільтонів цикл»

Слайд 2

Описание слайда:

Зміст Вступ…………………………………………………. 3 Ейлер розв’язав.………………….........………….. ....4 Малій кроки є значущими.........……………………..6 Ейлерів цикл…………………………………...……..7 Теорема 1 ………………………………....…….........8 Крок 2. Достатність.................………….......…….9 Гамільтонів цикл…………………........................…10 Цікава гра…………...……....…………………...…..11 Теорема..........................……………………………...…12 Висновки …………………………………………....14 Список літератури ……………………………….....15

Слайд 3

Описание слайда:

Вступ Початок теорії графів як розділу математики пов'язують із задачею про кенігсберзькі мости. Сім мостів міста Кенігсберга (нині - Калінінград у Росії) було розміщено на річці Прегель так, як зображено на рис. Чи можна, починаючи з якоїсь точки міста, пройти через усі мости точно по одному разу й повернутись у початкову точку?

Слайд 4

Описание слайда:

Ейлер розв’язав. Його розв’язання, опубліковане 1736 р., було першим явним застосуванням теорії графів. Ейлер поставив у відповідність плану міста мультиграф С, вершини якого відповідають чотирьом частинам А, В, С, D міста, а ребра — мостам. Цей мультиграф зображено нище.

Слайд 5

Описание слайда:

Малій кроки є значущими Отже, задачу про кенігсберзькі мости мовою теорії графів можна сформулювати так: чи існує в мультиграфі С простий цикл, який містить усі ребра цього мультиграфа? Ейлер довів нерозв’язність задачі про кенігсберзькі мости. Нагадаємо, що в простому циклі ребра не повторюються, а вершини можуть повторюватись.

Слайд 6

Описание слайда:

Ейлерів цикл

Слайд 7

Описание слайда:

Теорема 1 Зв’язний мультиграф С має ейлерів цикл тоді й лише тоді, коли степені всіх його вершин парні. Крок 1. Необхідність. Нехай у графі С існує ейлерів цикл. Він проходить через кожну вершину графа та входить до неї по одному ребру, а виходить по іншому. Це означає, що кожна вершина інцидентна парній кількості ребер ейлерового циклу. Оскільки такий цикл містить усі ребра графа С, то звідси зипливає парність степенів усіх його вершин.

Слайд 8

Описание слайда:

Крок 2. Достатність Почнемо шлях P1 із довільної вершини v1 продовжимо його, наскільки це можливо, вибираючи щоразу нове ребро. Степені всіх вершин парні, то, увійшовши в будь-яку вершину, відмінну від v1, ми завжди маємо можливість вийти з неї через іще не пройдене ребро. Тому шлях Р1 можна продовжити, додавши це ребро. Отже, побудова шляху Р1 завершиться у вершині v1 тобто Р1 обов’язково ВИЯВИТЬСЯ ЦИКЛОМ.

Слайд 9

Описание слайда:

Алгоритм Флері побудови ейлерового циклу Робота алгоритму полягає в нумерації ребер у процесі побудови ейлеровог циклу. Крок 1. Початок. Починаємо з довільної вершини и та присвоюємо довільному ребру {и, v} номер 1. Викреслюємо ребро {и, v} й переходимо у вершину v.

Слайд 10

Описание слайда:

Крок 2. Ітерагоя. Нехай v — вершина, у яку ми перейшли на попередньому кроці, k — останній присвоєний номер. Вибираємо довільне ребро, інцидент- не вершині v, причому міст вибираємо лише тоді, коли немає інших можливостей. Присвоюємо вибраному ребру номер (k + 1) і викреслюємо його. Крок 3. Закінчення. Цей процес закінчуємо, коли всі ребра графа викреслено та пронумеровано ці номери задають послідовність ребер в ейлеро вому циклі.

Слайд 11

$Гамільтонів цикл у графі Шлях х0, х1 ..., xп_1,хп у зв’язному графі G = (V, E) називають гамільтоновим циклом, якщо V = {х0, х1 ..., xп_1,хп} і х1 != х2 для 0 ≤ і ≤ j ≤ п. Цикл х0, х1 ..., xп_1,хп (тут п> 1) у графі G = (V, Е) називають гамільтоновим циклом, якщо х0, х1 ..., xп_1,хп — гамільтонів шлях. Інакше кажучи, гамільтонів цикл і гамільтонів шлях проходять через кожну вершину графа точно один раз$

Описание слайда:

Гамільтонів цикл у графі Шлях х0, х1 ..., xп_1,хп у зв’язному графі G = (V, E) називають гамільтоновим циклом, якщо V = {х0, х1 ..., xп_1,хп} і х1 != х2 для 0 ≤ і ≤ j ≤ п. Цикл х0, х1 ..., xп_1,хп (тут п> 1) у графі G = (V, Е) називають гамільтоновим циклом, якщо х0, х1 ..., xп_1,хп — гамільтонів шлях. Інакше кажучи, гамільтонів цикл і гамільтонів шлях проходять через кожну вершину графа точно один раз

Слайд 12

Описание слайда:

«Навколосвітня подорож» Кожній із двадцяти вершин додекаедра (правильного дванадцятигранника, грані якого — п’ятикутники) приписано назву одного з великих міст світу. Потрібно, розпочавши з довільного міста, відвідати решту 19 міст точно одип раз і повернутись у початкове місто. Перехід дозволено ребрами додекаедра

Слайд 13

Описание слайда:

Слайд 14

Описание слайда:

Висновки Отже, для задач даного типу покищо не є відомий чіткий алгоритм, але є влучні спроби його знаходження. Незважаючи на зовнішню подібність формулювань задач про існування ейлерового й гамільтонового циклів, ці задачі принципово різні. Використовуючи результати попереднього підрозділа, легко виявити, чи має граф ейлерів цикл, і, якщо має, то побудувати його. Граф, який містить гамільтонів цикл, часто називають гамільтоновим графом.

Слайд 15

Описание слайда:

Список літератури 1. Нікольський Ю. В. Дискретна математика/ Ю. В. Нікольський, В. В. Пасічник, Ю. М. Щербина. – Київ: Видавнича група BHV, 2007. – 367 с.