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

Категория: Математика
Нажмите для полного просмотра!
Зв’язаність графів. Шляхи, цикли ізоморфізм, слайд №1Зв’язаність графів. Шляхи, цикли ізоморфізм, слайд №2Зв’язаність графів. Шляхи, цикли ізоморфізм, слайд №3Зв’язаність графів. Шляхи, цикли ізоморфізм, слайд №4Зв’язаність графів. Шляхи, цикли ізоморфізм, слайд №5Зв’язаність графів. Шляхи, цикли ізоморфізм, слайд №6Зв’язаність графів. Шляхи, цикли ізоморфізм, слайд №7Зв’язаність графів. Шляхи, цикли ізоморфізм, слайд №8Зв’язаність графів. Шляхи, цикли ізоморфізм, слайд №9Зв’язаність графів. Шляхи, цикли ізоморфізм, слайд №10Зв’язаність графів. Шляхи, цикли ізоморфізм, слайд №11Зв’язаність графів. Шляхи, цикли ізоморфізм, слайд №12Зв’язаність графів. Шляхи, цикли ізоморфізм, слайд №13Зв’язаність графів. Шляхи, цикли ізоморфізм, слайд №14Зв’язаність графів. Шляхи, цикли ізоморфізм, слайд №15
Скачать
Вы можете ознакомиться и скачать презентацию на тему Зв’язаність графів. Шляхи, цикли ізоморфізм. Доклад-сообщение содержит 15 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

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

Слайд 1


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

Слайд 2


Зміст Вступ…………………………………………………. 3 Шлях…………………….………………………….. 4 Цикл.................................... …………………………..6 Теорема............................................................... ……..7 Орієнтований граф …………………………………..8 Зв’язаність графів................................ ……………….9 Ізоморфізм графів................................................... …10 Ізоморфні графи.........……………………...……..11 Теорема............... ……………………………………12 Проблеми визначення……….……………………...13 Висновки …………………………………………....14 Список літератури ……………………………….....15
Описание слайда:
Зміст Вступ…………………………………………………. 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 називають крайніми, а решту вершин шляху — внутрішніми.
Описание слайда:
Шлях Шляхом довжиною r [52] із вершини и в вершину v в неорієнтованому графі називають послідовність ребер е1 = {х0, х1}, е2 = {хІ ,х2}, ..., еr={хr-1 хr} де хr = v, r — натуральне число. Отже, шлях довжиною r має r ребер, причому ребро враховують стільки разів, скільки воно міститься в шляху. Вершини v та e називають крайніми, а решту вершин шляху — внутрішніми.

Слайд 5


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

Слайд 6


Теорема
Описание слайда:
Теорема

Слайд 7


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

Слайд 8


Зв’язаність графів Орієнтований граф називають сильно зв’язним, якщо для будь-яких його різних вершин и та V існують орієнтовані шляхи від и до V та від її до и. Позначають так: A=B Орієнтований граф на­зивають слабко зв’язним, якшо існує шлях між будь-якими двома різними вер­шинами у відповідному йому неорієнтованому графі (тобто без урахування на­прямку дуг).
Описание слайда:
Зв’язаність графів Орієнтований граф називають сильно зв’язним, якщо для будь-яких його різних вершин и та 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)
Описание слайда:
Нехай 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. Є й інші інваріанти, але порушення інваріантності — це лише достатня умовг неізоморфності графів.
Описание слайда:
Проблема визначення Часто неважко довести, що два прості графи не ізоморфні, якщо порушується ачастивість, інваріантна щодо ізоморфізму, наприклад: кількість вершин; кількість ребер; кількість вершин конкретного степеня (вершині v ≡ V1, deg(v) = d, має відпо відати вершина u = φ(v) ≡ V2, deg(u) = d. Є й інші інваріанти, але порушення інваріантності — це лише достатня умовг неізоморфності графів.

Слайд 14


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

Слайд 15


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

Скачать

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