Теория графов презентация
Содержание
- 2. Основоположником теории графов считается Леонард Эйлер, который доказал невозможность маршрута прохождения
- 3. Основные понятия Граф G=(V,E) состоит из двух множеств: конечного множества элементов,
- 4. Основные понятия Вершины vi и vj, определяющие ребро ek, называются концевыми
- 5. Основные понятия Изолированная вершина не инцидентна ни одному ребру (v3). Две
- 6. Основные понятия Подграф – любая часть графа, сама являющаяся графом.
- 7. Виды графов Граф G=(V,E) называется простым, если он не содержит петель
- 8. Виды графов
- 9. Виды графов Граф G с петлями и кратными ребрами называется псевдограф.
- 10. Особый интерес представляют связные акциклические графы, называемые деревьями. Дерево на множестве
- 11. На практике широко используются такие виды графов, как деревья и прадеревья.
- 12. Лесом называется несвязный граф, каждая компонента связности которого является деревом. Лесом
- 13. Неориентированный граф Граф G, рёбра которого не имеют определённого направления, называется
- 14. Ориентированный граф Граф G, имеющий определённое направление, называется ориентированным графом или
- 15. Способы задания графов 1) Явное задание графа как алгебраической системы. Чтобы
- 16. Способы задания графов 2) Геометрический.
- 17. Способы задания графов 3) Матрица смежности. Элементы Aij матрицы смежности A
- 18. Матрица смежности неорграфа Для неорграфа G, представленного на рисунке, матрица смежности
- 19. Матрица смежности орграфа Для орграфа G, представленного на рисунке, матрица смежности
- 20. Способы задания графов 4) Матрица инцидентности. Матрица инцидентности В
- 21. Способы задания графов 1) для неорграфа 1, если вершина vi инцидентна
- 22. Матрица инцидентности орграфа 2) для орграфа -1, если ребро ej входит
- 23. Маршрут Маршрут в графе G=(V,E) — конечная чередующееся последовательность вершин и
- 24. Маршрут Маршрут называется открытым, если его концевые вершины различны (v1, e1,
- 25. Цепь Маршрут называется цепью, если все его ребра различны. Цепь называется
- 26. Путь, цикл Открытая цепь называется путем, если все ее вершины различны
- 27. Cвойства путей и циклов 1. Степень каждой неконцевой вершины пути равна
- 28. Связность графов, компонента связности Две вершины vi и vj называются связанными
- 29. Степень вершины Степенью deg(vj) вершины vj называется число инцидентных ей ребер,
- 30. Сумма степеней вершин графа Утверждение («лемма о рукопожатиях») Сумма всех вершин
- 31. Изоморфизм графов Два графа G1 и G2 изоморфны, если существует такое
- 32. Пример изоморфных графов Соответствие вершин: v1v2’,v2v3’,v3v1’,v4v4’,v5v5’; Соответствие ребер: e1e1’, e3e2’, e5e4’,
- 33. Изоморфизм как отношение эквивалентности на множестве графов Отношение изоморфизма является эквивалентностью,
- 34. Помеченный и абстрактный графы Граф порядка n называется помеченным, если его
- 35. Характеристики расстояний в графах Характеристики расстояний в графах Пусть G(X) –
- 36. Отклоненностью вершины xi называется наибольшее из отклонений d(xi, xj) по всем
- 37. Граф, представляющий ее, изображен на рис, а матрица отклонений и вектор
- 38. Характеристические числа графов Решение многих технических задач методами теории графов
- 39. Характеристические числа графов Хроматическое число. Пусть р – натуральное число.
- 40. Характеристические числа графов Множество внутренней устойчивости. Множество S X графа G(X)
- 41. Эйлеровы и гамильтоновы графы
- 43. Граф называется эйлеровым, если он содержит эйлеров цикл Граф называется эйлеровым,
- 44. Задача может быть решена в другой постановке: если в граф добавить
- 45. Эйлеровы цепи и степени вершин Эйлеровы цепи и степени вершин Эйлеровы
- 46. Граф является эйлеровым тогда и только тогда, когда все его вершины
- 49. Определение негативного влияния соседних ячеек памяти на запоминание информации в тестируемой
- 54. Понятие гамильтонова цикла впервые появилось в связи с задачей о кругосветном
- 59. Эйлеровы графы Эйлеровы графы Определены необходимые и достаточные условия существования эйлеровых
- 60. Скачать презентацию
Слайды и текст этой презентации