Графы

В математике и в реальной жизни часто встречаются структуры, состоящие из связанных друг с другом объектов. Такие структуры удобно представлять геометрическими образами; при этом объекты изображаются точками на плоскости, а связи между ними – соединяющими их линиями. При этом значение имеют не геометрические координаты точек, а само их существование и факт наличия или отсутствия связи между ними. Подобные структуры получили название графов.

Рис. 1. Геометрическая интерпретация графа

С математической точки зрения графом называют пару (A, B), где A – множество элементов a_i, B – множество связей b_j между ними. Элементы a_i называются вершинами графа, а связи b_j – рёбрами. Две вершины, соединяемые одним ребром, называютсясмежными вершинами. Аналогично, два ребра, имеющие общую вершину, называются смежными рёбрами.

Граф, состоящий только из неориентированных рёбер, называется неориентированным. Аналогично, граф, все рёбра которого ориентированы, называется ориентированным графом (орграфом). Примером ориентированного графа может считаться кровеносная система человека: кровь в ней течёт только в одном направлении. Неориентированным графом является карта города, на всех улицах которого разрешено двустороннее движение.

Рис. 2. Ориентированные и неориентированные графы

Графы широко распространены в самых разных областях человеческой жизни. В качестве примеров можно привести:

• карту страны;
• схему метро;
• электрическую схему;
• описание бизнес-процесса.

Каждому ребру графа может быть сопоставлено какое-либо неотрицательное число (вес). Подобный граф называетсявзвешенным. Цепь – это последовательность различных ребёр в графе с учётом их ориентированности, в которой соседние звенья образуют общую вершину. Длиной цепи называется количество входящих в цепь рёбер; во взвешенном графе длина цепи определяется как сумма весов рёбер этой цепи. Расстоянием между вершинами называется длина кратчайшей цепи, соединяющей эти две вершины (в ориентированном графе – длина кратчайшего пути).

Взвешенные графы используются для решения самых разных задач из человеческой жизни: начиная от управления процессами и заканчивая вычислением кратчайшего пути между городами.

Графы часто представляются в табличном виде – в виде матрицы смежности. Каждый столбец или строка этой матрицы обозначает вершину графа. На пересечении i-го столбца и j-й строки ставится 1, если существует ребро, соединяющее вершины a_i и a_j, и 0 в противном случае. В ориентированных графахa_ij = 1, если ребро, соединяющее эти вершины, входит в вершину a_i (в противном случае значение ячейки остается равным нулю).