Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Реберный граф



Пусть S — непустое множество, a F = { S1, S2,......, Sn }— его покрытие непустыми несовпадающими подмножествами. Определим граф W(F) следующими условиями: V W(F) = F, вершины Si и Sj смежны, если i ¹ j и S iÇ Sj ¹ Æ. Произвольный граф G называется графом пересечений, если и только если существуют такое множество S и такое покрытие этого множества F, что G W(F).

Утверждение 10.1. Любой граф является графом пересечений.

> Пусть G — граф, VG = (1, 2,..., n), S — множество элементов графа G. Для i = обозначим через Si множество, составленное из вершины i и всех инцидентных ей ребер. Положив F = { S1, S2,..., Sn }, получим G W(F). <

Важный класс графов пересечений составляют реберные графы. Для произвольного графа G реберный граф L (G)определяется следующими двумя условиями:

1) VG (G) =EG,

2) вершины e 1 и e 2смежны в L (G)тогда и только тогда, когда ребра e1 и e2 смежны в G.

Если для некоторого графа H существует такой граф G, что H L (G), то H также называется реберным графом.

 
 

На рис. 10.1 совмещены два графа — G и L (G). Вершины графа G — темные кружочки, вершины графа L (G)— светлые кружки. Ребра графа G — тонкие линии, ребра графа L (G) — жирные линии.


Утверждение 10.2. Если d1, d2,..., dnстепенная последовательность (n, m) -графа G, то L (G) является (m, l) -графом, где


> Очевидно, что i -я вершина графа G порождает

 
 

ребер графа L (G), поэтому

