Уроки 27 - 28
§17. Графы
Содержание урока
Матрица смежности графа
Матрица смежности графа
Для хранения информации об узлах и связях показанного выше графа можно использовать таблицу такого вида (рис. 3.18).
Рис. 3.18
Единица на пересечении строки А и столбца В означает, что между вершинами А и В есть связь. Ноль указывает на то, что связи нет. Такая таблица называется матрицей смежности. Она симметрична относительно главной диагонали (см. закрашенные клетки в таблице).
Исследуйте матрицу смежности и сравните её с графом на рис. 3.17, б. Что означает единица на пересечении столбца С и строки С?
В этом графе есть петля — ребро, которое начинается и заканчивается в одной и той же вершине.
Степенью вершины называют количество рёбер, с которыми связана вершина. При этом петля считается дважды (с вершиной связаны оба конца ребра!).
Подсчитайте по матрице смежности, сколько ребёр в графе. Определите степени всех вершин. Как вы рассуждали?
Строго говоря, граф — это математический объект, а не рисунок. Конечно, его можно нарисовать на плоскости (например, как на рис. 3.17, б), но матрица смежности не даёт никакой информации о том, как именно располагать вершины друг относительно друга. Для таблицы, приведённой выше, возможны, например, такие варианты (рис. 3.19).
Рис. 3.19
Нарисуйте по матрице смежности (рис. 3.20) два разных изображения графа.
Рис. 3.20
Граф имеет 4 вершины, причём каждая вершина связана рёбрами со всеми остальными. Нарисуйте этот граф. Сколько всего рёбер в этом графе?
Граф имеет N вершин, причём каждая вершина связана рёбрами со всеми остальными. Сколько всего рёбер в этом графе?
Граф имеет 4 ребра. Чему равна сумма степеней вершин в этом графе? Зависит ли она от количества вершин?
Граф имеет N рёбер. Чему равна сумма степеней вершин в этом графе?
Попробуйте нарисовать граф с пятью вершинами, где все вершины имеют степень 3. Получилось ли у вас? Почему?
Следующая страница 
Связный граф
Cкачать материалы урока
