Специальная математика. Соловьев А.Е. - 57 стр.

Алгоритм приведения к ЯПФ:
1. Матрица смежности графа просматривается, и в очередной ярус выбираются вершины с
нулевой полустепенью захода, соответствующие нулевым столбцам.
2. Строки, соответствующие выбранным на предыдущем шаге вершинам, обнуляются.
3. Осуществляется возврат к шагу 1, до полного исчерпания матрицы.
4. Прорисовываются дуги.
В результате, вышеприведенный граф примет вид:

                            d



            e                               h


            g                               f
                                a

                                    c



                                b

Ширина яруса определяется числом вершин в ярусе.
Ширина графа в ЯПФ определяется шириной самого большого яруса.

                                4.10. Внутренняя устойчивость графа

Множество внутренней устойчивости - множество несмежных вершин графа.

                        a

            f                               b


                e                       c


                        d


    a   b       c   d   e    f
a               1
b   1                   1
c                            1
d       1               1
e               1
f       1           1   1




                                                — 57 —