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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

ориентированной дуги, т.е.(x
j
, x
i
) ∉A (рис.13в.). Очевидно, что в
антисимметрическом графе нет петель.
В качестве примера можно рассмотреть граф, являющийся моделью
некоторой группы людей: вершины графа интерпретируют людей, а дуги - их
взаимоотношения. Так, если в графе дуга, нарисованная от вершины x
i
к вершине
x
j
, означает, что x
i
является другом или родственником x
j
, тогда данный граф
должен быть симметрическим. Если дуга, направленная от x
i
к x
j
, означает, что
вершина x
j
подчинена вершине x
i
, то такой граф должен быть
антисимметрическим.
Комбинируя определения полного и симметрического графов и полного и
антисимметрического графов, получили следующие определения:
• Граф G =(X, A), в котором любая пара вершин (x
i
, x
j
) соединена
двунаправленными дугами называется полным симметрическим. (рис. 13. г)
• Граф G =(X, A), имеющий для каждой пары вершин (x
i
, x
j
) только одну
дугу, называется полным антисимметрическим. (Рис 13. д) или
турниром.
Связный граф , не имеющий циклов, либо граф , в котором каждая пара
вершин соединена одной и только одной простой цепью называется деревом
(рис.14 а, б).
Ориентированное дерево представляет собой ориентированный граф без
циклов, в котором полустепень захода каждой вершины , за исключением одной
(например, вершины x
1
), равна 1, а полустепень захода вершины x
1
, (называют
корнем этого дерева) равна 0.(рис.14 б).
Граф G =(X, A), который может быть изображен на плоскости или сфере без
пересечений называется планарным. (рис.15)
x
1
x
2
x
3
x
5
x
6
x
1
x
2
x
3
x
5
x
6
Рис. 15. Планарный граф
x
1
x
1
x
7
x
5
x
2
x
4
x
3
x
6
x
1
x
2
x
4
x
5
x
3
x
11
x
12
x
10
x
9
x
8
x
7
x
6
а)
б
)
Рис. 14. Граф типа “дерево”: а) - неориентированное
дерево, б) - ориентированное дерево
ориентированной дуги, т.е.(xj, xi) ∉A (рис.13в.).                                                     Очевидно, что в
антисимметрическом графе нет петель.
      В качестве примера можно рассмотреть граф, являющийся моделью
некоторой группы людей: вершины графа интерпретируют людей, а дуги - их
взаимоотношения. Так, если в графе дуга, нарисованная от вершины xi к вершине
xj, означает, что xi является другом или родственником xj, тогда данный граф
должен быть симметрическим. Если дуга, направленная от xi к xj, означает, что
вершина       xj   подчинена вершине xi, то такой граф должен быть
антисимметрическим.
    Комбинируя определения полного и симметрического графов и полного и
антисимметрического графов, получили следующие определения:
        • Граф G =(X, A), в котором любая пара вершин (xi, xj) соединена
   двунаправленными дугами называется полным симметрическим. (рис. 13. г)
        • Граф G =(X, A), имеющий для каждой пары вершин (xi, xj) только одну
   дугу, называется     полным антисимметрическим. (Рис 13. д) или
   турниром.
     Связный граф , не имеющий циклов, либо граф , в котором каждая пара
вершин соединена одной и только одной простой цепью называется деревом
(рис.14 а, б).
                                                                                     x1
                          x2                                          x2
                                                                                                           x6
                                    x4        x3
                                                                 x4             x3         x7
           x1                                                                        x11
                                              x6            x5                             x10
                                                                                                            x8
                                x5
                     x7                                                              x12              x9

                               а)                                                         б)
                 Рис. 14. Граф типа “дерево”: а) - неориентированное
                 дерево, б) - ориентированное дерево



     Ориентированное дерево представляет собой ориентированный граф без
циклов, в котором полустепень захода каждой вершины , за исключением одной
(например, вершины x1), равна 1, а полустепень захода вершины x1, (называют
корнем этого дерева) равна 0.(рис.14 б).
    Граф G =(X, A), который может быть изображен на плоскости или сфере без
пересечений называется планарным. (рис.15)
                                                                                 x2
                          x2


                                                                 x1
      x1                                                                                                        x3
                                              x3



                                                                           x5                    x6
                x5                       x6

                                         Рис. 15. Планарный граф

Страницы