О максимальных внешнеплоских графах с двумя симплициальными вершинами | ПДМ. 2015. № 3(29).

О максимальных внешнеплоских графах с двумя симплициальными вершинами

Рассматриваются максимальные внешнеплоские графы (МВП-графы) с двумя симплициальными вершинами. Для графов этого класса получены: рекурсивная характеризация, формула для расчёта количества непомеченных графов и полный инвариант, отличающийся от известного полного инварианта произвольных МВП-графов. Описан полиномиальный алгоритм вычисления полного инварианта.

Maximal outerplane graphs with two simplicial vertices.pdf Введение Одним из объектов изучения теории графов являются максимальные внешне-плоские графы (МВП-графы), которые впервые были исследованы Г. Чартрэндом и Ф. Харари в 1967г. [1]. Внешнеплоским графом называется плоский граф, все вершины которого принадлежат внешней грани. Максимальным внешнеплоским графом называется такой внешнеплоский граф, который при добавлении хотя бы одного ребра перестаёт быть внешнеплоским [2]. Графы этого вида являются триангуляциями выпуклого многоугольника и относятся к классу хордальных графов [3]. Работы по исследованию МВП-графов достаточно хорошо представлены в математической литературе (см., например, [1-11]). Основные свойства МВП-графов описаны в [2]. Характеризация в терминах запрещёных подграфов дана в [1], а рекурсивная характеризация - в [4, 5]. Некоторые «конструктивные» свойства МВП-графов рассмотрены в [5 - 7], а условия возможности укладки МВП-графов на двух параллельных линиях - в [8]. В работе [9] получены производящие функции для помеченных и непомеченных МВП-графов и формула для числа непомеченных МВП-графов, использующая числа Каталана. Полный инвариант МВП-графов и полиномиальный алгоритм определения изоморфизма представлены в [10]. В работе [11] разработан полиномиальный алгоритм расчёта индекса Винера МВП-графов. Такой широкий интерес к изучению МВП-графов вызван тем, что МВП-графы входят в класс хордальных графов, для которых многие NP-трудные задачи теории графов полиномиально разрешимы. Структура МВП-графов определяется количеством вершин степени 2, являющихся симплициальными (т.е. такими, что их окрестность порождает клику). Все МВП-графы, имеющие более двух симплициальных вершин, суть простые 2-деревья [6], а МВП-графы с двумя симплициальными вершинами - это 2-цепи [12]. Далее эти графы будем называть МВП-графами класса 2-цепь. МВП-графы класса 2-цепь могут быть использованы в качестве графовой модели потоковых сетей с источником и стоком, сетевых графиков, электрических двухполюсников, электрических сетей с двумя источниками и с поперечными связями [13, 14]. Однако несмотря на многочисленные исследования по МВП-графам, пока не получено полного описания МВП-графов класса 2-цепь. Это определяет актуальность исследования графов данного класса. В работе полностью описаны МВП-графы класса 2-цепь. В п. 1 приводятся типы МВП-графов класса 2-цепь, их основные свойства и условия укладки графов на двух параллельных линиях. Рекурсивная характеризация, полный инвариант и формула для числа непомеченных МВП-графов класса 2-цепь представлены в п. 2, 3 и 4. В п. 3 описан полиномиальный алгоритм вычисления их полных инвариантов. 1. Типы МВП-графов класса 2-цепь и их свойства Введём необходимые обозначения и определения. Везде далее через G(V, E) обозначается конечный неориентированный связный граф G без петель и кратных рёбер с множеством вершин V и множеством рёбер E. Число вершин и рёбер графа обозначается через n(G) = |V| и m(G) = |E| соответственно. Все основные термины и обозначения приводятся в соответствии с [3]. Полный граф из k вершин есть k-дерево; k-дерево с n + 1 вершинами получается из k-дерева с n вершинами путём добавления в него вершины v и k рёбер, соединяющих вершину v со всеми вершинами некоторой клики размера k (k-клики) [6]. Простым k-деревом называется k-дерево, в котором любая его k-клика является подграфом не более двух (k + 1)-клик. Простое k-дерево с двумя симплициальными вершинами есть 2-цепь [12]. Внутренним графом Int(G) МВП-графа G называется связный граф, образующийся после удаления всех внешних рёбер графа G [7]. Граф типа «гусеница» (или просто гусеница) -это дерево, в котором удаление всех вершин степени 1 приводит к образованию простой цепи [15]. Простая цепь, остающаяся после удаления из гусеницы всех вершин степени 1, называется спином. Вершины степени 1 называются концевыми вершинами или листьями. Двудольный граф G(A U B,E) называется BA-планарным, если его можно уложить на плоскости так, что все вершины размещены на двух параллельных линиях (вершины из множества A на одной линии, а вершины из множества B - на другой) без пересечений рёбер и каждое ребро является отрезком прямой. Уже уложенный таким образом граф называется плоской BA-укладкой графа G(A U B, E) или BA-плоским графом [8]. Граф G называется LL-планарным, если его можно уложить на плоскости так, что все вершины размещены на двух параллельных линиях без пересечений рёбер и каждое ребро является отрезком прямой. Уже уложенный таким образом граф называется плоской LL-укладкой графа G(V, E) или LL-плоским графом [8]. Гамильтоновой степенной последовательностью МВП-графа называется список D = (di,d2,... , dn) степеней вершин графа, упорядоченный в соответствии с порядком следования вершин в гамильтоновом цикле H = (v1, v2,... , v1). В работе [10] показано, что гамильтонова степенная последовательность МВП-графа является его полным инвариантом. Основные свойства МВП-графов описаны в [2, 4-6, 8-11]. Рассмотрим основные свойства МВП-графов класса 2-цепь. Пусть G(V, E) - МВП-граф класса 2-цепь с n вершинами. Тогда граф G имеет две несмежные симплициальные вершины s1, s2, которые разделяют гамильтонов цикл Cn графа на две цепи P1 = (s1, x1, x2,..., xa, s2) и P2 = (s1, y1, y2,..., s2), для которых Pi U P2 = Cra, P1 П P2 = {S1,S2}, X = {X1,X2, . . . ,xa}, Y = {y1,y2, . . . ,yb}. (1) Таким образом, множество вершин V состоит из подмножества V' (|V= n - 2), разделённого на две доли X и Y, и симплициальных вершин s1, s2: V = V' U{s1,s2}, V' = X U Y, X П Y = 0. (2) Множество рёбер E состоит из подмножеств внешних рёбер Eo (|Eo | = n) и внутренних рёбер E/ (|E/1 = n - 3), причём любое внутреннее ребро {u, w} соединяет пару вершин u и w из множеств X и Y: E = Eo U E/, EO = {ег : ег е Cra}, E/ = {ег : ег £ Cra}. (3) Этим условиям удовлетворяют три типа МВП-графов класса 2-цепь. Графы первого типа будем называть графами типа «веер», второго типа - графами типа «лестница», третьего типа - графами типа «цепь». Образцы графов этих трёх типов приведены на рис. 1 (внутренние рёбра изображены утолщёнными линиями, а внешние рёбра - тонкими). 3 3 5 7 9 B...........-jj^-............ B A ..tf^f-Jy-h-Sy^o- A ..-M 1 2 4 5 6 7 2 4 6 8 а б 2 4 5 8 9 10 12 B A 1

