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

UptoLike

ВУЗ: 

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

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

Рубрика: 

162
Типовые контрольные работы
Контрольная работа №1
1. Представить в виде ориентированного графа от-
ношение
ρ = (V, E), V = {2, 4, 16, 22},
E = {(х, у) : х / у – четно}.
2. Ориентированный граф G c множеством вершин
V = {1, 2, 3, 4, 5, 6, 7} задан списком дуг
{(1, 6), (2, 1), (2, 3), (3, 1), (3, 3), (3, 3), (3, 4),
(3, 6), (5, 1), (5, 6), (5, 6), (5, 6), (7, 4), (7, 6)}.
Построить реализацию графа, матрицу инцидент-
ности и матрицы соседства вершин для ориенти-
рованного и соответственного ему неориентиро-
ванного графов.
3. Найти матрицу расстояний, диаметр и радиус
графа, определить центральные вершины.
4. Для графа, представленного следующей матри-
цей смежности, определите матрицу инцидентно-
сти графа и изобразите его графически
15
на x
1
инцидентна дугам a
1
и a
2
; G (x
1
) = {x
2
, x
3
},
G.(x
2
) = ∅, G
.–1
(x
3
) = {x
1
}, G
.–1
(x
1
) = ∅.
Определение 1.12. Подграфом графа G называет-
ся граф, все вершины и ребра которого содержатся
среди вершин и ребер графа G. Подграф называет-
ся собственным, если он отличен от самого графа.
Определение 1.13. Граф G = (X, A) – полный, если
для любой пары вершин x
i
и x
j
существует ребро
(x
i
, x
j
).
Определение 1.14. Граф G = (X, A) – симметриче-
ский, если для любой дуги (x
i
, x
j
) существует про-
тивоположно ориентированная дуга (x
j
, x
i
).
Определение 1.15. Граф G = (X, A) – планарный,
если он может быть изображен на плоскости так,
что не будет пересекающихся дуг.
Определение 1.16. Неориентированный граф G =
= (X, A) – двудольный, если множество его вершин
X можно разбить на два подмножества X
1
и X
2
, что
каждое ребро имеет один конец в X
1
, а другой в X
2
.
Заметим, что граф К
m,n
имеет ровно m + n
вершин и m
⋅n ребер.
Рис. 5. Двудольные графы 
          Типовые контрольные работы                         на x1 инцидентна дугам a1 и a2; G (x1) = {x2, x3},
                                                             G.(x2) = ∅, G.–1(x3) = {x1}, G.–1(x1) = ∅.
               Контрольная работа №1
                                                             Определение 1.12. Подграфом графа G называет-
1. Представить в виде ориентированного графа от-             ся граф, все вершины и ребра которого содержатся
ношение                                                      среди вершин и ребер графа G. Подграф называет-
              ρ = (V, E), V = {2, 4, 16, 22},                ся собственным, если он отличен от самого графа.
              E = {(х, у) : х / у – четно}.                  Определение 1.13. Граф G = (X, A) – полный, если
2. Ориентированный граф G c множеством вершин                для любой пары вершин xi и xj существует ребро
V = {1, 2, 3, 4, 5, 6, 7} задан списком дуг                  (xi, xj).
                                                             Определение 1.14. Граф G = (X, A) – симметриче-
  {(1, 6), (2, 1), (2, 3), (3, 1), (3, 3), (3, 3), (3, 4),   ский, если для любой дуги (xi, xj) существует про-
  (3, 6), (5, 1), (5, 6), (5, 6), (5, 6), (7, 4), (7, 6)}.   тивоположно ориентированная дуга (xj, xi).
Построить реализацию графа, матрицу инцидент-                Определение 1.15. Граф G = (X, A) – планарный,
ности и матрицы соседства вершин для ориенти-                если он может быть изображен на плоскости так,
рованного и соответственного ему неориентиро-                что не будет пересекающихся дуг.
ванного графов.                                              Определение 1.16. Неориентированный граф G =
3. Найти матрицу расстояний, диаметр и радиус                = (X, A) – двудольный, если множество его вершин
графа, определить центральные вершины.                       X можно разбить на два подмножества X1 и X2, что
                                                             каждое ребро имеет один конец в X1, а другой в X2.




4. Для графа, представленного следующей матри-
цей смежности, определите матрицу инцидентно-                               Рис. 5. Двудольные графы
сти графа и изобразите его графически
                                                                  Заметим, что граф К    m,n   имеет ровно m + n
                                                             вершин и m⋅n ребер.


                                 162                                                    15

Страницы