Компьютерная математика: Часть 2. Теория графов. Волченская Т.В - 10 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

Граф описывается перечислением множества
вершин и дуг. Примеры описания приведены для
орграфов на рис.3 и рис. 4.
G
4
=(Х, А),
где Х = { х
i
}, i=1,2,3,4 - множество вершин;
А = { a
i
}, i=1,2,...,6 - множество дуг, причем А={(x
1
,
x
2
), (x
4
, x
2
), (x
2
, x
4
), (x
2
, x
3
), (x
3
, x
3
), (x
4
, x
1
)}.
G
5
=(X, A),
где X={B, C, D, E, F} - множество вершин графа,
A={a
i
}, i=1,2,...,5 - множество дуг графа,
причем a
1
=(F, B), a
2
=(B, E), a
3
=(F, D),
a
4
=(E, C), a
5
=(C, D).
1.2.2. Задание графов соответствием
Описание графов состоит в задании множества вершин Х и соответствия Г,
которое показывает, как между собой связаны вершины.
Соответствием Г называется отображение множества Х в Х, а граф в
этом случае обозначается парой G=(X, Г).
Отображением вершины x
i
— Г(x
i
) является множество вершин, в
которые существуют дуги из вершины x
i
, то есть Г(x
i
)={ x
j
:∃ дуга (x
i
, x
j
)∈A}.
Так для орграфа на рис.3 описание заданием множества вершин и
соответствия выглядит следующим образом:
G
4
=(X, Г)),
где X={x
i
}, i=1,2,...,4 - множество вершин,
Г(х
1
)={ x
2
}, Г(x
2
)={ x
3
, x
4
}, Г(x
3
)={ x
3
}, Г(x
4
)={ x
1
, x
2
} - отображения.
Для неориентированного или смешанного графов предполагается, что
соответствие Г задает такой эквивалентный ориентированный граф, который
получается из исходного графа заменой каждого ориентированного ребра двумя
противоположно направленными дугами, соединяющими те же самые вершины.
Например, для графа на рис.2,б Г(х
2
)={ x
1
, x
3
, x
5
}, Г(x
4
)={ x
3
, x
5
} и т.д.
1.2.3. Матричное представление графов
Для обработки на ЭВМ графы удобно представлять в виде матриц
смежности и инциденций.
Матрица смежности - это квадратная матрица размерностью n*n,(где n -
число вершин графа), однозначно представляющая его структуру.
A={a
ij
}, i,j= 1,2,...,n, а каждый элемент матрицы определяется следующим
образом:
a
ij
=1, если ∃ дуга (x
i
, x
j
),
a
ij
=0, если нет дуги (x
i
, x
j
).
x
1
x
4
x
2
x
3
a
1
a
6
a
2
a
3
a
4
a
5
Рис. 3. Орграф G
4
F
D
E
B
C
a
3
a
2
a
1
a
4
a
5
Рис. 4. Орграф G
5
                                                    Граф описывается перечислением множества
                    x2                       вершин и дуг. Примеры описания приведены для
                              a4             орграфов на рис.3 и рис. 4.
      a1                                            G4=(Х, А),
                                    x3       где Х = { хi }, i=1,2,3,4 - множество вершин;
x1          a2
                              a3                    А = { ai }, i=1,2,...,6 - множество дуг, причем А={(x1,
                                    a5       x2), (x4, x2), (x2, x4), (x2, x3), (x3, x3), (x4, x1)}.
      a6

                    x4
     Рис. 3. Орграф G4
                                              G5=(X, A),
                          B
                                              где X={B, C, D, E, F} - множество вершин графа,
           a1                                 A={ai}, i=1,2,...,5 - множество дуг графа,
                a2                            причем a1=(F, B), a2=(B, E), a3=(F, D),
     F                         a4        C
                     a3                       a4=(E, C), a5=(C, D).
                                     a5

                E             D
     Рис. 4. Орграф G5
                                    1.2.2. Задание графов соответствием

       Описание графов состоит в задании множества вершин Х и соответствия Г,
 которое показывает, как между собой связаны вершины.
       Соответствием Г называется отображение множества Х в Х, а граф в
 этом случае обозначается парой G=(X, Г).
       Отображением вершины xi — Г(xi) является множество вершин, в
 которые существуют дуги из вершины xi, то есть Г(xi)={ xj:∃ дуга (xi, xj)∈A}.
       Так для орграфа на рис.3 описание заданием множества вершин и
 соответствия                  выглядит                  следующим                 образом:
       G4=(X, Г)),
       где X={xi}, i=1,2,...,4 - множество вершин,
       Г(х1)={ x2 }, Г(x2)={ x3, x4 }, Г(x3)={ x3 }, Г(x4)={ x1, x2 } - отображения.
       Для неориентированного или смешанного графов предполагается, что
 соответствие Г задает такой эквивалентный ориентированный граф, который
 получается из исходного графа заменой каждого ориентированного ребра двумя
 противоположно направленными дугами, соединяющими те же самые вершины.
 Например, для графа на рис.2,б Г(х2)={ x1, x3, x5 }, Г(x4)={ x3, x5} и т.д.

                                   1.2.3. Матричное представление графов
       Для обработки на ЭВМ графы удобно представлять в виде матриц
 смежности и инциденций.
       Матрица смежности - это квадратная матрица размерностью n*n,(где n -
 число вершин графа), однозначно представляющая его структуру.
       A={aij}, i,j= 1,2,...,n, а каждый элемент матрицы определяется следующим
 образом:
       aij=1, если ∃ дуга (xi, xj),
       aij=0, если нет дуги (xi, xj).

Страницы