Анализ графов на ЭВМ. Методические указания. Макарычев П.П - 7 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

7
Контрольные вопросы
1. Чему равна сумма степеней всех вершин графа?
2. Докажите, что матрица смежности и матрица Кирхгофа для графа без
петель связаны соотношением
3. B
i,j
= I
i,j
.
M
2
i,j
(G) - M
i,j
(G)
4. где I — единичная матрица.
5. Покажите на примерах, что расстояние между вершинами l(v
i
,v
j
)
удовлетворяет следующим аксиомам метрики:
a) l(v
i
,v
j
) >= 0;
б) l(v
i
,v
j
) = 0, тогда и только тогда, когда v
i
= v
j
;
в) l(v
i
,v
j
) = l(v
j
,v
i
)
г) l(v
i
,v
k
) + l(v
k
,v
j
) >= l(v
i
,v
j
) (неравенство треугольника).
7. Пусть G — граф, множество вершин которого совпадает с отрезком
натурального ряда {1,2,...5}, а множество ребер определяется следующим
условием: несовпадающие вершины v
i
, и v
j
смежны тогда, когда числа i и j
взаимно просты. Какой вид имеют:
— матрица смежности графа G;
— матрица инциденций G;
— матрица Кирхгофа графа G.
Лабораторная работа №2
УНАРНЫЕ И БИНАРНЫЕ ОПЕРАЦИИ НАД ГРАФАМИ
Цель работы — исследование унарных, бинарных операций над
графами и приобретение практических навыков решения задач с
использованием основ теории графов.
Основные понятия и определения
Все унарные операции над графами можно объединить в две группы.
Первую группу составляют операции, с помощью которых из исходного
                                 Контрольные вопросы
 1. Чему равна сумма степеней всех вершин графа?
 2. Докажите, что матрица смежности и матрица Кирхгофа для графа без
петель связаны соотношением
 3. Bi,j = Ii,j.M2i,j(G) - Mi,j(G)
 4. где I — единичная матрица.
 5. Покажите на примерах, что расстояние между вершинами l(vi,vj)
удовлетворяет следующим аксиомам метрики:
       a) l(vi,vj) >= 0;
       б) l(vi,vj) = 0, тогда и только тогда, когда vi = vj;
       в) l(vi,vj) = l(vj,vi)
       г) l(vi,vk) + l(vk,vj) >= l(vi,vj) (неравенство треугольника).
 7. Пусть G — граф, множество вершин которого совпадает с отрезком
натурального ряда {1,2,...5}, а множество ребер определяется следующим
условием: несовпадающие вершины vi, и vj смежны тогда, когда числа i и j
взаимно просты. Какой вид имеют:
           — матрица смежности графа G;
           — матрица инциденций G;
           — матрица Кирхгофа графа G.

                                Лабораторная работа №2
        УНАРНЫЕ И БИНАРНЫЕ ОПЕРАЦИИ НАД ГРАФАМИ
       Цель работы — исследование унарных, бинарных операций над
графами и приобретение практических навыков решения задач с
использованием основ теории графов.
                           Основные понятия и определения
       Все унарные операции над графами можно объединить в две группы.
Первую группу составляют операции, с помощью которых из исходного




                                          7

Страницы