Теория графов презентация
Содержание
- 2. Литература В.А. Горбатов Дискретная математика М.: АСТ; Астрель, 2003 Харари
- 3. Задача о Кёнигсбергских мостах Леонард Эйлер(1707-1783)
- 4. Основные объекты графов носитель метаграфа (конечное множество вершин). V={v1,v2, …
- 5. Понятие графа и орграфа Граф G=<V,U>, где V={v1,v2,…,vn}, n1 –
- 6. Неориентированный граф (граф) G = <V, U>, V = {v1,v2,…,vn},n1,
- 7. Ориентированный граф (орграф) G=<V,U>, V={v1,v2,…,vn},n1 UVV (vi,vj) ≠ (vj,
- 8. Геометрический граф Граф
- 9. Обозначение Gp,q V= p, U= q G1,0 - тривиальный граф
- 10. типы метаграфов ГИПЕРГРАФ (модельный граф) Сигнатура (U) - множество граней, каждая
- 11. взвешенные метаграфы
- 12. Локальная структура графа (vi,vj)U – vi и vj – смежны uk=
- 13. Пример
- 14. Степень вершины Степень вершины (d(vi)) – число рёбер, инцидентных вершине d(v1)=2
- 15. Теорема В любом конечном графе число вершин нечётной степени чётно.
- 16. Свойства степеней графа Gp,q
- 17. Степень графа Степень графа (максимальная степень вершины) Минимальная степень вершины графа
- 18. Локальная структура ориентированного графа uk= (vi,vj) – дуга uk положительно инцидентна
- 19. Пример
- 20. Степени вершин в орграфе d+(vi) – число положительно инцидентных дуг вершины
- 21. Свойства степеней орграфа Для любого ориентированного графа
- 22. Свойства степеней орграфа Для любого ориентированного графа
- 23. Матричное представление графа Матрица смежности А:
- 24. Пример
- 25. Матрица инцидентности В
- 26. Пример
- 27. Матрица смежности орграфа А:
- 28. Пример
- 29. Матрица инцидентности В
- 30. Пример
- 31. Функциональный способ задания графов G=<V,Г> Г- функция окрестности вершин Г:VP(V)
- 32. Пример Г(v1)={v2, v3} Г(v2)={v1, v3} Г(v3)={v1, v2,v4} Г(v4)={v3}
- 33. Функциональный способ задания орграфов G=<V,Г+> G=<V,Г-> Г+, Г- - функции
- 34. Пример Г(v1)+={v2, v3} Г(v2)+={v3} Г(v3)+={v2,v4} Г(v4)+=
- 35. Пример Г(v1)-= Г(v2)- ={v1,v3} Г(v3) -={v1,v2} Г(v4)-={v3}
- 36. Изоморфизм графов Графы изоморфны, если существует взаимно однозначное соответствие между множествами
- 37. Функциональное задание изоморфизма графов Два графа Ga=Va,Ua и Gb=Vb,Ub изоморфны, если
- 38. Свойства изоморфизма Отношение рефлексивно симметрично транзитивно Эквивалентность
- 39. Пример изоморфных графов
- 40. Пример не изоморфных графов
- 41. Инварианты графа Количественная или качественная характеристики, неизменные для всех изоморфных
- 42. Полный граф Kn Граф полный, если каждая вершина смежна с
- 43. Двудольный граф Граф двудольный, если множество вершин графа можно разбить на
- 44. Двудольные графы. Примеры
- 45. Полный двудольный граф Km,n Km,n - граф двудольный и каждая вершина
- 46. Полные двудольные графы Km,n
- 47. Операции над графами Удаление ребра G=<V, U>, G\u=<V, U\{u}>
- 48. Удаление вершины G=<V, U>, G\v=<V’, U’> V’=V\{v}, U’=U(V’ V’)
- 49. Подграфы G’=<V’, U’> - подграф графа G=<V, U>, если V’V,
- 50. Подграфы G’=<V’, U’> - частичный подграф графа G=<V, U>, если
- 51. Дополнение графа =<V, U’> - дополнение графа G=<V,U>, если U’=((VV)\U)\I
- 52. Самодополнительные графы Граф, изоморфный своему дополнению - самодополнительный
- 53. Скачать презентацию
Слайды и текст этой презентации