PLANAR - проверка планарности графа

Иван Тищенко, Запорожский национальный университет

Программа 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>


Для получения PLANAR загрузите и разархивируйте один из следующих файлов: planar.zip или planar.tar.gz.

ПЕРЕЧЕНЬ ССЫЛОК

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 с.

Март 2007