Графы

Представление графов

Граф - является множеством вершин (узлов) и рёбер, которые соединяет пару различных вершин. Будем описывать граф массивом узлов nodes, каждый из которых содержит массив go с номерами узлов в которые можно перейти непосредственно из данного. В отличие от списков и деревьев, графы имеют сложную топологию, поэтому для их визуализации необходимо задать координаты x и y каждого узла. Узел также может иметь имя nm и хранить другие данные. Граф реализован классом Graph. Его можно задать по другому графу или массиву узлов, как в этом примере:

var g = new Graph( [
                      { nm:0,  go:[1],   x:50,  y:0 },
                      { nm:1,  go:[2],   x:0,   y:87},
                      { nm:2,  go:[0,1], x:100, y:87},
                   ]
                 );
document.write(g.getSVG());   // рисуем как svg-картинку
0 1 2 g
Если связи между двумя узлами направлены в обе стороны (как в случае с узлами 1 и 2), то при рисовании графа на таком ребре стрелки не ставятся. Ребро, соединяющее узел 2 и 0 - направленное (из узла 2 в 0 перейти можно, а вот обратно - нет).

Ещё один способ, создание графов в классе Graph - это задание числа его узлов, а затем постепенное добавление рёбер:

g = new Graph();                                  // пустой граф
g.create(6, 50);                                  // 6 несвязных узлов по окружности радиуса 50
document.write(g.getSVG(), "   ");
for(var i=0; i < g.numNodes(); i++)
   g.bind(i, i+1===g.numNodes()?0: i+1);          // задём двухсторонние связи между соседними узлам
document.write(g.getSVG(), "   ");
g.insertNode(1,4);                                // вставляем узел с рёбрами между узлами 1 и 4
document.write(g.getSVG(), "   ");
g.addRib(6,5);                                    // добавляем направленное ребро от 6 к 5
g.addRib(6,2);                                    // аналогично от 6 к 2
document.write(g.getSVG());                       // результирующий граф (последняя svg-картинка)
0 1 2 3 4 5     0 1 2 3 4 5     0 1 2 3 4 5 6     0 1 2 3 4 5 6

При создании графов можно также пользоваться редактором.

Большинству алгоритмов достаточно знать только узлы в которые можно перейти из данного. Однако, в ряде случаев необходима обратная информация - массив узлов из которых можно попасть в данный. Такие массивы on (в каждом узле) строятся по массивам go при помощи функции g.createOn(). В общем случае, узел может иметь следующие свойства:

nm  : 0,                      // имя узла
go  : [1,2],                  // узлы в которые можно перейти
 
x:200, y:100,                 // координаты узла
 
on  : [3],                    // узлы из которых можно попасть в данный
w   : [3,3],                  // толщина рёбер (визуализация)
d   : [7,3],                  // длина рёбер ("стоимость" перемещения по ребру)
chk : 1,                      // пометка узла (служит, например, для его покраски)
cols: ["#000", "#F00"]        // массив rgb цветов исходящих рёбер (визуализация)
col : "#00F"                  // rgb цвет заливки узла (визуализация)
По умолчанию, цвет узла равен Graph.svg.cFill="#FFC". Если задан массив цветов Graph.svg.colors и у узла есть пометка chk, то он красится цветом под номером chk из этого массива. Другой способ покраски узлов и рёбер - это прямое задание свойств col и cols каждого узла.

Немного определений

Однонаправленное ребро графа иногда называют дугой, а двунаправленное - собственно ребром. Граф, состоящий из V узлов ( == вершин), содержит не более V·(V-1) рёбер (считая двунаправленное ребро, как два ребра). Два графа называют изоморфными, если с точностью до имён узлов их топология (число узлов и способы их соединений) совпадает.

Путь на графе - это множество вершин в которые можно попасть последовательно одна за одной. Если все вершины и рёбра составляющие путь различны, то он называется простым путём. Ниже вершины 0,1,2 составляют путь. Цикл - это простой замкнутый путь (начинающийся и кончающийся на одной и той же вершине. На втором рисунке это 1,3,4:

0 1 2 3 4       90 86 90 90 80 0 1 2 3 4

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

0 1 2 3 4 5 6       0 1 2 3 4 5 6 7 8 9 10 11 12

Гамильтонов путь -это простой путь, проходящий через каждый узел графа один раз.
Эйлеров путь - проходит через каждое ребро в точности один раз.

Некоторые вычислительные задачи, связанные с графами:

Генерация больших графов

Большие графы задавать "ручным" способом непросто, поэтому для тестирования алгоритмов удобны функции генерации графов произвольного размера. Например, решётка шириной w узлов и высотой h узлов с длиной ребра len (в пикселях) создаётся функцией createGrid(w,h,len, oneway). Четвёртый аргумент в функции (если он есть и равен true) делает рёбра графа направленными. Ниже приведены три варианта использования этой функции. В третьем случае, при рисовании графа, отключен вывод имён узлов (Graph.svg.showNm = false). Во втором случае функция g.swapRibs(prob, ribs) с вероятностью prob переворачивает в узле от одного до ribs рёбер:
g.createGrid(4,3, 50, true);
g.createGrid(4,3, 50, true);
g.swapRibs(1, 1);
g.createGrid(16,12, 10);
     50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 0 1 2 3 4 5 6 7 8 9 10 11      0 1 2 3 4 5 6 7 8 9 10 11     

Ещё один, более "дырявый" вариант - это граф в виде треугольника Серпинского createTriangle(num, len) с числом рекурсий num и стартовым ребром длиной len (в px):

0 1 2 3 4 5     

Приведём код этой функции:

Graph.prototype.createTriangle = function(num, len)
{
   this.nodes = [                                 // начальный равносторонний треугольник
      { nm:0, go:[1,2], x:len*0.5, y:0 },
      { nm:1, go:[0,2], x:0,       y:len*0.866 },
      { nm:2, go:[0,1], x:len,     y:len*0.866 }
   ];
   this.ribs  = [];                               // очищаем массив рёбр
   this.createTri(num, 0,1,2);                    // вызываем рекурсивную функцию
}
Функция createTri(num, k0, k1, k2) внутри треугольника, образованного вершинами k0, k1, k2 рекурсивно num раз повторяет треугольник Серпинского:
Graph.prototype.createTri = function(num, k0, k1, k2)
{
   if(num <= 0)                                   // рекурсия закончилась
      return;
 
   var k3 = this.insertNode(k0,k1);   this.nodes[k3].nm = k3;
   var k4 = this.insertNode(k1,k2);   this.nodes[k4].nm = k4;
   var k5 = this.insertNode(k0,k2);   this.nodes[k5].nm = k5;
 
   this.bind(k3,k5);                              // связываем двухсторонним ребром
   this.bind(k3,k4);
   this.bind(k4,k5);
   this.createTri(num-1, k0, k3, k5);             // для каждого из 3-х треугольников
   this.createTri(num-1, k3, k1, k4);
   this.createTri(num-1, k5, k4, k2);
}

Модифицированный треугольник Серпинского можно получить функцией createTriangle2:

99 99 99 99 100 100 100 99 99 99 99 99 0 1 2 3 4 5 6 7 8     

В уже построенном графе, функция delRibs(prob, ribs) с вероятностью prob в каждом узле ликвидирует от одного до ribs рёбер (с равномерным распределением). Ниже приведен пример скрипта g.createGrid(50, 20, 10); g.delRibs(0.7, 1):

Класс Graph

Создание и изменение графов

Для работы с графами, необходимо подключить два модуля: graph.js и draw.js (графическое отображение).

Информация о графе

Алгоритмы на графе

Отображение графа

Деревья <