Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Эти рассуждения имеют смысл для ориентированных графов без контуров.
Граф находится в ярусно-параллельной форме (ЯПФ),
если в нулевом ярусе размещаются вершины, имеющие нулевую полустепень захода, в i-том ярусе - вершины, в которые заходят дуги только из предыдущих ярусов, причем хотя бы одна дуга из (i - 1)-го яруса.
Пусть дан произвольный граф без циклов.
a
h b
g c
f d
e
a | b | c | d | e | f | g | h | |
a | ||||||||
b | ||||||||
c | ||||||||
d | ||||||||
e | ||||||||
f | ||||||||
g | ||||||||
h |
Алгоритм приведения к ЯПФ:
1. Матрица смежности графа просматривается, и в очередной ярус выбираются вершины с нулевой полустепенью захода, соответствующие нулевым столбцам.
2. Строки, соответствующие выбранным на предыдущем шаге вершинам, обнуляются.
3. Осуществляется возврат к шагу 1, до полного исчерпания матрицы.
4. Прорисовываются дуги.
В результате, вышеприведенный граф примет вид:
d
e h
g f
a
c
b
Ширина яруса определяется числом вершин в ярусе.
Ширина графа в ЯПФ определяется шириной самого большого яруса.
Дата публикования: 2014-11-03; Прочитано: 456 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!