|
Дистанционные семинары
по подготовке к олимпиадам по информатике
Граф - это абстрактный математический объект. Он состоит из
вершин и ребер. Каждое ребро соединяет пару вершин.
Если одну и ту же пару вершин соединяют несколько ребер, то эти
ребра называются кратными. Ребро, соединяющее вершину с
ней самой, называется петлей.
По ребрам графа можно ходить, перемещаясь из одной вершины в другую.
В зависимости от того, можно ли по ребру ходить в обе стороны, или
только в одну, различают неориентированные и
ориентированные графы соответсвенно. Ориентированные ребра
называются дугами. Если у всех ребер графа есть вес
(т.е. некоторое число, однозначно соответсвующее данному ребру), то граф
называется взвешенным. Вершины, соединенные ребром, называются
соседними. Для неориентированного графа степень
вершины - число входящих в нее ребер. Для ориентриованного графа
различают степень по входящим и степень по исходящим ребрам. Граф
называется полным, если
между любой парой различных вершин есть ребро.
Граф - объект абстрактный, и интерпретировать его мы можем
по-разному, в зависимости от конкретой задачи. Рассмотрим пример.
Пусть вершины графа - города, а ребра - дороги, их соединяющие.
Если дороги имеют одностороннее движение, то граф ориентированный,
иначе неориентированный. Если проезд по дорогам платный, то граф
взвешенный.
На бумаге граф удобно представлять, изображая вершины точками,
а ребра - линиями, соединяющими пары точек. Если граф
ориентированный, на линиях нужно рисовать стрелочку,
задающую направление; если граф взвешенный, то на каждом ребре
необходимо еще надписывать число - вес ребра.
Есть несколько способов представления графа в памяти компьютера.
На этом занятии мы рассмотрим некоторые из них.
Способ первый: массив ребер.
Пусть в графе M ребер. Заведем массив размером Mx2, в котором будем хранить
ребра парами вершин, которые они соединяют. Это наиболее понятный,
но достаточно неудобный способ хранения графа. Однако у него есть
один большой плюс - при таком способе представления легко вводить
дополнительные характеристики ребер. Например, чтобы сохранить
веса ребер, достаточно сделать массив размером Mx3 и в дополнительную
ячейку для каждого ребра записать его вес.
Способ второй: матрица смежности.
Пусть в графе N вершин. Заведем матрицу размером NxN, где в элемент
ai,j запишем количество ребер из вершины i в
вершину j. Если граф взвешенный, то вместо количества запишем
вес соответствующего ребра. В случае отсутствия ребра запишем
бесконечность. Таким образом, проявился один из недостатков такого
представления: в матрице смежности невозможно хранить взвешенный
граф с кратными ребрами. Однако, в некоторых случаях, это можно
обойти. Очень часто из всего множества ребер между данной парой
вершин нам достаточно хранить только одно - самое легкое.
Рассмотрим несколько свойств матрицы смежности.
- В матрице смежности графа без петель на главной диагонали стоят 0.
- Матрица смежности неориентированного графа симметрична относительно главной диагонали.
Теперь рассмотрим несколько простых задач, чтобы
немного привыкнуть к новой терминологии и на практике попробовать
способы представления графов в памяти компьютера.
Задача 04-1. Города и дороги
|
Задача 04-2. Светофорчики
|
Задача 04-3. Цветной дождь
|
Задача 04-4. Издевательство
|
Примечание. Формальное определение графа.
Граф - множество V вершин и набор набор E
неупорядоченных и упорядоченных пар вершин; обозначается
граф через G(V,E).
[Математическая энциклопедия, том 1, Москва, "Советская энциклопедия", 1977]
|