Содержание
- 2. Определение графа Пусть V – множество вершин, а Е – множество ребер. Графом G называется пара
- 3. Определение графа Вершины v' и v" называются смежными, если существует ребро, соединяющее их, т.е. они инцидентны
- 4. Определение графа Граф, содержащий направленные ребра (дуги) с началом v' и концом v" , называется ориентированным
- 5. Определение графа Рис.1 Неориентированное ребро (a,b) Рис.2 Ориентированное ребро (a,b)
- 6. Определение графа Ребро, концевые вершины которого совпадают, называется петлей. Рис.3. Неориентированная петля Рис.4. Ориентированная петля
- 7. Определение графа Ребра (дуги), имеющие одинаковые начало и конец, называются параллельными или кратными. Рис.5 Кратные неориентированные
- 8. Определение графа Рис. 6. Кратные ориентированные ребра
- 9. Определение графа Ребра орграфа, соединяющие одну и туже пару вершин в разных направлениях называются симметричными или
- 10. Определение графа Граф называется конечным, если множество его элементов (вершин и ребер) конечно. Рис. 8. Конечный
- 11. Определение графа Граф называется бесконечным, если бесконечно множество вершин или множество его ребер. Рис. 9. Граф
- 12. Определение графа Рис. 10. Граф с бесконечным числом ребер
- 13. Определение графа Рис. 11. Бесконечный граф
- 14. Каноническое соответствие Каждому неориентированному графу канонически соответствует ориентированный граф с тем же множеством вершин, в котором
- 15. Каноническое соответствие Рис 12. Канонически соответствующие графы
- 16. Способы задания Задать граф – значит описать множества его вершин и ребер, а также отношение инцидентности.
- 17. Матрица инцидентности матрица инцидентности размера (строкам соответствуют ребра, столбцам – вершины графа), в которой для нграфа
- 18. Матрица инцидентности для орграфа
- 19. Пример: матрица инцидентности н-графа
- 20. Пример: матрица инцидентности ор-графа
- 21. Матрица смежности Матрица смежности размера , столбцам и строкам которой соответствуют вершины графа. Для нграфа равно
- 22. Матрица смежности Матрица смежности нграфа всегда симметрична. Матрица смежности орграфа в общем случае не симметрична. Она
- 23. Пример: матрица смежности н-графа
- 24. Пример: матрица смежности ор-графа
- 25. Список ребер Списком ребер можно задать граф без кратных ребер. Ребро представляется парой вершин, инцидентных ему,
- 26. Рисунок Рисунок или геометрическая интерпретация появляется, если сопоставить вершинам точки плоскости, ребрам – линии на плоскости,
- 27. Пример: список ребер н-графа E={(a,a), (a,b), (a,c), (b,c)}
- 28. Пример: список ребер ор-графа E={(a,a), (a,b), (a,c), (с,a), (b,c)}
- 29. Планарные графы На рисунке приведен пример не планарного графа Рис. 12 Граф «три дома - три
- 30. Изоморфные графы Графы, отличающиеся только нумерацией вершин, называются изоморфными.
- 32. Скачать презентацию