Практикум по курсу "Алгоритмизация и программирование". Часть 2. Андрианова А.А - 107 стр.

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

. Практикум по курсу «Алгоритмизация и программирование». Часть 2
ленными ребрами от родителя к потомку.
Источник графа – это вершина, из которой достижимы все остальные вер-
шины (из этой вершины можно построить путь в любую вершину графа).
Сток графа – это вершина, достижимая из всех других вершин.
Каркасом называется дерево, содержащее все вершины исходного графа
и часть его ребер. Граф может иметь несколько каркасов. Каркасами для гра-
фа, представленного на рис. 7.1, являются следующие графы (деревья):
Рис. 7.4. Каркасы графа, изображенного на рис. 7.1.
Приведем часто используемые способы представления графов.
1. Матрица инцидентности
A(n, m)={a
i j
},
где n – число вершин, а m – число ребер графа
1, вершина i инцидентна ребру j
a
i j
=
0, вершина i и ребро j не инцидентны
В каждом столбце такой матрицы содержится ровно две единицы. Равных
столбцов в матрице нет.
Приведем пример матрицы инцидентности для графа, изображенного на
рис. 7.1.
<1,2> <1,3> <2,3> <3,4>
1 1 1 0 0
A =
2 1 0 1 0
3 0 1 1 1
4 0 0 0 1
107
              .        Практикум по курсу «Алгоритмизация и программирование». Часть 2
ленными ребрами от родителя к потомку.
    Источник графа – это вершина, из которой достижимы все остальные вер-
шины (из этой вершины можно построить путь в любую вершину графа).
Сток графа – это вершина, достижимая из всех других вершин.
    Каркасом называется дерево, содержащее все вершины исходного графа
и часть его ребер. Граф может иметь несколько каркасов. Каркасами для гра-
фа, представленного на рис. 7.1, являются следующие графы (деревья):




                   Рис. 7.4. Каркасы графа, изображенного на рис. 7.1.


   Приведем часто используемые способы представления графов.

   1. Матрица инцидентности
   A(n, m)={a i j},
   где n – число вершин, а m – число ребер графа

            1, вершина i инцидентна ребру j
   a ij =
            0, вершина i и ребро j не инцидентны

    В каждом столбце такой матрицы содержится ровно две единицы. Равных
столбцов в матрице нет.
    Приведем пример матрицы инцидентности для графа, изображенного на
рис. 7.1.
                               <1,2>     <1,3>      <2,3> <3,4>
                         1         1         1         0       0
                         2         1          0        1         0
                  A=
                         3         0          1        1         1
                         4         0          0        0         1


                                        107

Страницы