Олимпиады по программированию

olympiads.ru

МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике

Дистанционные семинары
по подготовке к олимпиадам по информатике

Занятие 4. Графы - введение.

Граф - это абстрактный математический объект. Он состоит из вершин и ребер. Каждое ребро соединяет пару вершин. Если одну и ту же пару вершин соединяют несколько ребер, то эти ребра называются кратными. Ребро, соединяющее вершину с ней самой, называется петлей. По ребрам графа можно ходить, перемещаясь из одной вершины в другую. В зависимости от того, можно ли по ребру ходить в обе стороны, или только в одну, различают неориентированные и ориентированные графы соответсвенно. Ориентированные ребра называются дугами. Если у всех ребер графа есть вес (т.е. некоторое число, однозначно соответсвующее данному ребру), то граф называется взвешенным. Вершины, соединенные ребром, называются соседними. Для неориентированного графа степень вершины - число входящих в нее ребер. Для ориентриованного графа различают степень по входящим и степень по исходящим ребрам. Граф называется полным, если между любой парой различных вершин есть ребро.

Граф - объект абстрактный, и интерпретировать его мы можем по-разному, в зависимости от конкретой задачи. Рассмотрим пример. Пусть вершины графа - города, а ребра - дороги, их соединяющие. Если дороги имеют одностороннее движение, то граф ориентированный, иначе неориентированный. Если проезд по дорогам платный, то граф взвешенный.

На бумаге граф удобно представлять, изображая вершины точками, а ребра - линиями, соединяющими пары точек. Если граф ориентированный, на линиях нужно рисовать стрелочку, задающую направление; если граф взвешенный, то на каждом ребре необходимо еще надписывать число - вес ребра.

Есть несколько способов представления графа в памяти компьютера. На этом занятии мы рассмотрим некоторые из них.

Способ первый: массив ребер.
Пусть в графе M ребер. Заведем массив размером Mx2, в котором будем хранить ребра парами вершин, которые они соединяют. Это наиболее понятный, но достаточно неудобный способ хранения графа. Однако у него есть один большой плюс - при таком способе представления легко вводить дополнительные характеристики ребер. Например, чтобы сохранить веса ребер, достаточно сделать массив размером Mx3 и в дополнительную ячейку для каждого ребра записать его вес.

Способ второй: матрица смежности.
Пусть в графе N вершин. Заведем матрицу размером NxN, где в элемент a_i,j запишем количество ребер из вершины i в вершину j. Если граф взвешенный, то вместо количества запишем вес соответствующего ребра. В случае отсутствия ребра запишем бесконечность. Таким образом, проявился один из недостатков такого представления: в матрице смежности невозможно хранить взвешенный граф с кратными ребрами. Однако, в некоторых случаях, это можно обойти. Очень часто из всего множества ребер между данной парой вершин нам достаточно хранить только одно - самое легкое.
Рассмотрим несколько свойств матрицы смежности.

• В матрице смежности графа без петель на главной диагонали стоят 0.
• Матрица смежности неориентированного графа симметрична относительно главной диагонали.

Теперь рассмотрим несколько простых задач, чтобы немного привыкнуть к новой терминологии и на практике попробовать способы представления графов в памяти компьютера.

Примечание. Формальное определение графа.
Граф - множество V вершин и набор набор E неупорядоченных и упорядоченных пар вершин; обозначается граф через G(V,E).
[Математическая энциклопедия, том 1, Москва, "Советская энциклопедия", 1977]