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

UptoLike

ВУЗ: 

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

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

Рубрика: 

12
Рис. 3.
Определение 1.4. Граф называется простым, если
каждую пару вершин соединяет не более чем одно
ребро.
Определение 1.5. Граф, имеющий как ориентиро-
ванные, так и неориентированные ребра, называ-
ется смешанным.
Различные ребра могут соединять одну и ту
же пару вершин. Такие ребра называют кратными
.
Определение 1.6.
Граф, содержащий кратные реб-
ра, называется мультиграфом.
Неориентированное ребро графа эквива-
лентно двум противоположно направленным ду-
гам, соединяющим те же самые вершины.
Ребро может соединять вершину саму с со-
бой. Такое ребро называется петлей.
Определение 1.7. Граф с кратными ребрами и
петлями называется
псевдографом.
Множество ребер графа может быть пустым.
Множество вершин графа не может быть пустым.
165
12BЗадачи для самостоятельного решения
1. Описать граф, заданный матрицей смежности,
используя как можно больше характеристик. Со-
ставить матрицу инцидентности и связности
(сильной связности).
2. Пользуясь алгоритмом Форда-Беллмана, найти
минимальный путь из x
1
в x
7
в ориентированном
графе, заданном матрицей весов.
3. Пользуясь алгоритмом Краскала, найти мини-
мальное остовное дерево для графа, заданного
матрицей длин ребер.
Варианты заданий
1.1 1.2 1.3
0 1 1 0 1 1 4 6 12
∞ ∞ ∞ ∞ ∞
12 6 20 14
1 0 0 1 0 0
∞ ∞ ∞
13 7
∞ ∞
12
∞
2 4 6
1 0 0 0 1 0
∞ ∞ ∞
5
∞
3
∞
6 2
∞
10 12
0 1 0 0 1 0
∞ ∞ ∞ ∞
10 9
∞
20 4 10
∞
6
1 0 1 1 0 1
∞ ∞ ∞ ∞ ∞ ∞
8 14 6 12 6
∞
1 0 0 0 1 0
∞ ∞ ∞ ∞ ∞ ∞
11
∞ ∞ ∞ ∞ ∞
∞ ∞
2.1 2.2 2.3
1 0 0 0 0 1
∞
1 3 9
∞ ∞ ∞ ∞
1
∞
4 5
0 0 1 1 1 0
∞ ∞ ∞
10 4
∞ ∞
1
∞
2
∞
1
0 0 0 0 0 0
∞ ∞ ∞
5
∞
1
∞ ∞
2
∞
1 1
1 0 0 0 0 1
∞ ∞ ∞ ∞
7 6
∞
4
∞
1
∞
3
1 0 1 0 0 0
∞ ∞ ∞ ∞ ∞ ∞
5 5 1 1 3
∞
1 0 1 0 0 0
∞ ∞ ∞ ∞ ∞ ∞
8
∞ ∞ ∞ ∞ ∞ ∞ ∞
3.1 3.2 3.3 
                                                            Задачи для самостоятельного решения
                                                            12B




                                                    1. Описать граф, заданный матрицей смежности,
                                                    используя как можно больше характеристик. Со-
                                                    ставить матрицу инцидентности и связности
                                                    (сильной связности).
                                                    2. Пользуясь алгоритмом Форда-Беллмана, найти
                    Рис. 3.
                                                    минимальный путь из x1 в x7 в ориентированном
Определение 1.4. Граф называется простым, если      графе, заданном матрицей весов.
каждую пару вершин соединяет не более чем одно      3. Пользуясь алгоритмом Краскала, найти мини-
ребро.                                              мальное остовное дерево для графа, заданного
Определение 1.5. Граф, имеющий как ориентиро-       матрицей длин ребер.
ванные, так и неориентированные ребра, называ-                      Варианты заданий
ется смешанным.                                   1.1              1.2                1.3
      Различные ребра могут соединять одну и ту   0     1   1     0   1   1   4   6   12   ∞    ∞     ∞   ∞    ∞     12   6    20   14
                                                  1     0   0     1   0   0   ∞   ∞   ∞    13   7     ∞   ∞    12    ∞    2    4    6
же пару вершин. Такие ребра называют кратными.    1     0   0     0   1   0   ∞   ∞   ∞    5    ∞     3   ∞    6     2    ∞    10   12
Определение 1.6. Граф, содержащий кратные реб-    0     1   0     0   1   0   ∞   ∞   ∞    ∞    10    9   ∞    20    4    10   ∞    6
ра, называется мультиграфом.                      1     0   1     1   0   1   ∞   ∞   ∞    ∞    ∞     ∞   8    14    6    12   6    ∞
                                                  1     0   0     0   1   0   ∞   ∞   ∞    ∞    ∞     ∞   11
      Неориентированное ребро графа эквива-                                   ∞   ∞   ∞    ∞    ∞     ∞   ∞
лентно двум противоположно направленным ду-
гам, соединяющим те же самые вершины.             2.1                         2.2                              2.3
      Ребро может соединять вершину саму с со-    1     0   0     0   0   1   ∞   1   3    9     ∞    ∞   ∞    ∞     1    ∞    4    5
                                                  0     0   1     1   1   0   ∞   ∞   ∞    10    4    ∞   ∞    1     ∞    2    ∞    1
бой. Такое ребро называется петлей.               0     0   0     0   0   0   ∞   ∞   ∞    5     ∞    1   ∞    ∞     2    ∞    1    1
Определение 1.7. Граф с кратными ребрами и        1     0   0     0   0   1   ∞   ∞   ∞    ∞     7    6   ∞    4     ∞    1    ∞    3
петлями называется псевдографом.                  1     0   1     0   0   0   ∞   ∞   ∞    ∞     ∞    ∞   5    5     1    1    3    ∞
                                                  1     0   1     0   0   0   ∞   ∞   ∞    ∞     ∞    ∞   8
      Множество ребер графа может быть пустым.                                ∞   ∞   ∞    ∞     ∞    ∞   ∞
Множество вершин графа не может быть пустым.
                                                  3.1                         3.2                              3.3

                         12                                                                     165

Страницы