1.2 Способы задания графов

Первое и на наш взгляд самое простое задание графа - это представление его с помощью картинки в соответствии с геометрическим определением графа. При этом, в соответствии с договоренностью выше, вершинам конкретного представления графа будут приписаны номера.

Так на рис.2 даны два представления одного и того же графа.

Рисунок 2

Другое задание графа - списком. Можно считать, что в соответствии с теоретико-множественным определением графа все элементы множества R⊆V×V, входящего в определение, т.е. упорядоченные пары, упорядочены сначала по первым элементам пар, а затем по вторым, в соответствии с нумерацией вершин (нумерацией элементов множества V). Тогда два представления графа с рис.2 будут заданы двумя списками (рис. 3):

Рисунок 3

В первом столбце - первые элементы пар, затем по строкам, списком через запятую, идут вторые элементы.

Третье задание графа - матрицами. Ниже выписаны две матрицы - A и B, задающие два представления графа с рис. 2:

Рисунок 4

Большинство задач информатики удобно решать при использовании матричного задания графов. Квадратная таблица R = ||r_i,j||n_x(n) называется матрицей смежности, если ее элементы образуются по правилу:

r_i,j =

Представления графа в соответствии с различными определениями будем называть различными видами представлений. Между различными видами представлений графа существует взаимнооднозначное соответствие. Действительно, поскольку речь идет о представлении графа, то множество вершин можно считать пронумерованным. Тогда дуге (ребро будем рассматривать как пару противоположно направленных дуг), идущей из вершины i в вершину j будет соответствовать упорядоченная пара (i, j) или, что то же самое, в списке вершины i будет присутствовать вершина j, а в матрице A = (a_ij), представляющей граф, элементa_ij = 1. Отсутствию дуги, идущей из вершины i в вершину j, будет соответствовать отсутствие вершины j в списке вершины i, а a_ij = 0.

В силу указанного выше взаимнооднозначного соответствия между различными видами представлений мы и можем воспользоваться различными определениями одного и того же понятия - граф. При этом при изучении различных свойств графа мы стараемся каждый раз пользоваться тем языком, который наиболее удобен для описания выбранного свойства. Вероятно, не следует выбирать один из языков в качестве единственного языка теории графов. Иногда для описания того или иного свойства, атрибута графа, требуется конкретный язык. Так если мы говорим о плоском (планарном) графе, то нам по необходимости приходится использовать геометрический язык теории графов. Если же мы говорим о "спектре" графа, то мы формулируем это понятие на матричном языке.

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