Специальная математика
| Вид материала | Конспект |
Содержание4.9. Приведение графа к ярусно-параллельной форме Ширина яруса |
- Направления работы семинара, 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.9. Приведение графа к ярусно-параллельной форме
Эти рассуждения имеют смысл для ориентированных графов без контуров.
Граф находится в ярусно-параллельной форме (ЯПФ),
если в нулевом ярусе размещаются вершины, имеющие нулевую полустепень захода, в i-том ярусе - вершины, в которые заходят дуги только из предыдущих ярусов, причем хотя бы одна дуга из (i - 1)-го яруса.
Пусть дан произвольный граф без циклов.
a
h b 
g c
f de
| | a | b | c | d | e | f | g | h |
| a | | | 1 | | | | | |
| b | | | | | | | | |
| c | | 1 | | | | | | |
| d | | | | | 1 | | | 1 |
| e | 1 | | | | | | 1 | |
| f | | | 1 | | | | | |
| g | | 1 | 1 | | | | | |
| h | 1 | | | | | 1 | | |
Алгоритм приведения к ЯПФ:
1. Матрица смежности графа просматривается, и в очередной ярус выбираются вершины с нулевой полустепенью захода, соответствующие нулевым столбцам.
2. Строки, соответствующие выбранным на предыдущем шаге вершинам, обнуляются.
3. Осуществляется возврат к шагу 1, до полного исчерпания матрицы.
4. Прорисовываются дуги.
В результате, вышеприведенный граф примет вид:
d
e h
g f a
c bШирина яруса определяется числом вершин в ярусе.
Ширина графа в ЯПФ определяется шириной самого большого яруса.