Очевидно, что если графы G и H изоморфны, то L (GL (H)также изоморфны. В то же время справедливы соотношения L (K 3) L (K 1,3) = K 3. X. Уитни доказал, что K 3и K 1,3— единственная пара несовпадающих связных графов, имеющих один и тот же реберный граф. Если порядок хотя бы одного из рассматриваемых графов меньше пяти, то это проверяется непосредственно, а для графов больших порядков вытекает из следующей теоремы.

Теорема 10.3 (X. Уитни, 1932 г.). Пусть G и H — связные графы, | G |>4, | H |>4 и L (G) L (H). Тогда G H и, более того, для всякого изоморфизма j: L (G) ->L (H) существует единственный изоморфизм y: G ->H, индуцирующий j, т. е. такой, что j(e) = y(u) y (v) для любого ребра e = uv графа G.

> Изоморфизм j реберных графов L (GL (H) будем рассматривать как биекцию EG->EH между множествами ребер графов G и H, при которой смежным ребрам соответствуют смежные, а несмежным — несмежные.

Лемма 10.4. Если ребра ei (i = ) составляют звезду K 1, r в графе G, то их образы j(ei) составляют такую же звезду K 1, r в графе H.

> Доказательство леммы. При r =2 утверждение леммы верно по определению изоморфизма графов. Пусть r= 3и ребра e 1, e 2, e 3составляют в графе G звезду K 1,3. Поскольку граф G связен и порядок его более четырех, то в нем есть четвертое ребро e, смежное с каждым из ребер e iили точно с одним из них. Таким же свойством обладает j(e) по отношению к j(ei). Ребра j(ei) составляют в графе H либо звезду K 1,3, либо треугольник. Но ребро, смежное с каким-либо ребром треугольника, смежно ровно с двумя из ребер. Тем самым доказано, что ребра j(ei) составляют звезду в графе H. Нужное утверждение доказано для r = 3. Очевидно, что для r >3 оно просто получается по индукции. <

Поскольку отображение j-1: L (H)-> L (G)также является изоморфизмом реберных графов, то из предыдущей леммы вытекает следующее утверждение: ребра ei (i = ) составляют максимальную (относительно включения) звезду K1,r в графе G тогда и только тогда, когда их образы j(ei) составляют максимальную звезду K 1,rв графе H.

Итак, изоморфизм j определяет биекцию между множествами максимальных звезд графов G и H. Очевидно, что в каждой из этих звезд более одного ребра, и потому в ней есть лишь одна центральная вершина. Максимальную звезду графа G с центром x обозначим через SG (x). Очевидно, что если j(SG (x)) = SH (x'), то соответствие y: x -> x' является инъекцией множества всех вершин графа G, не являющихся концевыми, в аналогичное подмножество вершин графа H. Из соображений симметрии следует, что y— биекция.

Теперь распространим действие отображения y на концевые вершины графа G. Пусть v — одна из таких вершин. В графе G есть смежная с ней вершина x степени большей, чем 1. Положим xv = e и выберем в звезде SH (x')такое ребро e' = x'v', что j(e) = e'. Покажем, что


Пусть это не так. Тогда в звезде SH (v')есть ребро e 1' = e'. Следовательно, в звезде j-1(SH (v')) есть ребро e1 = j-1(e 1'), смежное с ребром e, но не входящее в SG (x). Но тогда вершина v — конец этого ребра и deg v ¹1. Равенство (1) доказано.

Положив y(v) = v', получим инъекцию множества концевых вершин графа G в множество концевых вершин графа H. Из соображений симметрии теперь следует, что y — биекция.


Итак, построена биекция y: VG -> VH. Докажем, что эта биекция является графовым изоморфизмом. Сохраним обозначение SG (x)и в том случае, когда deg x = 1. В этой ситуации SG (x)содержит одно ребро, инцидентное вершине x, и не является максимальной звездой. Смежность вершин x и y в графе G означает, что звезды SG (xSG (y)имеют общее ребро. Поэтому

Доказано, что y: G -> H — изоморфизм графов. Из определения отображения y видно, что оно индуцирует j, т. е. j(e) = x'y'= y(x) y(y)для любого ребра e = xy Î EG. Существование нужного изоморфизма y доказано.

Остается доказать единственность. Пусть, напротив, есть два изоморфизма y1¹ y 2, удовлетворяющих условию теоремы. Тогда y1(a) ¹ jy(a) для некоторой вершины a Î VG. Рассмотрим
 
 

произвольное ребро e = ax в графе G. Тогда

и, следовательно, y2(x) = y1(a). Если deg a > 1 и ay — другое ребро G, то аналогично получаем y2(y) = y1(a)=y2(x), что противоречит инъективности y2. Если же deg a =1, то из y2(x) = y1(a) получаем deg x = 1, что противоречит связности G. <

Известно, что не всякий граф является реберным, например, звезда K 1,3не есть реберный граф. (Характеризация реберных графов имеется в книге [7].) Однако класс реберных графов достаточно содержателен. Об этом свидетельствует, в частности, тот факт, что гипотеза реберной реконструируемости произвольных графов эквивалентна гипотезе вершинной реконструируемости реберных графов. Приведем без доказательства следующую теорему.

Теорема 10.5 (Р. Хемминджер, 1969 г.). Связный граф G с более чем тремя ребрами реберно реконструируем тогда и только тогда, когда реберный граф L (G) вершинно реконструируем.

Отметим еще любопытную связь, существующую между матрицей инцидентности графа G и матрицей смежности реберного графа L (G).

Утверждение 10.6. Если I = I (G) — матрица инцидентности графа G и A = A (L (G)) — матрица смежности графа L (G), записанная при той же, что и I, нумерации ребер, то


где Eединичная матрица порядка |EG|.


> Рассмотрим элемент произведения I T I, занимающий позицию (k, l):

Последняя сумма равна числу вершин графа G, инцидентных обоим ребрам с номерами k и l. При k = l это число равно 2. Если k ¹ l, то это число по определению есть элемент Au матрицы A. Равенство (2) доказано. <

Следствие 10.7. Любой корень характеристического полинома всякого реберного графа не меньше, чем –2.

 
 

> Пусть G — реберный граф. Тогда для него верно равенство (2). С другой стороны, пусть Ax = l x для ненулевого вектора x. Тогда ITIx= (l + 2) x (в силу равенства (2)). Теперь рассмотрим квадрат длины вектора lx:

 
 

Следовательно,





Дата публикования: 2015-01-23; Прочитано: 1147 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.008 с)...