Основные понятия теории графов. Гладких О.Б - 13 стр.

UptoLike

ВУЗ: 

ЕГУ им. Бунина | Елец

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

Рубрика: 

164
рованного и соответственного ему неориентиро-
ванного графов.
3. Найти матрицу расстояний, диаметр и радиус
графа, определить центральные вершины.
4. Для графа, представленного следующей матри-
цей смежности, определите матрицу инцидентно-
сти графа и изобразите его графически
01110
10001
10010
10101
01010
⎡
⎤
⎢
⎥
⎢
⎥
⎢
⎥
⎢
⎥
⎢
⎥
⎢
⎥
⎣
⎦
5. Ориентированный граф с множеством вершин
{1, 2, 3, 4, 5, 6, 7} задан списком дуг
{(1, 4), (1, 6), (2, 1), (2, 2), (2, 6), (2, 6),
(3, 2), (3, 4), (3, 6), (4, 6),(5, 2), (5, 4),
(5, 4), (5, 5), (6, 2), (6, 5), (7, 1), (7, 6)}.
Построить реализацию графа, матрицу инцидент-
ности и матрицу соседства вершин.
13
Пример 1.3.
На рис. 4. изображен ориентированный граф
G = (X, A).
X = {x
1
, x
2
, x
3
, x
4
},
A
=
∅
.
Рис. 4.
Как в случае ориентированного, так и в слу-
чае неориентированного ребра говорят, что вер-
шины x
и y инцидентны ребру a, если эти верши-
ны соединены a.
Определение 1.8. Две вершины называются
смежными, если они инцидентны одному и тому
же ребру. Два ребра называются смежными, если
они имеют общую вершину.
Определение 1.9. Степенью вершины графа на-
зывается число ребер, инцидентных этой вершине.
Вершина, имеющая степень 0, называется
изолированной, а степень 1 – висячей.
Необходимость учитывать ориентацию ре-
бер в орграфе приводит к расщеплению понятия
«степень вершины» на две части: полустепенью
захода вершины v
i
(d
–
(v
i
)) называется число ребер,
заходящих в v
i
, полустепенью исхода v
i
(d
+
(v
i
)) –
число ребер, выходящих из нее. 
рованного и соответственного ему неориентиро-                                   Пример 1.3.
ванного графов.                                                На рис. 4. изображен ориентированный граф
3. Найти матрицу расстояний, диаметр и радиус            G = (X, A).
графа, определить центральные вершины.                         X = {x1, x2, x3, x4},
                                                               A = ∅.



                                                                                Рис. 4.
4. Для графа, представленного следующей матри-                Как в случае ориентированного, так и в слу-
цей смежности, определите матрицу инцидентно-            чае неориентированного ребра говорят, что вер-
сти графа и изобразите его графически                    шины x и y инцидентны ребру a, если эти верши-
                    ⎡0    1 1 1 0⎤                       ны соединены a.
                    ⎢1    0 0 0 1⎥                       Определение 1.8. Две вершины называются
                    ⎢              ⎥                     смежными, если они инцидентны одному и тому
                    ⎢1    0 0 1 0⎥
                    ⎢              ⎥                     же ребру. Два ребра называются смежными, если
                    ⎢1    0 1 0 1⎥
                                                         они имеют общую вершину.
                    ⎢⎣0   1 0 1 0 ⎥⎦                     Определение 1.9. Степенью вершины графа на-
                                                         зывается число ребер, инцидентных этой вершине.
5. Ориентированный граф с множеством вершин
                                                              Вершина, имеющая степень 0, называется
{1, 2, 3, 4, 5, 6, 7} задан списком дуг
                                                         изолированной, а степень 1 – висячей.
      {(1, 4), (1, 6), (2, 1), (2, 2), (2, 6), (2, 6),        Необходимость учитывать ориентацию ре-
      (3, 2), (3, 4), (3, 6), (4, 6),(5, 2), (5, 4),     бер в орграфе приводит к расщеплению понятия
      (5, 4), (5, 5), (6, 2), (6, 5), (7, 1), (7, 6)}.   «степень вершины» на две части: полустепенью
                                                         захода вершины vi (d – (vi)) называется число ребер,
Построить реализацию графа, матрицу инцидент-            заходящих в vi, полустепенью исхода vi (d + (vi)) –
ности и матрицу соседства вершин.                        число ребер, выходящих из нее.


                               164                                                   13

Страницы