Содержание
- 2. Граф G = (V, R) V – множество вершин R - множество ребер, соединяющих пару вершин
- 3. вершины V1 V2 V3 V4 R23 R14 R15 R45 R35 R25 R34 V5 смежные не смежные
- 4. Степень вершины V1 V2 V3 V4 R23 R14 R15 R45 R35 R25 R34 V5 R12 -
- 5. Маршрут графа - последовательность чередующихся вершин и ребер V1 V2 V3 V4 R23 R14 R15 R45
- 6. Ориентированный граф каждое ребро (дуга) имеет одно направление. Дуга – упорядоченная пара вершин. входящая степень вершины
- 7. V1 V2 V3 V4 R23 R14 R34 R12 R21 R32 Определите входящие и исходящие степени вершин
- 8. 4 3 5 7 8 5 5 Взвешенный граф (сеть) ребрам или дугам графа поставлены в
- 9. Матрица смежности - табличная форма представления графа номера вершин несмежные вершины
- 10. 4 3 5 7 8 5 5 V1 V2 V3 V4 R23 R14 R34 R12 R32
- 11. Подграф граф, у которого все вершины и ребра принадлежат исходному графу. V1 V2 V3 V4 R23
- 12. Остовной связной подграф подграф, содержащий все вершины исходного графа и каждая вершина достижима из любой другой.
- 13. Дерево граф, в котором нет циклов. V3 V4 R23 R14 R15 R45 R35 R25 R34 V5
- 14. ПРЕОБРАЗОВАНИЕ ГРАФА В ОСТОВНОЕ СВЯЗНОЕ ДЕРЕВО МИНИМАЛЬНОГО ВЕСА. цикломатическое число γ = m – n +
- 15. Преобразовать граф в остовные связные деревья: V3 V4 R23 R15 R45 R35 R25 R34 V5 R12
- 16. Алгоритм Крускала Построение остовного связного дерева минимального веса. 1. Удалить из графа все ребра остовной подграф
- 17. 2. Сортировка ребер по возрастанию весов. V3 V4 R23 R15 R45 R35 R25 R34 V5 R12
- 18. R25 7 R23 6 R45 4 3 3. Ребра последовательно включают в остовное дерево по возрастанию
- 20. Скачать презентацию