Система абстрактных связных подграфов линейного графа | ПДМ. 2012. № 2(16).

Система абстрактных связных подграфов линейного графа

Линейным графом называется граф, полученный из некоторой цепи путём какойлибо ориентации её рёбер. Множество всех графов, изоморфных связным подграфам заданного линейного графа L, упорядочивается отношением вложимости. Выясняется, для каких L это упорядоченное множество будет решёткой.

The system of abstract connected subgraphs of a linear graph.pdf Под ориентированным графом (далее - граф) понимается пара G = (V, а), где V -конечное непустое множество и а С V х V - отношение на нём. Элементы множества Vназываются вершинами графа, а пары, входящие в отношение смежности а, - дугами.Если (и, v) . а, то говорят, что вершина и является началом дуги (и, v), а вершина v -её концом. Граф G можно изобразить на плоскости, сопоставляя каждой его вершиненекоторую точку и проводя отрезок, ориентированный от точки и к точке v, если(и, v) . а.Если V' С V и а' = а П (V' х V'), то граф G = (V', а1) называется подграфом гра-фа G. При |V| = n граф G = (V, а) имеет 2п подграфов (включая и пустой подграф).Изоморфизмом графа G = (V, а) на граф H = (W, в) называется биекцияр : V ^ W, такая, что (Уи, v . V)((U,V) . а ^^ (p(u),p(v)) . в). Два графаизоморфны тогда и только тогда, когда они допускают одно и то же немое (т. е. с точ-ностью до обозначения вершин) изображение. Если граф G изоморфен некоторомуподграфу графа H, то говорят, что G вкладывается в H. Класс G' графов, изоморф-ных подграфу G' графа G, можно трактовать как абстрактный подграф графа G,представленный в G подграфом G'.Вершины u,v . V графа G называются связанными, если (Зи1,и2,.. .Uk . V)((U,U1) . а U а- 1)&((и1 , и2) . а U а - 1 ) & . . . & ( ( u k ,v) . а U а - 1 ) ) . Граф, в которомлюбые две вершины связаны, по определению является связным.Маршрутом с началом и и концом v называется последовательность примыкаю-щих дуг (и, и1), (и1,и2),... , (uk, v). Маршрут можно представить в виде перечисленияпроходимых вдоль него вершин: UU1U2 . . . Uk v. Цепь - это маршрут, в котором все вер-шины разные. Цепь, состоящую из m дуг, обозначим через Pm и будем использоватьдалее её стандартную запись Pm = vcv1 . . .vm.Линейным графом длины m назовём граф L, полученный из цепи Pm переориен-тацией некоторых её дуг. Линейные графы рассматривались в [1] в связи с задачейпостроения минимальных примитивных расширений графов.Прямое изображение линейного графа L длины m получается, если его вершиныvc, v1, v2, . . . , vm расположить в этом порядке слева направо на горизонтальной оси.Отобразив этот рисунок относительно вертикальной оси, проведённой правее верши-ны vm, и пометив отображённые вершины слева направо как vc, v1, v2, . . . , vm, получимобратноеизображение графа L.Если L' - связный подграф линейного графа L, то прямое изображение для L'представляет собой в естественном понимании отрезок в прямом изображении графа L.Пусть L' и L" -два линейных графа и L' допускает вложение в L". Тогда в каче-стве отрезка в L" содержится одно из изображений графа L' - прямое или обратное -с согласованным для каждого случая обозначением соответствующих вершин.Для линейного графа L через ASubc L обозначим совокупность всех линейных гра-фов, вложимых в L. Элементы этого множества можно считать абстрактными связ-ными подграфами графа L. Множество ASubc L упорядочивается отношением вложи-мости: L' ^ L'' для двух его элементов означает, что граф L' вкладывается в граф L".Рассмотрим вопрос о том, для каких линейных графов L упорядоченное множествоASubc L является решёткой, т.е. когда в нём для любых L', L'' существуют точныеграни inf(L', L'') и sup(L', L'').Для неориентированных (т. е. с симметричным и антирефлексивным отношени-ем смежности) графов G близкие вопросы рассматривались различными авторами.Так, в [2] установлены некоторые общие свойства упорядоченных множеств вида(ASubc G, В [3] показано, что не для всякого G упорядоченное множество связныхабстрактных подграфов будет шпернеровым. В [4] дана абстрактная характеризацияупорядоченных множеств рассматриваемого вида. В [5] изучаются решёточные упо-рядочения на множестве ASubcG. В других работах (см., например, [6, 7]) авторыотказываются от условия связности и исследуют упорядоченное множество всех во-обще абстрактных подграфов данного неориентированного графа. В частности, в [7]доказано, что упорядоченное множество всех абстрактных подграфов неориентиро-ванного графа тогда и только тогда будет решёткой, когда либо сам этот граф, либоего дополнение представляет собой полный многодольный граф.Пусть b - некоторый двоичный вектор. Двойственным для него называется век-тор Ъ, получаемый из b, если компоненты вектора b записать в обратном порядке, азатем взаимно заменить в компонентах нули и единицы, т. е. осуществить преобразо-вание Ъ м- (Ъ- 1 ) ' . Понятно, что b^ = Ъ. Например, для Ъ = 011100 будет Ъ = 110001.Под отрезками вектора понимаются блоки, состоящие из подряд идущих компонентэтого вектора. Через ASubc Ъ обозначим совокупность всех попарно не двойственныхотрезков двоичного вектора b. На множестве ASubc Ъ вводится порядок: b' ^ Ъ'', еслиЪ' или (Ъ')й является отрезком в Ъ''.Двоичные векторы естественным образом кодируют линейные графы, а именно,линейному графу L длины m соотносится двоичный m-мерный вектор b = b(L) пу-тём сопоставления каждой дуге графа в прямом изображении символа 1, если эта дуганаправлена от vo к vm, и символа 0 в противном случае. С другой стороны, каждомуm-мерному двоичному вектору Ъ соответствует линейный граф L = L(b) длины m,получающийся из цепи Pm в прямом изображении переориентацией её дуг, согласован-ной со значениями компонент вектора Ъ. Двоичным кодом каждого связного подграфалинейного графа L, очевидно, является отрезок вектора b ( L ).Линейный граф L длины m имеет m(m + 1)/2 связных подграфов, среди кото-рых могут оказаться и изоморфные, так что в ASubc Ъ в общем случае будет меньшеэлементов. Например, у линейного графа L, представленного вектором 0110, имеется10 связных подграфов: 0, 01, 011, 0110, 1, 11, 110, 1, 10, 0, различны (т. е. неизоморфны)из которых 7, а именно: 0, 01, 011, 0110, 11, 110, 10. У графа L=0101 из 10 связныхподграфов различными являются 5: 0, 01, 010, 0101, 10.Л е м м а 1. Если L - линейный граф и Ъ - соответствующий ему двоичный век-тор, то упорядоченные множества (ASubc L, и (ASubc Ъ, изоморфны.Доказательство. Между множествами ASubc L и ASubc b устанавливается вза-имно однозначное соответствие L' м b(L'), b' м L(b'). Пусть L',L'' G ASubcL иL' ^ L'', т.е. L' допускает вложение в L''. Это означает, что в L'' содержится в каче-стве отрезка граф L' в его прямом или обратном изображении. Тогда в векторе b(L'')имеется отрезок, совпадающий с b(L') или с (b(L'))5, т.е. b(L') ^ b(L''). Аналогич-но, если b' ^ b'' для некоторых b', b'' G ASubc b, то L(b') вкладывается в L(b''), т.е.L(b') ^ L(b''). Из леммы следует, что упорядоченное множество (ASubc L, абстрактных связ-ных подграфов линейного графа L является решёткой тогда и только тогда, когдарешёткой является упорядоченное множество (ASubc b, попарно не двойственныхотрезков двоичного вектора b, кодирующего граф L.Пример 1. Рассмотрим диаграммы упорядоченных множеств (ASubcb, длядвоичных векторов b = 00010 (рис. 1,а) и b = 00100 (рис. 1,б).Рис. 1. Диаграмма упорядоченного множества (ASubc b, а - b = 00010; б - b = 00100аКак видим, первое из этих упорядоченных множеств является решёткой, а вто-рое- нет, так как в нем не определён, например, inf(0010,100): у элементов 0010 и 100общими нижними гранями являются элементы 0, 00 и 10, но среди них нет наиболь-шего.В дальнейшем при записи двоичных векторов будем группировать одинаковые ком-поненты и использовать экспоненциальную запись: 01100110010 = 0(1202)210 и т.п.Теорема 1. Пусть L - линейный граф. Упорядоченное множество (ASubc L,его связных абстрактных подграфов тогда и только тогда является решёткой, ко-гда двоичный вектор b, кодирующий этот граф, имеет вид b = 0k(10г ) 5 1 илиb = 1k(0111)50*, где k,l,s,t - неотрицательные целые числа.Доказательство. Необходимость. Пусть для линейного графа L упорядочен-ное множество (ASubc L, является решёткой. Вследствие леммы решёткой будети изоморфное ему упорядоченное множество (ASubcb, где b - двоичный вектор,кодирующий L. Покажем, что в составе вектора b не могут присутствовать одновре-менно триграммы 001, 010 и 100. Пусть это не так и в составе b есть все указанныетриграммы. Тогда в составе b обязательно содержится хотя бы одна из тетраграмм0010 или 0100. Допустим, что таких тетраграмм в b нет. По предположению, в со-ставе b есть триграмма 010. Посмотрим, как может расширяться этот отрезок в b.Добавление 0 ни слева, ни справа невозможно, так как получим запрещённые 0010или 0100. Значит, слева и справа могут быть только 1, т.е. получатся 0101 или 1010.Далее, как только появятся два одинаковых соседних символа (00 или 11), получим0010 (возможно, в виде 1011) или 0100 (возможно, в виде 1101). Следовательно, b со-стоит из чередующихся 0 и 1. Но тогда в составе b нет ни 001, ни 100, что противоречитпредположению.Итак, b содержит все три триграммы 001, 010 и 100 и хотя бы одну из тетраграмм0010 или 0100. Если в b есть 0010, то в (ASubc b, не существует точной нижней гранидля 0010 и 100. Действительно, общими нижними гранями для 0010 и 100 являются 0,00 и 10, но среди них нет наибольшей. Аналогично, если в b присутствует отрезок 0100,то не существует точной нижней грани для 0100 и 001: общими нижними гранями дляэтих элементов будут 0, 00 и 01, но среди них нет наибольшей.Проведённые рассуждения показывают, что в составе b нет по крайней мере однойиз триграмм 001, 010 или 100. Рассмотрим три случая:1) если в b отсутствует 001, то b = 1k(01)s0t , так что этот вектор имеет требуемыйвид;2) если в b отсутствует 100, то b = 0k(10)s0* - требуемый вид;3) если в b отсутствует 010, то b = 0k 1110l21l3 . . . 0h 1* или b = 1k01 11l 20l 3 . . . 1h0*,где li > 1,1 ^ i ^ s.Покажем, что все внутренние блоки имеют одинаковую длину, т. е. что l1 == l2 = l3 = = ls. Предположим, что это не так и в составе b есть внутренниеблоки 0Л и 0м разной длины. Так как эти блоки внутренние, то b содержитотрезки 10Л1 и 10м 1. В ASubc b эти элементы не имеют точной нижней грани,поскольку оба они содержат 01 и 10, но в указанном упорядоченном множественет элемента, который содержал бы 01 и 10 и содержался бы в 10Л1 и в 10м 1.Если же в составе b есть внутренние блоки 0Л и 1м разной длины, то в ASubc bне существует inf(10Л1, 01м0), так как оба эти элемента содержат 01 и 10, нов указанном упорядоченном множестве нет никакого элемента, содержащего 01и 10 и содержащегося в 10Л1 и 01м0. Итак, b = 0k(1101)s1t или b = 1k(011z)s0*,где l > 1, что соответствует утверждению теоремы.Достаточность. Пусть b = 0k(110z)s1*, где k,l,s,t - неотрицательные целые числа(второй случай рассматривается вполне аналогично). Возможными отрезками в b яв-ляются векторы следующих видов: 1) 0"; 2) 0"1b; 3) 0"10b ; 4) 0" 110г16; 5) 0Пг0г 1г06;6) 0"(1г0г)°" 1b; 7) 0 " ( 1 г0г110b , где a,b,a - положительные целые числа Покажем, что улюбых двух отрезков есть точная нижняя грань в (ASubcb, т.е. что это упорядо-ченное множество является нижней полурешёткой. В п. ij указывается точная нижняягрань для отрезков i и j, 1 ^ i ^ j ^ 7. Заметим ещё, что inf((b1 ) 5 , (b2 ) 5 ) = (inf(b1, b 2 ) ) 5для любых отрезков b1 , b2 вектора b.1112131415161722232425nf(0", 0b)_0m i n ( " ' b );n f ( 0 " 06 1 c ) 0min(a,max(b,c));nf ( 0 " 0b 1 l 0 c ) 0min(a,max(b,1,c));n f ( 0 " 0b 1 l0l1c) 0min(",max(b,1,c));nf ( 0 " 06110^ 110c) 0min(",max(b,1,c));nf (0" 06(1г0г)ст 1c) 0min(",max(b,1,c));nf (0" 06(1г0г)ст 1'0c) 0min(",max(b,1,c));nf(0"1b 0c1d) 0min(max(a,b),max(c,d)) 1min(a,,b,c,d);nf(0"1b 0c10d ) 0min(max(a,b),max(c,1)) 1min(a,b,max(a,1));nf(0"1b 0c1l 0^ 1 d ) 0min(max(a,b),max(c,d,1)) 1min(a,,b,max(c,d,1));nf(0"1b 0c1l 0^ 110d) 0min(max(a,b),max(c,Z,)) 1min(a,b,max(c,1));26) inf (0а1Ь 0е(110')СТ 1^) 0min(max(a,b),max(c,d,Z)) 1min(a,b,max(c,d,Z)).27) inf (0а1Ь 0С(10')СТ 1'0d) 0min(max(a,b),max(e,1,)) 1min(a,b,max(c,Z)).3 3 ) i n f ( 0 a 1 ' 0 b 0C1'0d ) 0min(max(a,b),max(e,1)) 1'0min(max(a,b),max(d,1)).34) inf(0"1' 0^ 0 ^ 0 ' 1^) 0min(a, max(c,d)) 1'0min(b,1).35) inf(0a1' 0^ 0C1'0' 1' 0d ) 0min(a,max(c,1)) 1'0min(b,max(d,1)).36) inf(0a1' 0^ 0C(1'0' )a 1d ) 0min(a,max(c,d,1)) 1'0min(b,1).37) inf(0a1'0^ 0C(1'0')a 1'0d) 0min(a,max(c,d,1)) 1'0min(b,Z).4 4 ) i n f ( 0 a 1 ' 0 ' 0c 1 ' 0 ' 1d) 0min(max(a,b),max(c,d)) 1 ' 0 ' 1min(a,b,c,d).4 5 ) i n f ( 0 a 1 ' 0 ' 0c 1 ' 0 ' 1 ' 0 d ) 0min(max(a,b),max(c,')) 1 ' 0 ' 1min(a,b,c,d).4 6 ) i n f ( 0 a 1 ' 0 ' 0 c ( 1 ' 0 ' 1 d ) 0min(max(a,b),max(c,d,Z)) 1 ' 0 ' 1min(a,b,c,d,Z).4 7 ) i n f ( 0 a 1 ' 0 ' 0 c ( 1 ' 0 ' 1 ' 0 d ) 0min(max(a,b),max(c,Z)) 1 ' 0 ' 1min(a,b,c,Z).5 5 ) i n f ( 0 a 1 ' 0 ' 0c 1 ' 0 ' 1 ' 0 d ) 0min(max(a,c),max(c,Z)) 1 ' 0 ' 1'0min(b,d).56) inf (0a 1'0' 1'0b 0c (1'0')CT ld)_0min(a,mаx(c,Z)) 1'0' 1'0min(b,Z).57) inf (0a 1'0' 1'0b 0c (1'0')CT 1'0d) 0min(a,mаx(c,Z)) 1'0' 1Z0min(b,d,Z).6 6 ) i n f ( 0 a ( 1 ' 0 ' 0 c ( 1 ' 0 ' ) T 1d) 0min(a,max(c,d,Z)) (1Z0Z)min(a",r) 1min(a,b,c,d,Z).6 7 ) i n f ( 0 a ( 1 ' 0 ' 0 c ( 1 ' 0 ' ) T 1 ' 0 d ) 0min(max(a,b),max(c,Z)) (1Z0')min(

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

линейный граф, абстрактный подграф, упорядоченное множество, решётка, двоичный вектор, двойственность, path, linear graph, abstract subgraph of a graph, ordered set, lattice, binary vector, duality

Авторы

ФИООрганизацияДополнительноE-mail
Салий Вячеслав НиколаевичСаратовский государственный университет им. Н. Г. Чернышевскогокандидат физико-математических наук, заведующий кафедрой,профессорSaliiVN@info.sgu.ru
Всего: 1

Ссылки

Салий В. Н. Минимальные примитивные расширения ориентированных графов // Прикладная дискретная математика. 2008. №1(1). С. 116-119.
Trotter W. T. and Moore J. I. Some theorems on graphs and posets // Discr. Math. 1976. V. 15. No. 1. P. 79-84.
Jacobson M. S., Kezdy F. E., and Seif S. The poset of connected induced subgraphs of a graph need not be Sperner // Order. 1995. V. 12. No.3. P. 315-318.
Kezdy A. E. and Seif S. When is a poset isomorphic to the poset of connected induced subgraphs of a graph? // Southwest J. Pure Appl. Math. 1996. V. 1. P. 42-50. (Electronic.)
Nieminen J. The lattice of connected subgraphs of a connected graph // Comment. Math. Prace Mat. 1980. V.21. No. 1. P. 187-193.
Adams P., Eggleton R. B., and MacDougall J. A. Degree sequences and poset structure of order 9 graphs // Proc. XXXV Southeast. Conf. Comb., Graph Theory and Computing. Boca Raton, FL, USA. 2004. V. 166. P. 83-95.
Leach D. and Walsh M. A characterization of lattice-ordered graphs // Proc. Integers Conf. 2005. N.Y.: Gruyter, 2007. P. 327-332.
 Система абстрактных связных подграфов линейного графа | ПДМ. 2012. № 2(16).

Система абстрактных связных подграфов линейного графа | ПДМ. 2012. № 2(16).

Полнотекстовая версия