Ключевые слова

максимальные внешнеплоские графы, 2-цепь, рекурсивная характеризация, непомеченные графы, полный инвариант, maximal outerplanar graphs, 2-path, enumeration, unlabeled graphs, complete invariant

Авторы

ФИООрганизацияДополнительноE-mail
Носов Юрий Леонидовичг. Липецкyl.nosov@yandex.ru
Всего: 1

Ссылки

Chartrand G. and Harary F. Planar permutation graphs // Ann. Inst. Henri Poincare, Sec. B. 1967. V. 3. No. 4. P. 433-438.
Харари Ф. Теория графов. М.: Мир, 1973. 300с.
Евстигнеев В. A., Касьянов В. Н. Словарь по графам в информатике. Новосибирск: ООО «Сибирское Научное Издательство», 2009. 300с.
Mitchel S. Linear algorithms to recognize outerplanar and maximal outerplanar graphs // Inform. Process. Lett. 1979. V. 5. No. 1. P. 229-232.
Asratian A. S. and Oksimets N. Graphs with hamiltonian balls // Australasian J. Combinatorics. 1998. V. 17. No 4. P. 185-198.
Markov M. On the vertex separation of maximal outerplanar graphs // Serdica J. Computing. 2008. V. 154. No 5. P. 207-238.
Hedetniemi S. M., Proskurowski A. J., and Syslo M. M. Interior graphs of maximal outerplane graphs // J. Combin. Theory. Ser.B. 1985. V. 38. No. 2. P. 156-167.
Cornelsen S., Schank T., and Wagner D. Drawing graphs on two and three lines // J. Graphs Algorithms Appl. 2004. V.8. No. 2. P. 161-177.
Guanzhang Hu. Catalan number and enumeration of maximal outerplanar graphs // Tsinghua Sci. Technol. 2000. V. 5. No. 1. P. 109-114.
Beyer T., Jones W., and Mitchell S. Linear algorithms for isomorphism of maximal outerplanar graphs // J. ACM. 1979. V.26. No. 4. P. 603-610.
Носов Ю.Л. Индекс Винера максимальных внешнеплоских графов // Прикладная дискретная математика. 2014. №4(26). С. 112-122.
Markenzon L., Justel C. M., and Paciornik N. Subclasses of k-trees: Characterization and recognition // Discr. Appl. Math. 2006. V. 154. No. 5. P. 818-825.
Майника Э. Алгоритмы оптимизации на сетях и графах. М.: Мир, 1981. 324с.
Свами М., Тхуласираман К. Графы, сети и алгоритмы. М.: Мир, 1984. 455 с.
Harary F. and Schwenk A. J. The number of caterpillars // Discr. Math. 1973. V. 6. No. 4. P. 359-365.
Harary F. and Schwenk A. J. A new crossing number for bipartite graphs // Utilitas Math. 1972. V. 1. P. 203-209.
Gionfrido M., Harary F., and Tuza Z. The color cost of caterpillar // Discr. Math. 1997. V. 174. No. 1-3. P. 125-130.
http://www.oeis.org/A005418 - Sloane N. J. A. The On-Line Encyclopedia of Integer Sequences.
 О максимальных внешнеплоских графах с двумя симплициальными вершинами | ПДМ. 2015. № 3(29).

О максимальных внешнеплоских графах с двумя симплициальными вершинами | ПДМ. 2015. № 3(29).