Тема 9. Графы и матрицы

Задание 1. Постройте матрицы смежности, принадлежности, расстояний и достижимости для графов, изображенный на рисунках. Нумерацию вершин и ребер введите самостоятельно. Что произойдет с матрицей, если будут выбраны отличные друг от друга нумерации? Что можно сказать о графах, полученных таким образом?

Задание 2. Постройте матрицы смежности, принадлежности, расстояний и достижимости для графов .

Задание 3. Постройте матрицы смежности, принадлежности, расстояний и достижимости для графов . Что можно сказать о свойствах матрицы смежности полного двудольного (трехдольного) графа?

Задание 4. Постройте матрицы смежности, принадлежности, расстояний и достижимости для графов .

Задание 5. Постройте матрицы смежности, принадлежности, расстояний и достижимости для какого-либо дерева на 3 (4, 5) вершинах. Найдите число нулей и единиц в матрице смежности дерева на n вершинах.

Задание 6. Постройте графы по их матрице смежности:

; ;

; .

Задание 7. Сколько существует графов на n вершинах? Сколько из них содержит ровно m ребер?

Задание 8. Пусть - граф с множеством вершин , в котором вершины i и j смежны тогда и только тогда, когда числа i и j взаимно - просты. Изобразите , найдите соответствующие им матрицы. Покажите, что если m<n, то граф - подграф графа .

Задание 9. Опишите матрицы смежности полных графов, пустых графов, двудольных графов, простых циклов. Что можно сказать о матрицах смежности графа и его дополнения?

Задание 10. Характеристическими числами графа называются характеристические числа его матрицы смежности. Найдите характеристические числа графов . Докажите, что сумма характеристических чисел графа G равно 0.

Задание 11. Пусть А – матрица смежности связного графа на вершинах . Покажите, что число маршрутов (возможны повторения ребер) длины k из в равно (i, j)-му элементу матрицы . Покажите, что след матрицы равен 6 с, где с – число треугольников в первоначальном графе.

Задание 12. Исследуйте свойства функции d (x,y), используемой при построении матрицы расстояний графа G. Покажите, что эта метрика – метрика кратчайшего пути графа G. Докажите, что данная метрика целочисленная. Докажите, что если , то найдется вершина z: d (x, y) = d (x, z) +d (z, y). Приведите примеры других известных вам метрик (евклидова метрика, - метрика, - метрика и т.д.). Проверьте, что для любого множества Х функция: , определенная по закону d (x, y) = 1 для и d (x, x) = 0, является метрикой на Х.

Задание 13. Диаметр графа – максимальное возможное расстояние между его вершинами. Центр графа – точка, максимальное расстояние от которой до других вершин минимально. Это расстояние называется радиусом графа, . Найдите диаметр и радиус графов , графа Петерсона, графов тел Платона. Приведите примеры графа, имеющего более одного центра. Докажите, что и , где - максимальная из степеней вершин графа. Докажите, что каждое дерево один или два центра.