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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

Каждая вершина орграфа x
i
может характеризоваться полустепенью исхода
d
0
(x
i
) и полустепенью захода d
t
(x
i
).
Полустепенью исхода вершины x
i
— d
0
(x
i
) называется количество дуг,
исходящих из этой вершины. Например, для орграфа G
1
(рис.2,а) характеристики
полустепеней исхода следующие: d
0
(x
1
)=1, d
0
(x
2
)=2, d
0
(x
3
)=2, d
0
(x
4
)=1.
Полустепенью захода вершины x
i
— d
t
(x
i
) называется количество дуг,
входящих в эту вершину. Например, для орграфа G
1
: d
t
(x
1
)=2, d
t
(x
2
)=1, d
t
(x
3
)=2,
d
t
(x
4
)=1.
Очевидно, что сумма полустепеней исхода всех вершин графа, а также
сумма полустепеней захода всех вершин графа равна общему числу дуг графа,
т.е.
() ()
0
11
dx dx
i
i
n
ti
i
n
m
==
∑∑
==
,
где n-число вершин графа, m-число дуг.
Каждая вершина неориентированного графа x
i
может характеризоваться
степенью вершины d(x
i
).
Степенью вершины x
i
— d(x
i
) называется количество ребер,
инцидентных этой вершине. Например, для орграфа G
1
(рис.2,б) характеристики
степеней следующие: d(x
1
)=2, d(x
2
)=3, d(x
3
)=2, d(x
4
)=2.
Алгоритм и программа нахождения характеристик графа приведены в
прил.1.
. Упражнения 1.1 .
1. Какого типа граф изображен на рисунке?
Ответ: . . . . . . . . . . . . . .
2. Какие вершины инцидентны дуге f ?
Ответ: . . . . . . . . . . . . . .
3. Какие дуги инцидентны вершине 3 ?
Ответ: . . . . . . . . . . . . . .
4. Перечислите дуги, являющиеся петлями?
Ответ: . . . . . . . . . . . . . .
5. Найдите полустепени исхода и захода для всех вершин графа.
Ответ: d
0
(x
1
)=. . ., d
0
(x
2
)= . . ., d
0
(x
3
)= . . ., d
t
(x
1
)=. . ., d
t
(x
2
)= . . ., d
t
(x
3
)=. . ..
. .
1.2 Способы описания графов
1.2.1. Теоретико-множественное представление графов
1
2
3
a
c
b d
e
f 
      Каждая вершина орграфа xi может характеризоваться полустепенью исхода
d0(xi) и полустепенью захода dt(xi).
    Полустепенью исхода вершины xi — d0(xi) называется количество дуг,
исходящих из этой вершины. Например, для орграфа G1 (рис.2,а) характеристики
полустепеней исхода следующие: d0(x1)=1, d0(x2)=2, d0(x3)=2, d0(x4)=1.
      Полустепенью захода вершины xi — dt(xi) называется количество дуг,
входящих в эту вершину. Например, для орграфа G1: dt(x1)=2, dt(x2)=1, dt(x3)=2,
dt(x4)=1.
     Очевидно, что сумма полустепеней исхода всех вершин графа, а также
сумма полустепеней захода всех вершин графа равна общему числу дуг графа,
т.е.
       n             n
      ∑ d 0 (x i ) = ∑ d t (x i ) = m ,
      i =1           i =1

      где n-число вершин графа, m-число дуг.
     Каждая вершина     неориентированного графа xi может характеризоваться
степенью вершины d(xi).
     Степенью     вершины       xi — d(xi) называется количество ребер,
инцидентных этой вершине. Например, для орграфа G1 (рис.2,б) характеристики
степеней следующие: d(x1)=2, d(x2)=3, d(x3)=2, d(x4)=2.


    Алгоритм и           программа        нахождения характеристик графа приведены в
прил.1.


.     Упражнения 1.1                                                                            .
1. Какого типа граф изображен на рисунке?
Ответ: . . . . . . . . . . . . . .                                            1     a

2. Какие вершины инцидентны дуге f ?
Ответ: . . . . . . . . . . . . . .                         d                            b
                                                                                                    c
                                                                          e
3. Какие дуги инцидентны вершине 3 ?                                                        2
Ответ: . . . . . . . . . . . . . .
                                                           3
4. Перечислите дуги, являющиеся петлями?
                                                                              f
Ответ: . . . . . . . . . . . . . .

5. Найдите полустепени исхода и захода для всех вершин графа.
Ответ: d0(x1)=. . ., d0(x2)= . . ., d0(x3)= . . ., dt(x1)=. . ., dt(x2)= . . ., dt(x3)=. . ..
.                                                                                               .

                                  1.2     Способы описания графов
           1.2.1. Теоретико-множественное представление графов

Страницы