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

UptoLike

ВУЗ: 

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

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

Рубрика: 

158
11. Какие из следующих утверждений являются
правильными:
а) если матрица смежности несимметричная, то
граф ориентированный;
б) если граф неориентированный, то матрица
смежности симметричная;
в) если диагональные элементы матрицы смеж-
ности – нули, то граф неориентированный?
12. Может ли вершина, входящая в цикл графа,
иметь степень, меньшую двух?
13. Как называется путь, у которого
начало первой
дуги совпадает с концом последней?
14. Как называется маршрут, у которого первая
вершина совпадает с последней?
15. Можно ли утверждать, что сильно связный
граф всегда содержит контур?
16. Какие из следующих матриц полностью задают
граф:
а) матрица инцидентности;
б) матрица односторонней связности;
в) матрица связности;
г) матрица сильной связности;
д
) матрица смежности?
17. По какой матрице можно без дополнительных
вычислений определить число компонент связно-
сти неориентированного графа:
а) матрице смежности;
б) матрице инциденций;
19
Возможны следующие различные способы
задания графа:
а) посредством графического изображения;
б) указанием множества вершин и множест-
ва ребер (дуг);
в) матрицей смежности;
г) матрицей инцидентности.
3B1.3. Изоморфизм графов
Определение 1.19. Графы G
1
=.(X
1
,.A
1
) и G
2
=.(X
2
,.A
2
)
изоморфны, если существует взаимно однозначное
соответствие между множествами вершин X
1
и X
2
,
такое, что любые две вершины одного графа со-
единены тогда и только тогда, когда соответст-
вующие вершины соединены в другом графе.
Пример 1.9.
Графы, изображенные на рис. 6 являются
изоморфными.
Рис. 6.
Пример 1.10.
Покажем, что следующие два графа изоморфны. 
11. Какие из следующих утверждений являются              Возможны следующие различные способы
правильными:                                        задания графа:
  а) если матрица смежности несимметричная, то           а) посредством графического изображения;
     граф ориентированный;                               б) указанием множества вершин и множест-
  б) если граф неориентированный, то матрица                ва ребер (дуг);
     смежности симметричная;                             в) матрицей смежности;
  в) если диагональные элементы матрицы смеж-            г) матрицей инцидентности.
     ности – нули, то граф неориентированный?
12. Может ли вершина, входящая в цикл графа,                     1.3. Изоморфизм графов
                                                                 3B




иметь степень, меньшую двух?                        Определение 1.19. Графы G1 =.(X1,.A1) и G2 =.(X2,.A2)
13. Как называется путь, у которого начало первой   изоморфны, если существует взаимно однозначное
дуги совпадает с концом последней?                  соответствие между множествами вершин X1 и X2,
14. Как называется маршрут, у которого первая       такое, что любые две вершины одного графа со-
вершина совпадает с последней?                      единены тогда и только тогда, когда соответст-
15. Можно ли утверждать, что сильно связный         вующие вершины соединены в другом графе.
граф всегда содержит контур?
                                                                     Пример 1.9.
16. Какие из следующих матриц полностью задают
                                                         Графы, изображенные на рис. 6 являются
граф:
                                                    изоморфными.
  а) матрица инцидентности;
  б) матрица односторонней связности;
  в) матрица связности;
  г) матрица сильной связности;
  д) матрица смежности?
17. По какой матрице можно без дополнительных
вычислений определить число компонент связно-                              Рис. 6.
сти неориентированного графа:                                        Пример 1.10.
  а) матрице смежности;                             Покажем, что следующие два графа изоморфны.
  б) матрице инциденций;

                         158                                                    19

Страницы