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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

1. ГРАФЫ И СПОСОБЫ ИХ ПРЕДСТАВЛЕНИЯ
1.1. Основные определения
Граф задается множеством точек или вершин х
1
, х
2
, ..., х
n
и множеством
линий или ребер a
1
, a
2
, ... , a
m
, соединяющих между собой все или часть точек.
Формальное определение графа может быть дано следующим образом:
Графом называется двойка вида
G = (X, A),
где X={x
i
},i=1,2,...,n - множество вершин графа,
A={a
i
},i=1,2, ... ,m -множество ребер графа.
Графы могут быть ориентированными, неориентированными и смешанными
(рис.2). Если ребра у множества A ориентированы, что обычно показывается
стрелкой, то они называются дугами, и граф с такими ребрами называется
ориентированным графом или орграфом (рис.2,а).
Если ребра не имеют ориентации, то граф называется неориентированным
(рис 2,б). Граф, в котором присутствуют и ребра, и дуги называется смешанным
(рис 2,в). В случае, когда G=(X, A) является орграфом, и мы хотим пренебречь
направленностью дуг из множества A, то неориентированный граф,
соответствующий G, будет обозначаться
GXA= (,)
и называться
неориентированным дубликатом или неориентированным двойником
(рис.2,г).
Дуга a
i
может быть представлена упорядоченной парой вершин (x
n
, x
k
),
состоящей из начальной x
n
и конечной x
k
вершин. Например, для графа G
1
(рис.2,а) дуга a
1
задается парой вершин (x
1
, x
2
), а дуга а
3
парой (x
2
, x
3
). Если x
n
, x
k
— концевые вершины дуги a
i
, то говорят, что вершины x
n
и x
k
инцидентны дуге a
i
или дуга a
i
инцидентна вершинам x
n
и x
k
.
Дуга, у которой начальная и конечная вершины совпадают, называется
петлей. В графе G
3
(рис.2,в) дуга а
7
является петлей.
x
1
x
2
x
3
x
4
a
6
a
5
a
4
a
3
a
1
a
2
x
4
x
5
x
2
x
3
x
1
a
2
a
1
a
3
a
4
a
5
x
1
x
5
x
4
x
5
x
2
a
1
a
3
a
2
a
4
a
5
a
6
a
7
x
1
x
4
x
3
x
2
а)
б)
в)
г)
Рис. 2. Виды графов: а) ориентированный граф G
;б
б)неориентированный граф G; в)
смешанный граф G
3
г)неориентированный дубликат графа G
.
                              1. ГРАФЫ И СПОСОБЫ ИХ ПРЕДСТАВЛЕНИЯ
                                                  1.1. Основные определения
    Граф задается множеством точек или вершин х1, х2, ..., хn и множеством
линий или ребер a1, a2, ... , am , соединяющих между собой все или часть точек.
Формальное определение графа может быть дано следующим образом:
     Графом называется двойка вида
             G                            =             (X,           A),
      где               X={xi},i=1,2,...,n  -   множество   вершин графа,
      A={ai},i=1,2, ... ,m -множество ребер графа.
     Графы могут быть ориентированными, неориентированными и смешанными
(рис.2). Если ребра у множества A ориентированы, что обычно показывается
стрелкой, то они называются дугами, и граф с такими ребрами называется
ориентированным графом или орграфом (рис.2,а).
                              x2                                        x1               a2
               a1 a                    a3                                                               x2
                    2
                        a4                        x3                                         a3
        x1                                                                   a1
                             a5                                                                        a4
                                   a6                                                    x3
                             x4
        а)                                                              x4              a5        x5
                                                                      б)

                                   x2                                              x2
                                                 a2
                 a1
       x   1
                                  a3                        x5
                   a4                                            x1                                    x3
                             a5
                                                       a6
                                            x4                                x4
                    x5             a7
        в)                                              г)
       Рис. 2. Виды графов: а) ориентированный граф G;б
            б)неориентированный граф G; в) смешанный граф G3
                  г)неориентированный дубликат графа G.

 Если ребра не имеют ориентации, то граф называется неориентированным
(рис 2,б). Граф, в котором присутствуют и ребра, и дуги называется смешанным
(рис 2,в). В случае, когда G=(X, A) является орграфом, и мы хотим пренебречь
направленностью дуг из множества A, то неориентированный граф,
                                                                      G = (X , A )
соответствующий G, будет обозначаться                                и называться
неориентированным дубликатом или неориентированным двойником
(рис.2,г).
     Дуга ai может быть представлена упорядоченной парой вершин (xn, xk),
состоящей из начальной xn и конечной xk вершин. Например, для графа G1
(рис.2,а) дуга a1 задается парой вершин (x1, x2), а дуга а3 парой (x2, x3). Если xn, xk
— концевые вершины дуги ai, то говорят, что вершины xn и xk инцидентны дуге ai
или дуга ai инцидентна вершинам xn и xk.
    Дуга, у которой начальная и конечная вершины совпадают, называется
петлей. В графе G3 (рис.2,в) дуга а7 является петлей.

Страницы