Глава 2.Ненаправленные графы, часть 1. Простые графы (графы) Способы задания графа Основные способы задания графов графический
![]()
|
![]() ![]() ![]() ![]() ![]() ![]() 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. |