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

UptoLike

ВУЗ: 

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

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

Рубрика: 

20
Рис. 7.
Действительно, на рис. 7 отображение
a
→ e, b → f, c → g, d → h,
являющееся изоморфизмом, легко представить как
модификацию первого графа, передвигающую
вершину d в центр рисунка.
Изоморфные графы отличаются только ну-
мерацией вершин. Матрицы смежности двух изо-
морфных графов могут быть получены одна из
другой перестановкой строк и столбцов. Чтобы
узнать, являются ли два графа изоморфными,
нужно произвести все возможные перестановки
строк и столбцов матрицы смежности одного из
графов. Если после какой-нибудь перестановки
получится матрица смежности
второго графа, то
эти графы изоморфны. Чтобы убедиться, что гра-
фы неизоморфны, надо выполнить все n! возмож-
ных перестановок строк и столбцов.
157
Контрольные вопросы
1. Какое из двух утверждений верно:
а) ориентированный граф является частным слу-
чаем неориентированного графа;
б) неориентированный граф является частным
случаем ориентированного графа?
2. Перечислите все возможные способы задания
графов.
3. Что характеризует сумма элементов столбца
матрицы смежности неориентированного графа?
4. Что характеризует сумма элементов строки мат-
рицы смежности неориентированного графа?
5. Что
характеризует сумма элементов столбца
матрицы смежности ориентированного графа?
6. Что характеризует сумма элементов строки мат-
рицы смежности ориентированного графа
7. Всегда ли матрица смежности симметрична от-
носительно главной диагонали?
8. Как по матрице смежности определить число
ребер неориентированного графа?
9. Как по матрице инцидентности, не рисуя граф,
определить его матрицу смежности?
10. Может
ли матрица
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
0 1 0
0 0 1
1 1 0
быть матрицей
смежности неориентированного графа? 
                                                              Контрольные вопросы
                                                 1. Какое из двух утверждений верно:
                                                    а) ориентированный граф является частным слу-
                                                       чаем неориентированного графа;
                                                    б) неориентированный граф является частным
                                                       случаем ориентированного графа?
                    Рис. 7.                      2. Перечислите все возможные способы задания
Действительно, на рис. 7 отображение             графов.
                                                 3. Что характеризует сумма элементов столбца
           a → e, b → f, c → g, d → h,
                                                 матрицы смежности неориентированного графа?
являющееся изоморфизмом, легко представить как
                                                 4. Что характеризует сумма элементов строки мат-
модификацию первого графа, передвигающую
                                                 рицы смежности неориентированного графа?
вершину d в центр рисунка.
                                                 5. Что характеризует сумма элементов столбца
      Изоморфные графы отличаются только ну-     матрицы смежности ориентированного графа?
мерацией вершин. Матрицы смежности двух изо-     6. Что характеризует сумма элементов строки мат-
морфных графов могут быть получены одна из       рицы смежности ориентированного графа
другой перестановкой строк и столбцов. Чтобы     7. Всегда ли матрица смежности симметрична от-
узнать, являются ли два графа изоморфными,       носительно главной диагонали?
нужно произвести все возможные перестановки      8. Как по матрице смежности определить число
строк и столбцов матрицы смежности одного из     ребер неориентированного графа?
графов. Если после какой-нибудь перестановки     9. Как по матрице инцидентности, не рисуя граф,
получится матрица смежности второго графа, то    определить его матрицу смежности?
эти графы изоморфны. Чтобы убедиться, что гра-                           ⎛0 1 1 ⎞
                                                                         ⎜      ⎟
фы неизоморфны, надо выполнить все n! возмож-    10. Может ли матрица    ⎜1 0 0 ⎟   быть матрицей
                                                                         ⎜ 0 1 0⎟
ных перестановок строк и столбцов.                                       ⎝      ⎠
                                                 смежности неориентированного графа?



                         20                                               157

Страницы