Программа PLANAR разработана с помощью системы компьютерной
алгебры GAP [1] и пакета GRAPE [2] и
предназначена для проверки планарности связных графов.
Если нужна предварительная проверка того, что граф является связным,
то ее можно выполнить с помощью функции
IsConnectedGraph из пакета GRAPE [2].
Кроме того, граф должен быть неориентированным и не должен иметь
кратных ребер и петель (заметьте, что эти свойства графа не отражаются
на его планарности).
Для корректной работы программы запустите GAP из каталога, в
котором лежит PLANAR. Для начала работы с программой задайте
команду Read(“init.g”);
gap> Read("init.g");
#I Package `GRAPE': non-Unix architecture or binaries not compiled
#I Package `GRAPE': functions depending on nauty will not work
Loading GRAPE 4.3 (GRaph Algorithms using PErmutation groups),
by L.H.Soicher@qmul.ac.uk.
PLANAR
gap>
Основными функциями данной программы являются IsPlanar(G) и IsPlanarByMcLane(G). Функция IsPlanarByMcLane (G) проверяет связный граф на планарность с помощью критерия Мак-Лейна. При этом IsPlanarByMcLane(G) перебирает всевозможные базисы подпространства циклов. Данный перебор при большом количестве рёбер может занять много времени. В связи с этим была разработана функция IsPlanar(G), которая при выборе базисов использует структурные числа [3]. Хотя целью разработки PLANAR являлись описанные выше функции, в процессе их написания был разработан ряд вспомогательных функций, которые могут представлять независимый интерес. Ниже будут изложены описания данных функций.
Функция GraphByMat(m) задаёт граф по его матрице смежности m.
gap> m:=[[0,1,0,1],[1,0,1,0],[0,1,0,1],[1,0,1,0]];
[ [ 0, 1, 0, 1 ], [ 1, 0, 1, 0 ], [ 0, 1, 0, 1 ], [ 1, 0, 1, 0 ] ]
gap> H:=GraphByMat(m);
rec( isGraph := true, order := 4, group := Group(()),
schreierVector := [ -1, -2, -3, -4 ],
adjacencies := [ [ 2, 4 ], [ 1, 3 ], [ 2, 4 ], [ 1, 3 ] ],
representatives := [ 1, 2, 3, 4 ], names := [ 1, 2, 3, 4 ] )
Проверим граф H на планарность.
gap> IsPlanar(H);
true
gap> IsPlanarByMcLane(H);
Generating 1 combinations ... OK
true
Функция GraphByEdges(t) задаёт граф по списку t его рёбер.
gap>
t:=[[1,2],[2,4],[4,1],[2,5],[4,5],[5,6],[6,1],[6,2],[6,3]];
[ [ 1, 2 ], [ 2, 4 ], [ 4, 1 ], [ 2, 5 ], [ 4, 5 ], [ 5, 6 ], [ 6, 1 ],
[ 6, 2 ], [ 6, 3 ] ]
gap> D:=GraphByEdges(t);
rec( isGraph := true, order := 6, group := Group(()),
schreierVector := [ -1, -2, -3, -4, -5, -6 ],
adjacencies := [ [ 2, 4, 6 ], [ 1, 4, 5, 6 ], [ 6 ], [ 1, 2, 5
],
[ 2, 4, 6 ], [ 1, 2, 3, 5 ] ], representatives := [ 1, 2,
3, 4, 5, 6 ],
names := [ 1, 2, 3, 4, 5, 6 ] )
Функция CompleteGraphByOrder(n) задаёт полный граф порядка n.
gap> C:=CompleteGraphByOrder(7);
rec( isGraph := true, order := 7, group := Group(()),
schreierVector := [ -1, -2, -3, -4, -5, -6, -7 ],
adjacencies := [ [ 2, 3, 4, 5, 6, 7 ], [ 1, 3, 4, 5, 6, 7 ],
[ 1, 2, 4, 5, 6, 7 ], [ 1, 2, 3, 5, 6, 7 ], [ 1, 2, 3, 4,
6, 7 ],
[ 1, 2, 3, 4, 5, 7 ], [ 1, 2, 3, 4, 5, 6 ] ],
representatives := [ 1, 2, 3, 4, 5, 6, 7 ],
names := [ 1, 2, 3, 4, 5, 6, 7 ] )
Проверим граф С на планарность.
gap> IsPlanar(C);
false
gap> IsPlanarByMcLane(C);
false
Функция SimpleCycles(G,a,b) возвращает все простые циклы, проходящие по ребру [a,b] графа G.
gap> s:=SimpleCycles(G,1,3);
[ [ 1, 2, 3 ], [ 1, 3, 2, 4 ], [ 1, 3, 5, 4 ], [ 1, 3, 2, 6 ], [ 1, 3,
7, 6 ] ]
Функция SimpleCyclesForVertex(G,a) возвращает все простые циклы, проходящие через вершину a графа G.
gap> s:=SimpleCyclesForVertex(G,7);
[ [ 1, 3, 7, 6 ], [ 2, 3, 7 ], [ 2, 3, 7, 6 ], [ 2, 6, 7 ] ]
Функция TauCycles(G) возвращает единичные циклы графа и добавляет их в запись графа.
gap> tau:=TauCycles(G);
[ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 2, 6 ], [ 1, 3, 5, 4 ], [ 1, 3, 7, 6
],
[ 2, 3, 5 ], [ 2, 3, 7 ], [ 2, 4, 5 ], [ 2, 6, 7 ] ]
Функция MackLane(m) вычисляет функционал Мак-Лейна от матрицы m.
gap> j:=MackLane(m);
40
Функция TreeOfGraph(G) возвращает список ребер дерева графа G.
gap> T:=TreeOfGraph(G);
[ [ 1, 2 ], [ 2, 3 ], [ 2, 4 ], [ 2, 5 ], [ 2, 6 ], [ 2, 7 ] ]
Также в программе PLANAR были реализованы структурные числа и операции над ними. Функция StructuralNumber(m) задает структурное число, где m – матрица, которая не имеет одинаковых столбцов (при этом столбцы нужно рассматривать, как неупорядоченные множества), а столбцы, в свою очередь, не имеют одинаковых элементов [3]. Были инсталлированы следующие методы:
– сравнение структурных чисел;
– сложение структурных чисел;
– умножение структурных чисел.
gap> sn1:=StructuralNumber([[1,2,3],[3,9,1],[5,7,9]]);
[ [ 1, 1, 2 ],
[ 3, 3, 7 ],
[ 5, 9, 9 ] ]
gap> sn2:=StructuralNumber([[8,4,3],[3,9,1],[5,7,9]]);
[ [ 1, 3, 4 ],
[ 3, 5, 7 ],
[ 9, 8, 9 ] ]
gap> sn1=sn2;
false
gap> sn1+sn2;
[ [ 1, 2, 3, 4 ],
[ 3, 7, 5, 7 ],
[ 5, 9, 8, 9 ] ]
gap> sn1*sn2;
[ [ 1, 2 ],
[ 3, 3 ],
[ 4, 5 ],
[ 5, 7 ],
[ 7, 8 ],
[ 9, 9 ] ]
gap> sn1
true
gap> sn1>sn2;
false
gap>
1. The GAP Group, GAP - Groups, Algorithms, and Programming, Version
4.4.9; 2006 (http://www.gap-system.org).
2. L.H. Soicher, The GRAPE package for GAP, Version 4.3, 2006,
http://www.maths.qmul.ac.uk/~leonard/grape/.
3. Курапов С.В., Савин В.В. Векторная алгебра и рисунок графа. –
Запорожье: ЗГУ, 2003. –200 с.