Зв’язаність графів. Шляхи, цикли ізоморфізм - презентация, доклад, проект скачать

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

Зв’язаність графів. Шляхи, цикли ізоморфізм, слайд №1

Зв’язаність графів. Шляхи, цикли ізоморфізм, слайд №2

Зв’язаність графів. Шляхи, цикли ізоморфізм, слайд №3

Зв’язаність графів. Шляхи, цикли ізоморфізм, слайд №4

Зв’язаність графів. Шляхи, цикли ізоморфізм, слайд №5

Зв’язаність графів. Шляхи, цикли ізоморфізм, слайд №6

Зв’язаність графів. Шляхи, цикли ізоморфізм, слайд №7

Зв’язаність графів. Шляхи, цикли ізоморфізм, слайд №8

Зв’язаність графів. Шляхи, цикли ізоморфізм, слайд №9

Зв’язаність графів. Шляхи, цикли ізоморфізм, слайд №10

Зв’язаність графів. Шляхи, цикли ізоморфізм, слайд №11

Зв’язаність графів. Шляхи, цикли ізоморфізм, слайд №12

Зв’язаність графів. Шляхи, цикли ізоморфізм, слайд №13

Зв’язаність графів. Шляхи, цикли ізоморфізм, слайд №14

Зв’язаність графів. Шляхи, цикли ізоморфізм, слайд №15

Содержание ▲

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

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

Слайд 1

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

Лекція-2.1. Тема: «Зв’язаність графів. Шляхи, цикли ізоморфізм»

Слайд 2

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

Зміст Вступ…………………………………………………. 3 Шлях…………………….………………………….. 4 Цикл.................................... …………………………..6 Теорема............................................................... ……..7 Орієнтований граф …………………………………..8 Зв’язаність графів................................ ……………….9 Ізоморфізм графів................................................... …10 Ізоморфні графи.........……………………...……..11 Теорема............... ……………………………………12 Проблеми визначення……….……………………...13 Висновки …………………………………………....14 Список літератури ……………………………….....15

Слайд 3

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

Вступ Теорія графів — одна з істотних частин математичного апарату інформатики та кібернетики. У термінах теорії графів можна сформулювати багато задач, пов’язаних із дискретними об’єктами. Такі задачі виникають у проектуванні інтегральних схем і схем управління, у дослідженні автоматів, в економіці й статистиці, теорії розкладів і дискретній оптимізації.

Слайд 4

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

Шлях Шляхом довжиною r [52] із вершини и в вершину v в неорієнтованому графі називають послідовність ребер е1 = {х0, х1}, е2 = {хІ ,х2}, ..., еr={хr-1 хr} де хr = v, r — натуральне число. Отже, шлях довжиною r має r ребер, причому ребро враховують стільки разів, скільки воно міститься в шляху. Вершини v та e називають крайніми, а решту вершин шляху — внутрішніми.

Слайд 5

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

Цикл Циклом у неорієнтованому графі називають шлях, який з’єднує вершину саму собою, тобто и = V.

Слайд 6

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

Теорема

Слайд 7

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

Орієнтованим графом називають пару (V, Е), де V — скінченна непорожня множина вершин, а £ множина впорядкованих гар елементів множини V.

Слайд 8

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

Зв’язаність графів Орієнтований граф називають сильно зв’язним, якщо для будь-яких його різних вершин и та V існують орієнтовані шляхи від и до V та від її до и. Позначають так: A=B Орієнтований граф називають слабко зв’язним, якшо існує шлях між будь-якими двома різними вершинами у відповідному йому неорієнтованому графі (тобто без урахування напрямку дуг).

Слайд 9

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

Ізоморфізм графів У теорії графів і її застосуваннях істотно, що існують об’єкти (вершини графа) і зв’язки між ними (ребра). Тому доцільно не розрізняти графи, котрі можна одержати один з одного зміною позначень вершин. Сформулюємо ці міркування у вигляді наступного означення.

Слайд 10

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

Нехай G1 = (VІ, Е1) і G2=(V2, Е2) прості графи, а φ: Vх → V2 — бієкція. Якщо для будь-яких вершин u та v графа G1 їх образи φ(u) та φ(v) суміжні в G2 тоді й лише тоді, коли и та v суміжні в G1 то цю бієкцію називають ізоморфізмом графа G1 на граф G2, а графи G1 G2 — ізоморфними. Нехай G1 = (VІ, Е1) і G2=(V2, Е2) прості графи, а φ: Vх → V2 — бієкція. Якщо для будь-яких вершин u та v графа G1 їх образи φ(u) та φ(v) суміжні в G2 тоді й лише тоді, коли и та v суміжні в G1 то цю бієкцію називають ізоморфізмом графа G1 на граф G2, а графи G1 G2 — ізоморфними. Отже, V и, v ≡ v1 ({и, v} ≡ Е1 тоді й лише тоді, коли {φ(u), φ(v)} ≡ Е2)

Слайд 11

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

Ізоморфні графи

Слайд 12

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

Теорема Прості графи ізоморфні тоді й лише тоді, коли їх матриці суміжності можна отримати одну з одної однаковими перестановками рядків і стовпців. Виявити ізоморфізм дуже складно. Теоретично алгоритм перевірки пари простих графів на ізоморфізм існує, але він не зручний.

Слайд 13

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

Проблема визначення Часто неважко довести, що два прості графи не ізоморфні, якщо порушується ачастивість, інваріантна щодо ізоморфізму, наприклад: кількість вершин; кількість ребер; кількість вершин конкретного степеня (вершині v ≡ V1, deg(v) = d, має відпо відати вершина u = φ(v) ≡ V2, deg(u) = d. Є й інші інваріанти, але порушення інваріантності — це лише достатня умовг неізоморфності графів.

Слайд 14

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

Висновки Отже, не існує набору інваріантів для виявлення ізоморфізму. Для сильної зв’язності орієнтованого графа має існувати послідовність дуг з урахуванням орієнтації від будь-якої вершини графа до будь-якої іншої. Шлях, буквально, - це послідовність ребер Між кожною парою різних вершин зв’язного неорієнтованого графа існує простий шлях.

Слайд 15

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

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