Специальная математика
| Вид материала | Конспект |
Содержание4.8. Определение путей в графе |
- Направления работы семинара, 152.43kb.
- «Математика. Прикладная математика», 366.03kb.
- Программа подраздела «Философские проблемы математики», 94.9kb.
- Рабочая программа по курсу «Специальная педагогика и специальная психология» на 5 курсе, 94.48kb.
- Специальная обработка, 1624.5kb.
- Расшифровка : Математика, 146.94kb.
- Abramson Family Cancer Research Institute University of Pennsylvania (usa) Роль апоптоза, 15.2kb.
- Программа дисциплины "Математика и информатика" (раздел «Математика») (специальность:, 399.2kb.
- Пангеометризм и математическая мифология, 956.71kb.
- Строительство. Система производственного контроля. Часть, 84.92kb.
4.8. Определение путей в графе
a b 
g 
c
f 
e d Требуемые результаты получаются путем перемножения матриц смежности графа.
M - матрица смежностей, показывает пути длиной в 1 в данном графе.
| | a | b | c | d | e | f | g |
| a | | | | 1 | 1 | | |
| b | | 1 | | | | | |
| c | | | | | | | |
| d | | | | | | | 1 |
| e | | | 1 | 1 | | | |
| f | | | 1 | | 1 | | |
| g | | 1 | | | | | |
| | a | b | c | d | e | f | g |
| a | | | | 1 | 1 | | |
| b | | 1 | | | | | |
| c    | | | | | | | |
| d | | | | | | | 1 |
| e | | | 1 | 1 | | | |
| f | | | 1 | | 1 | | |
| g | | 1 | | | | | |
M M
Матрица M2 дает все пути длиной в 2
| | a | b | c | d | e | f | g |
| a | | | | | | | 1 |
| b | | | | | | | |
| c | | | | | | | |
| d | | 1 | | | | | |
| e | | | | | | | 1 |
| f | | 1 | | 1 | | | |
| g | | | | | | | |
Матрица Мn - пути длиной в n.
Если Мi - нулевая матрица, то наибольший путь в графе имеет длину i - 1.
Для определения наличия путей между двумя вершинами можно использовать «транзитивное замыкание» матриц
M* = M1 M2 M3 ...
Непустая клеточка ij будет говорить о наличии пути из i-ой вершины в j-ую.