Глава 2.Ненаправленные графы, часть 1. Простые графы (графы) Способы задания графа Основные способы задания графов графический
 Скачать 1.28 Mb.
|
     Q t x v d[u]=3  6 Очередь Q: из таблицы индицентности для вершины x: t,w –черные, y – белая. Добавляем в очередь вершину y. Вершина x – черная. Вершина y – серая. d[y]=3 7 Очередь Q: все вершины были помещены в очередь, начинается очищение очереди. Вершина v – черная. 8 Очередь Q: изымается вершина u. Вершина u – черная.  N Рисунок графа Описание действий алгоритма u 3 r 1  2 v s 0 t 2 3 y 2 x 1 w     u r v s t y x w  Ребра, не вошедшие в это дерево, являются ребрами касания: {t,x},{u,y} Дерево обхода в ширину данного примера имеет вид:  9 Очередь Q: изымается вершина y. Вершина y – черная. Очередь пуста, алгоритм стоп.    d[r]=1,d[w]=1,d[v]=2,d[t]=2,d[x]=2,d[u]=3,d[y]=3 1 Арлазаров В.Л. и др. Алгоритм приведения конечных ненаправленных графов к канонической форме. – Журнал вычислительной математики и математической физики,14,1974,737-743. McKay B.D. Computing automorphisms and canonical labelings of graphs. – Combinatorial Mathematics, Springer Lecture Notes in Mathematics,686,1977,223-232. |