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

UptoLike

ВУЗ: 

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

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

Рубрика: 

18
B =
1 1 0 0
1 0 0 1
0 1 1 1
0 0 1 0
⎛⎞
⎜⎟
−−
⎜⎟
⎜⎟
−
⎜⎟
−
⎝⎠
.
Матрица инцидентности, так же, как и мат-
рица смежности, полностью задает граф.
Матрицы смежности и инцидентности удоб-
ны для задания графов на ЭВМ.
Основные свойства матриц смежности и ин-
цидентности
1. Матрица смежности неориентированного
графа является симметричной. Для ориен-
тированного графа это, вообще говоря, не-
верно.
2. Сумма элементов i – ой строки
или i –го
столбца матрицы смежности неориентиро-
ванного графа равна степени вершины x
i
.
3. Сумма элементов i – ой строки матрицы
смежности ориентированного графа равна
числу дуг, исходящих из x
i
.
4. Сумма элементов i – го столбца матрицы
смежности ориентированного графа равна
числу дуг, входящих в вершину x
i
.
5. Сумма строк матрицы инцидентности ори-
ентированного графа является нулевой
строкой.
159
в) матрице расстояний;
г) матрице связности?
18. Может ли число компонент связности графа
превосходить число его вершин?
19. Верно или неверно утверждение, что в ориен-
тированном графе с контурами минимальный путь
может содержать контуры?
20. Как называется связный граф без циклов?
21. Пусть n – число вершин, а m – число ребер в
связном
графе без циклов. Какие из следующих
соотношений возможны:
а) n = m; б) n < m;
в) n
≤
m;
г) n > m;
д) n
≥ m?
22. Сколько ребер имеет связный граф без циклов
с n вершинами?
23. Чему равно наименьшее и наибольшее число
ребер в связном графе без петель и кратных ребер
с n вершинами?
24. Чему равно наименьшее и наибольшее число
ребер в графе без петель и кратных ребер с n вер-
шинами?
25. Верно или
неверно следующее утверждение:
Минимальное остовное дерево может содержать
циклы? 
                    ⎛ 1 1 0 0⎞                        в) матрице расстояний;
               B=   ⎜ −1 0 0 − 1 ⎟ .
                    ⎜            ⎟                    г) матрице связности?
                    ⎜ 0 −1 1 1 ⎟                   18. Может ли число компонент связности графа
                    ⎜            ⎟
                    ⎝ 0 0 −1 0⎠                    превосходить число его вершин?
                                                   19. Верно или неверно утверждение, что в ориен-
      Матрица инцидентности, так же, как и мат-    тированном графе с контурами минимальный путь
рица смежности, полностью задает граф.             может содержать контуры?
      Матрицы смежности и инцидентности удоб-      20. Как называется связный граф без циклов?
ны для задания графов на ЭВМ.                      21. Пусть n – число вершин, а m – число ребер в
      Основные свойства матриц смежности и ин-     связном графе без циклов. Какие из следующих
цидентности                                        соотношений возможны:
   1. Матрица смежности неориентированного            а) n = m; б) n < m;
       графа является симметричной. Для ориен-        в) n ≤ m;
       тированного графа это, вообще говоря, не-      г) n > m;
       верно.                                         д) n ≥ m?
   2. Сумма элементов i – ой строки или i –го      22. Сколько ребер имеет связный граф без циклов
       столбца матрицы смежности неориентиро-      с n вершинами?
       ванного графа равна степени вершины xi.     23. Чему равно наименьшее и наибольшее число
   3. Сумма элементов i – ой строки матрицы        ребер в связном графе без петель и кратных ребер
       смежности ориентированного графа равна      с n вершинами?
       числу дуг, исходящих из xi.                 24. Чему равно наименьшее и наибольшее число
   4. Сумма элементов i – го столбца матрицы       ребер в графе без петель и кратных ребер с n вер-
       смежности ориентированного графа равна      шинами?
       числу дуг, входящих в вершину xi.           25. Верно или неверно следующее утверждение:
   5. Сумма строк матрицы инцидентности ори-       Минимальное остовное дерево может содержать
       ентированного графа является нулевой        циклы?
       строкой.



                           18                                               159

Страницы