Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

3) 4). Пусть ab и tz–два ребра графа G. По условию G имеет простые циклы S и S', первый из которых содержит ab и z, а второй – ab и t. Далее искомый цикл строится так же, как в предыдущих пунктах.

4) 5). Пусть a,b VG, tz EG. Будучи связным, граф G содержит простую цепь P=(a,x,…,b). Согласно утверждению 4) а графе G есть простой цикл S, содержащий ребра ax, tz. Легко видеть, что в объединении S P имеется требуемая цепь.

5) 6). Пусть a,b,c VG, cd EG. По условию в графе имеется простая (a,b)–цепь, проходящая через cd и, следовательно, содержащая c.

6) 1). Пусть v VG. Покажем. Что граф G – v связен, т.е. любая a,b его вершин соединена цепью. Действительно, согласно утверждению 6) в графе G имеется простая (v,b)-цепь, которая, очевидно, не проходит через v и, следовательно, является (a, b)-цепью и в графе G – v. Доказано.

Если в формулировке теоремы 34.1 заменить всюду слова «простая цепь» и «простой цикл» соответственно на слова «цепь» и «цикл», то получим аналогичную теорему о 2–реберно–связном графах.

Как отмечалось выше, при решении многих задач на графах достаточно уметь решать эти задачи для каждой 2–связной компоненты графа. Поэтому представляет интерес взаимное расположение 2–компонент в графе.

Максимальные относительное включения элементы множества связных подграфов графа G, не имеющих точек сочленения, называются его блоками. Таким образом, каждый блок графа либо 2–связен, либо совпадает с К₂ или К₁ (граф К₁ – блок тогда и только тогда, когда он является связной компонентой). Связный граф без точек сочленения также называют блоком.

Множество вершин блока будем называть блоковым множеством.

Например, граф, изображенный на рис. 5.2, содержит пять блоков B_i (i=1,2,3,4,5) (они обведены пунктирными линиями). Среди этих блоков В₁, В₂ и В₃ –2-связные графы, а каждый из двух оставшихся является ребром.

Утверждение 5.2. Любые два блока графа имеют не более одной общей вершины. В частности, всякое ребро графа входит только в один его блок.

Утверждение 5.3. Если блок графа содержит вершины a и b, то он содержит и всякую простую (a, b)-цепь этого графа.

Эти утверждения непосредственно следуют из перечисленных в начале параграфа свойств 2–связных графов и теоремы 5.1.

Следствие 5.4. Система блоковых множеств графа является покрытием множеств его вершин. Каждая пара блоковых множеств либо не пересекаются, либо имеют единственную общую вершину, и эта вершина является точкой сочленения графа.

Следующая конструкция дает представление о структуре графа «с точностью до блоков». Пусть В=В{B_i} и С={c_i} – соответственно множества блоков и точек сочленения графа G. Сопоставим с G граф bc(G), у которого B C – множество вершин и {B_ic_i: B B, c_i C, c_i B_i} – множество ребер. Тем самым, ребра двудольного графа bc(G) указывают на принадлежность точек сочленения блоками. На рис. 5.3 представлены графы G и bc(G).

Утверждение 5.5. Если граф G связен, то bc(G)–дерево.

Доказательство:

Очевидно, что из связности графа G вытекает связность графа bc(G).

Предположим, что bc(G) содержит цикл С. Пусть этот цикл имет вид С=(c , b ,c , b ,…,c ,b ,c ). Каждый из блоков B содержит (с ,с )- цепь и объединение этих цепей дает простой цикл в графе G. Обозначим этот цикл через С'. Ясно, что С' содержит по крайне мере две вершины каждого из блоков B . Поэтому из утверждения 34.3 следует, что цикл С' должен содержаться в каждом их этих блоков. Последнее означает, что каждая пара блоков B имеет не менее |C'| 3 общих вершин. Получаем противоречие с утверждением 5.2. доказано.

Граф bc(G) называется bc–деревом связного графа G.

Блоки графа G, соответствующие концевым вершинам его bc–дерева, называются концевыми блоками.

Похожее представление графа можно получить, положив в основу его максимальные реберно-2-связные подграфы, т.е. максимальные связные подграфы, не содержащие мостов. Такие подграфы называют листами. Не останавливаясь на деталях заметим следующее. Каждая вершина графа порядка n>1 принадлежит в точности одному листу и каждое ребро, не являющееся мостом, входит только в один лист. Таким образом, граф состоит из листов и мостов, соединяющих некоторые из них. Для описания строения графа «с точностью до листов» можно ввести граф, аналогичный графу bc(G). Вершины такого графа биективно соответствуют листам графа G и две его вершины соединены ребром в том и только в том случае, когда соответствующая пар листов в G соединена мостом. Можно показать, что введенный таким образом граф является деревом, если исходный граф связен.

На рис. 5.4 граф G имеет 5 листов L₁, L₂, L₃, L₄, L₅ и 4 моста, а граф G' показывает, как связаны между собой листы графа G.

Приведем некоторые результаты о трехсвязных графах, которые будут использованы в главе «Планарность».

Пусть G–связный граф, H–некоторый его подграф. Простую открытую цепь . графа G назовем H–цепь, если выполняются условия

v₁ VH, v_k VH, v_i VH, i=

ребро e=uv графа G также будем называть Н–цепь, если u VH, v VH, e EH.

Лемма 5.6. Пусть G–двусвязный граф. Тогда для всякого его подграфа Н, содержащего более одной вершины и отличного от G, существует Н–цепь графа G.

Доказательство

Если Н–остовный подграф, то любое ребро графа G, не входящее в EH, служит Н–цепью.

Пусть подграф не является остовным. Рассмотрим три попарно различные вершины u VH, v VH, w VH. По теореме 5.1 в графе G есть проcтая (u,v) – цепь, проходящая через w. Очевидно существование подцепи этой цепи, являющейся Н – цепью графа G. Доказано.

Ниже для u,v VG положим G_uv = G-u-v.

Теорема 5.7. Во всяком 3-связном графе G есть такое ребро uv, что граф G_uv не имеет точек сочленения.

Доказательство

Если |G|=n=4, то утверждение теоремы очевидно . Поэтому будем считать, что n 5. Предположим противное, т.е. что для любого ребра uv EG граф G_uv имеет хотя бы одну точку сочленения. Тогда на 3-связности графа G следует, что при любом выборе ребра uv EG граф G_uv обладает следующими свойствами (рис. 5.5):

1. если а – висячая вершина графа G_uv, то av EG, au EG;

2. всякий висячий блок графа G_uv, не являющийся ребром , содержит такую пару вершин с и d, отличных от точек сочленения графа G_uv, что uc EG, vd EG.

3. всякий блок графа G_uv, имеющий ровно две точки сочленения и отличный от ребра, содержит такую вершину l, не являющуюся точкой сочленения графа G_uv, что или ul EG.

Обозначим через B_uv максимальный по числу вершин блок графа G_uv, а через t_uv– число вершин в этом блоке . Теперь выберем ребро uv так, чтобы число t_uv было наибольшим.

Покажем, что в этом случае t_uv 3. Пусть t_uv=2 и а – висячая вершина графа G_uv (являющегося деревом). Так как n 5, то существует ребро cd EG_uv. Из свойства 1) вытекает, что в графе G_cd существует цикл (u,a,v,u), т.е. t_cd>t_uv. Получено противоречие, следовательно, t_uv 3.

Через D_uv обозначим bc-дерево графа G_uv и рассмотрим следующие случаи.

1. Дерево D_uv не является цепью. Выберем в этом дереве цепь, соединяющую пару висячих вершин и проходящую через вершину, соответствующую блоку B_uv. Этой цепи соответствует последовательность B₁,…,B_p блоков графа G_uv, среди которых содержится блок B_uv, причем блоки B₁ и B_p являются висячими (рис. 5.6).

Пусть B'– произвольный висячий блок графа G_uv, отличный от B₁ и B_p. Из свойств 1) и 2) вытекает существование таких отличных от точек сочленения графа G_uv вершин a VB₁, b VB_p, c VB', uc EG, va EG, vb EG. Тогда в графе G_uc вершины множества входят в один блок и, следовательно, t_uv<t_uc. Последнее противоречит выбору ребра uv.

1. Дерево D_uv–цепь и B_uv–блок графа G_uv, не являющийся висячим. Пусть B₁,…,B_p – последовательность всех блоков графа G, причем блоки B₁ и B_p–висячие, B_i B_i+1 Ø (i= ), B_uv=B_k (1<k<p) (рис. 5.7). Cогласно свойству 3) найдется вершина b VB_uv отличная от точек сочленения графа G_uv, смежная с u или с v. Пусть ub EG. Согласно свойствам 1) и 2)

существует такие отличные от точек сочленения графа G_uv вершины a VB₁, c VB_p, что ua EG, vc EG. Легко видеть, что в графе G_vc имеется блок, содержащий все вершины множества . Поэтому t_vc>t_uv, и снова получаем противоречие.

1. Дерево D_uv – цепь и B_uv – висящий блок графа G_uv. Если граф G_uv содержит такое ребро xy, что VB_uv {x, y}=Ø, то, используя свойство 2), легко показать, что в графе G_xy есть блок, содержащий множество вершин VB_uv {x, y}, а, значит t_uv<t_xy. Так как B_uv – висячий блок графа

G_uv, то последнее означает, что граф G_uv состоит из блока B_uv и ребер ab₁,ab₂,…ab_l (рис 5.8). Из 3–связности графа G следует, что граф G – а не имеет точек сочленения. Поскольку в графе G– a вершина b₁ смежна только с вершинами u и v, a uv EG, то граф также не имеет точек сочленения, что противоречит предположению.

Таким образом , показано ,что во всяком связном графе G существует такое ребро uv, что граф G_uv не имеет точек сочленения. Доказано.

Следствие 5.8. Всякий 3–связный граф с числом вершин n 5 содержит ребро, стягивание которого приводит к 3–связному графу.

Доказательство также проведем от противного. Пусть, стягивая некоторое ребро x=uv 3–связного графа G в вершину , получаем граф G_x, для которого (G_x)=2 (Равенство (G_x)=1 невозможно в силу 3–связности графа G). Тогда в графе G_x существуют две вершины, удаление которых делают его несвязным. Одной из них должна быть (в противном случае (G_x)=2). Удалению вершины из G_x соответствует удаление вершины u и v из графа G. Поэтому для любого ребра x=uv EG граф G имеет такую вершину w, что граф G–u–v–w несвязен. Вершина w является точкой сочленения графа G_uv, что противоречит предыдущей теореме. Доказано.

Отметим без доказательства следующую теорему.

Теорема 5.9. Почти все ребра двусвязны.

Поскольку каждый мост инцидентен точкам сочленения графа, то из этой теоремы вытекает

Следствие 5.10. Почти все графы не содержат мостов.

§6 Теорема Менгера.

Из теоремы 5.1 следует, что 2–граф связен тогда и только тогда, когда любые две его несовпадающие вершины a и b соединены парой простых (a, b) цепей, не имеющих общих вершин, за исключением a и b. Аналогичный критерий k–связности справедлив при произвольном k.

Говорят, что множество вершин S разделяет несмежные вершины a и b связного графа G, если в графе G – S вершины a и b принадлежат различным связным компонентам. В этой ситуации множество S называют также сепаратором или (a, b)–сепаратором. Две (a, b)–цепи графа G называют непересекающимися, если у них нет общих вершин, за исключением a и b, и реберно–непересекающимися, если у них нет общих ребер. Очевидно, непересекающиеся цепи являются и реберно–непересекающимися, а обратно, вообще говоря, неверно.

К. Менгер доказал в 1927 году следующую теорему, устанавливающую соотношение между числом непересекающихся простых цепей, соединяющих две несмежные вершины графа, и его связностью.

Теорема Менгера. Наименьшее число вершин, разделяющих две несмежные вершины графа a и b, равно наибольшему числу попарно непересекающихся простых (a, b)–цепей этого графа.

Приведем доказательство принадлежащее В. Маквайгу (1982 г.).

Ясно, что если k вершин разделяют a и b, то существует не более k попарно непересекающихся (a, b)–цепей. Остается показать, что если в графе G нет множества, содержащего менее чем k вершин, разделяющих несмежные вершины a и b, то в нем имеется k попарно непересекающихся цепей. Используем индукцию по k. утверждение правильно при k=1. Предположим, что оно верно для некоторого k 1. Рассмотрим граф G, в котором несмежные вершины a и b нельзя разделить множеством, содержащим менее чем k+1 вершин. По предположению индукции в G имеется k попарно непересекающихся (a, b)–цепей P₁, P₂, …, P_k. Рассмотрим множество вторых (считая а первой) вершин в этих цепях. Это множество состоит из k вершин и, следовательно, но оно не разделяет вершины a и b. Значит, имеется (a, b)–цепь Р, первое ребро которой не принадлежит ни одной из цепей P_i (i= ). Пусть v–первая, считая от а, вершина Р, принадлежащая одной из P_i (i= ), и пусть P_k+1 обозначает (a, v)–подцепь цепи Р. Цепи P₁, …, P_k, P_k+1 могут быть выбраны, вообще говоря, многими различными способами. Выберем их так, чтобы в графе G – a расстояние v до b было минимально. Если окажется, что v=b, то P₁, P₂, …, P_k+1 будет требуемым набором k+1 цепей. Допустим, что v b. Тогда в графе G – v вершины a и b нельзя разделить множеством, содержащим менее чем k вершин. По индуктивному предположению в этом имеется k непересекающихся (a, b) – цепей Q₁, Q₂, …, Q_k, которые могут быть выбраны разными способами. Выберем их так, чтобы множество

включало минимальное число ребер этих цепей. Иначе говоря, цепи Q_i должны состоять «в основном» из ребер цепей P_i. Рассмотрим теперь граф H, состоящий из вершин и ребер цепей Q₁, Q₂, …, Q_k и вершины v (эта вершина будет в графе H изолированной). Пусть P_r – одна из цепей P_i (i= ), у которой ребро, инцидентно вершине а, не принадлежит EH. Ясно, что такая цепь среди P_i (i= ) найдется, поскольку число их равно k+1, а цепей Q_i, составляющих H, только k. Пусть, далее, x–первая, считая от а, вершина P_r, входящая в VH.

Если x=b, то, добавив цепь P_r к Q₁, Q₂, …, Q_k, получим требуемый набор из k+1 (a, b) цепей. Допустим, что x b, и рассмотрим другие возможности для x.

Если x=v, то обозначим через R кратчайшую (v, b) – цепь и G – a. Пусть z – первая, считая от v, вершина цепи R, лежащая на некоторой Q_j (j= ). Объединим цепь P_r c (v, z) – подцепью цепи R и обозначим полученную (a, z) – цепь через Q_k+1. Цепи Q₁, Q₂, …, Q_k, Q_k+1 обладают тем свойством, что расстояние в графе G – a от z до b меньше, чем расстояние от v до b , а это противоречит выбору P₁, P₂, …, P_k, P_k+1.

Рассмотрим теперь последнюю возможность: x принадлежит некоторой цепи Q_j (j= ). В этом случае (a, x) – подцепь цепи Q_i имеет ребра в L, иначе бы две цепи в { P₁, P₂, …, P_k, P_k+1} пересекались в вершинах, отличных от a, b, v. Заменив теперь (a, x) – подцепь Q_i на (a, x) – подцепь P_r, получим непересекающиеся (a, b) – цепи в графе G – v, и эти цепи будут использовать меньше ребер из L, чем Q₁, …, Q_k. Снова получаем противоречие, которое и завершает доказательство теоремы.

Из теоремы Менгера непосредственно вытекает

Теорема 6.1. (Х. Уитни, 1932 г.). граф k–связен тогда и только тогда, когда любая пара его несовпадающих вершин соединена по крайне мере k непересекающимися цепями.

Имеется несколько аналогов и обобщений теоремы Менгера. Здесь мы остановимся на реберном варианте этой теоремы.

Во многих прикладных задачах приходится рассматривать множество ребер (а не вершин, как ранее), разделяющих вершины a и b графа G, т.е. такое множество ребер R, что входит в различные компоненты графа G – R. Минимальное относительно включения множество R с этими свойствами называется (a, b) – разрезом графа.

Теорема 6.2. Наибольшее число реберно–непересекающихся цепей, соединяющих две вершины графа, равно наименьшему числу ребер, разделяющих эти вершины.

Доказательство этой теоремы легко получить, используя теорему Менгера. С этой целью сопоставим графу G граф G', который получается из G следующим образом. Каждая вершина v VG заменяется группой из deg v

попарно смежных вершин, а ребра графа G', соединяющие вершины из разных групп, находятся в биективном соответствии с ребрами графа G' (рис. 6.1). Если в графе G нет (a, b) – разреза, содержащего менее чем k ребер, то в G' нет множества, имеющего менее чем k вершин, разделяющего какую-либо пару вершин a', b' из групп, соответствующих a и b. Тогда по теореме Менгера вершины a', b' соединены в G' по крайней мере k вершинно-непересекающимися цепями , которым соответствует столько же реберно-непересекающихся (a, b) – цепей графа G.

С другой стороны, ясно, что граф, имеющий (a, b) – разрез из k ребер, может содержать не более k реберно- непересекающихся (a, b) – цепей.

Глава III

Выделение k непересекающихся остовных деревьев

2k–реберно связном графе

Из классического результата теории графов – теоремы Менгера– известно, что для любых двух вершин x и y графа G локальная реберная связность (x, y, G) равняется наибольшему количеству непересекающихся по ребрам путей от x до y в графе G. Однако, при k>1 не во всяком графе G с реберной связностью (G) k существуют k непересекающихся по ребрам связных остовов. Из ранее известных результатов «глобальным ананлогом» теоремы Менгера в некоторой степени является доказанный результат: в графе G с реберной связностью (G) k существуют k остовных деревьев T₁, T₂, …, T_k такие, что для любого j от 1 до k объединение деревьев T₁, T₂, …, T_j дает j–реберно связный граф.

В настоящей работе мы рассматриваем еще один глобальный аналог теоремы Менгера: будет доказано, что при (G) 2k в графе G существует k остовных деревьев, не имеющих общих ребер. Мы докажем необходимость условия (G) 2k при k>1. Более того, мы построим примеры (2k-1)–связныцх графов, у котороых минимальная степень вешины больше любого заданного числа, но среди любых k связных остовов какие–то два имеют общее ребро.

В нашей работе используется редукционная техника, которую разработал . Введем необходимые понятия и обозначения.

Пусть W– множество из нескольких вершин графа G. Через G-W мы, как обычно, будем обозначать граф, полученный из G при удалении всех вершин множества W и всех выходящих из них ребер. Пусть F– множество из нескольких ребер графа G. Через G-F мы , будем обозначать граф, полученный из G при удалении вcех ребер множества F.

Для произвольной вершины x графа G через d_G(x) мы будем обозначать степень вершины x в графе G(V, E). Для x V, A V через d_G(x, A) обозначим количество ребер, соединяющих вершину x с вершинами множества A (с учетом кратных ребер). Минимальную степень вершины в графе G будем обозначать через (G), a максимальную степень– через (G).

Пусть z–вершинa четной степени в графе G. Рассмотрим граф G-z, разобъем на пары все вершины, смежные в графе G с z и соединим вершины в парах. Полученный граф G^z назовем разрезом графа G по вершине z.

§7. Построение k непересекающихся остовных деревьев.

Теорема 7.1. Пусть граф G(V, E) таков что (G)=k, а вершина z V не является точкой сочленения. Тогда существует такой разрез G^z графа G по вершине z, что для любых x,y V\{z} выполняется соотношение (x, y, G^z)=(x, y, G) и, в частности (G^z) (G).

Замечание. Доказательство обобщается на случай , когда вершина z–точка сочленения, но ни одно из ребер с концами в z не является мостом. В частности, при (G) 2 для любой вершины z существует разрез по z такой, что (G^z) (G).

Теорема 7.1 позволяет редуцировать граф, не уменьшая реберной связности. Это открывает широкие возможности для построения различных конструкций. В наших конструкциях также использует последовательные разрезы графа по вершинам опирается на теорему 7.1.

Для построения нам также потребуется классический результат относительно минимально k–связных графов.

Теорема 7.2. Пусть степени всех вершин мультиграфа G(V, E) строго более k и (G) k. Тогда существует ребро e E такое, что (G-e) k.

Замечание. Впервые результат теоремы 7.2 для графов без кратных ребер доказал . Это доказательство обобщается на случай мультиграфа .

Перейдем к доказательству основного результата настоящей работы.

Теорема 7.3. Пусть мультиграф G(V, E) (в нем допускается наличие кратных ребер, но запрещены петли) таков, что (G) 2k. Тогда у мультиграфа G существуют попарно k непересекающиеся ребра остовных дерева.

Доказательство. Будем доказывать теорему индукцией по количеству вершин в мультиграфе G₀. База для мультиграфа с двумя вершинами очевидна. Предположим, что теорема доказана для любого 2k– реберно связного мультиграфа, у которого меньше вершин, чем у G. По теореме 7.2, у графа G(V, E) существует остовный подграф G₀(V, E₀), такой, что (G₀)=2k и одна из его вершин z V имеет степень d (z)=2k. Очевидно , что граф G₀–z связен, следовательно, по теореме 7.1 существует разрез G графа G₀ по вершине z такой, что (G ) 2k. Если в графе G есть петли, то уберем их. Из условия (G ) 2k следует, что графа G₁, полученного из G в результате удаления петель, выполняется условие (G₁) 2k.

Назовем новыми ребра графа G₁, добавленные при разрезе по вершине z. Пусть этo ребра e₁, …, e_m. Поскольку при построении разреза было добавлено k ребер, после чего были удалены петли, то m k. По индукционному предположению, у графа G₁ существуют непересекающиеся по ребрам остовные деревья T₁, T₂, …, T_k. Опишем метод построения по каждому из этих k деревьев остовного графа G. Все ребра, которые могут входить в деревья T₁, T₂, …, T_k, либо являются ребрами графа G, либо новыми ребрами. Пусть дерево T_i содержит m_i новых ребер, тогда

m₁+m₂+…+m_k m k (1)

Если дерево T_i не содержит ни одного нового ребра, то оно является подграфом мультиграфа G. Поскольку множество вершин дерева T_i содержит все вершины графа G, кроме z, то добавив к T_i вершину z и любое ребро графа G с концом в z, мы получим остовное дерево T'_i графа G. Отметим, что в этом случае для построения дерева T'_i потребовалось одно ребро графа G, инцидентное вершине z (причем это ребро можно выбрать произвольно).

Предположим, что m_i>0, то есть дерево T_i содержит новые ребра. Поставим в соответствие дереву T_i подграф T_i^* графа G, в котором каждое новое ребро xy дерева T_i заменим на два ребра xy и yz графа G. Каждое новое ребро в дереве T_i соответствует двум ребрам в графе T_i^*, при этом, к вершинам дерева добавляется вершина z. Следовательно, мы получили связный остовный подграф T_i^* графа G, в котором количество ребер на m_i-1 больше , чем в дереве. Таким образом, в графе T_i^* ровно m_i-1 цикл, причем не трудно заметить, что каждый из этих циклов проходит через вершину z. Следовательно, из графа T_i^* можно удалить m_i-1 инцидентных вершине z ребер так, что получится отстовное дерево T_i^' графа G. В дерево T_i^' входит m_i+1 ребро, инцидентное вершине z. По построению очевидно, что при i j, m_i>0 и m_j>0 остовные деревья T_i^' и T_j^' графа не имеют общих ребер.

Пронумеруем k непересекающихся по ребрам остовных деревьев графа G таким образом, чтобы деревья T₁, …, T_n содержали новые ребра, а деревья T_n+1, …, T_k не содержали новых ребер (где 0 ). С помощью описанного выше способа построим по остовным деревьям T₁, …, T_n графа G₁ остовные деревья T'₁, …, T'_n графа G, никакие два из этих деревьев не будут иметь общих ребер. Всего при построении этих n деревьев использовано (m₁+1)+…+(m_n+1) ребер графа G, инцидентных вершине z. В силу неравенства (1), мы получаем, что

(m₁+1)+…+(m_n+1)=(m₁+m₁+…+m₁)+n (2)

Следовательно, в силу неравенства (2), и так как d_G(z) , остались неиспользованными еще хотя бы n-k ребер графа G, инцидентных вершине z. Для дополнения каждого из оставшихся деревьев T_n+1, …, T_k до остовного дерева графа G требуется еще по одному ребру, инцидентному вершине z, причем это ребро можно выбрать произвольно. Таким образом, мы можем построить попарно k непересекающихся по ребрам отстовных дерева графа G.

§8 Необходимость условия (G) 2k.

Мы покажм необходимость условия (G) 2k для выделения k попарно непересекающихся по ребрам остовных деревьев из графа G. Более того, при n>1 для любого n мы построим (2k-1)–вершинно связный граф G_n, у которого степени всех вершин более n, но среди любых k связных остовов графа G_n какие–то два имеют общее ребро. Таким образом, ослабление условия реберной 2k–связности нельзя «компенсировать», накладывая допoлнительно условия на минимальную степень вершины и условие вершинной (2k-1)–связности. Перейдем к построению серии примеров.

Определение.8.1. Пусть A V–множество из некотрорых вершин графа G(V, E). Определим граф G^A с множеством вершин (V\A) (где a ). Удалим в графе G все ребра между вершинами из множеcтва А, объединим все вершины множемтва А в одну новую вершину а. Для любой вершины b , мы добавим ровно d_G(b, A) ребер ab. Все вершины из V\A и соединяющие их ребра в графе G^A будут же, как и в графе G. Назовем построенный граф G^A стягиванием графа G по множеству А.

Лемма 8.2. Пусть в графе G(V, E) есть k попарно непересекающихся по ребрам остовных дерева. Тогда для любого A V в графе G^A также есть k попарно непересекающихся по ребрам остовных дерева.

Доказательство. Пусть T₁, T₂,…, T_k –остовные деревья графа G. По определению стягивания нетрудно заметить, что графы T^A₁, T^A₂,…, T^A_k связны и никакие два из них не имеют общих ребер.

Определние 8.3. Пусть граф H(V, E) не имеет кратных ребер, a V, n>d_H(a). Пусть граф H получен из Н в результате замены вершины а на полный грaф K_n, причем все ребра, инцидентные вершине а в графе Н, в H будут из разных вершин соответствующего Н полного графа K_n.

Для n> определим граф Hⁿ, в котором каждую вершину а графа H заменим полным графом K_n (других вершин в Hⁿ нет). Для каждого ребра ab графа Н проведем в графе Hⁿ ребро, соединяющее какие–то две вершины из соответствующих a и b полных графов (такие ребра графа Hⁿ мы назовем главными). При этом, мы проведем главные ребра так, чтобы никакие два из них не имели общего конца (это возможно так, как n> ).

Текст программы

unit diplom;

interface

uses

Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,

StdCtrls, Buttons, ExtCtrls, Menus, CheckLst, ActnList;

type

masiv = set of byte;

TForm1 = class(TForm)

BitBtn1: TBitBtn;

Image1: TImage;

Image2: TImage;

ComboBox1: TComboBox;

Label1: TLabel;

procedure Image1MouseDown(Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

procedure Image1MouseUp(Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

procedure FormActivate(Sender: TObject);

procedure ComboBox1Change(Sender: TObject);

private

{ Private declarations }

function Proverka(ind: byte): boolean;

procedure Newselect(ind: byte);

procedure Duga(ind:byte);

procedure Graph;

public

{ Public declarations }

end;

var

Form1: TForm1;i:integer;

b,b1,b2,b4:boolean;

Data: array[1..20] of record x1,y1:integer;end;

matr,matr_edit:array[1..40,1..40] of integer;

mas_x,mas_y : masiv;

x2,y2:integer;

implementation

{$R *.DFM}

//************************esli mouse najata*****************************

procedure TForm1.Image1MouseDown(Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

begin

canvas.MoveTo(x,y); x2:=x;y2:=y;

if (ssleft in Shift) then b:=true

else

if (ssRight in Shift) then b:=false else

end;

procedure TForm1.Image1MouseUp(Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

var k,k1:integer;

begin

if b then

begin

Canvas.Brush.Color := clRed;

canvas.Ellipse(x-10,y-10,x+10,y+10);

inc(i);

canvas.TextOut(x-3,y-6,inttostr(i));

Data[i].x1:=x;Data[i].y1:=y;

combobox1.items.Append(inttostr(i));

end

else

//risovanie peteli

if (x=x2) and (y=y2) then begin

for k:=1 to i do

if (sqr(X-data[k].x1)+sqr(Y-data[k].y1)<=100) then

begin

canvas.arc(data[k].x1,data[k].y1-30,data[k].x1+50,data[k].y1+30,

data[k].x1+5,data[k].y1+2,data[k].x1,data[k].y1);

break;end;

end

else

//--------------------------

for k:=1 to i do

if (sqr(X-data[k].x1)+sqr(Y-data[k].y1)<=100) then

begin

for k1:=1 to i do

if (sqr(x2-data[k1].x1)+sqr(y2-data[k1].y1)<=100) then begin

canvas.MoveTo(data[k1].x1,data[k1].y1);x2:=0;y2:=0;break;end;

canvas.Lineto(data[k].x1,data[k].y1);

matr[k1,k]:=1;matr[k,k1]:=1;

matr_edit[k1,k]:=1;matr_edit[k,k1]:=1;

matr[k,k]:=0;matr_edit[k,k]:=0;

Combobox1.visible:=true;

Label1.Visible:=true;

end;

end;

//*************************************************

procedure TForm1.FormActivate(Sender: TObject);

var j:integer;

begin

for i:=1 to 20 do

for j:=1 to 20 do

matr[i,j]:=0;

i:=0; x2:=0;y2:=0;

b1:=false;b2:=false; b4:=true;

combobox1.Items.Append('(None)');

Combobox1.visible:=false;

Label1.Visible:=false;

end;

//**provereaet esli vershina imeet kratnye riobra*********

function TForm1.Proverka(ind: byte): boolean;

var sum,i1,i2: byte;

begin

sum:=0;

for i1:=1 to i do

sum:=sum+matr[ind,i1];

if ((sum mod 2) =0) then

Proverka:=true else Proverka:=false;

end;

//*****delete vershinu********************************

procedure TForm1.Newselect(ind: byte);

var

ARect: TRect;

i1,i2:integer;

begin

with Image2.Canvas do

begin

CopyMode :=Whiteness;

ARect := Rect(0, 0, Image2.Width, Image2.Height);

CopyRect(ARect, Image2.Canvas, ARect);

CopyMode := cmSrcCopy;

//***************************

for i1:=1 to i do

for i2:=1 to i do

matr_edit[i1,i2]:=matr[i1,i2];

if proverka(ind) then

for i2:=1 to i do

begin

matr_edit[ind,i2]:=0;

matr_edit[i2,ind]:=0;

end;

if (proverka(ind)) then

begin

image2.Canvas.Brush.Color := clRed;

image2.canvas.pen.color:=clblack;

for i1:=1 to i do

for i2:=1 to i do

if matr_edit[i1,i2]=1 then

begin

image2.canvas.Ellipse(data[i1].x1-10,data[i1].y1-10,

data[i1].x1+10,data[i1].y1+10);

image2.canvas.TextOut(data[i1].x1-3,data[i1].y1-6,inttostr(i1));

image2.canvas.MoveTo(data[i1].x1,data[i1].y1);

image2.canvas.Lineto(data[i2].x1,data[i2].y1);

end;

end; end;end;

//----------------------------------------------------------

procedure TForm1.Graph;

var i1,i2:integer;

ARect: TRect;

begin

with Image2.Canvas do

begin

CopyMode :=Whiteness;

ARect := Rect(0, 0, Image2.Width, Image2.Height);

CopyRect(ARect, Image2.Canvas, ARect);

CopyMode := cmSrcCopy;

image2.Canvas.Brush.Color := clRed;

image2.canvas.pen.color:=clblack;

for i1:=1 to i do

for i2:=1 to i do

if matr[i1,i2]=1 then

begin

image2.canvas.Ellipse(data[i1].x1-10,data[i1].y1-10,

data[i1].x1+10,data[i1].y1+10);

image2.canvas.TextOut(data[i1].x1-3,data[i1].y1-6,inttostr(i1));

image2.canvas.MoveTo(data[i1].x1,data[i1].y1);

image2.canvas.Lineto(data[i2].x1,data[i2].y1);

end; end; end;

//****soedineam dve sosednie vershiny***********************

procedure TForm1.Duga(ind:byte);

var

v,i2,a1,d1,a2,d2,a,b: integer;

R:double;

s_1:array[1..2] of integer;

begin

v:=1;

if proverka(ind) then

for i2:=1 to i do

begin

if ((matr[ind,i2]=1) and (ind<>i2)) then

begin

s_1[v]:=i2;inc(v);

end;

if v=3 then

begin

a2:=data[s_1[1]].x1;d2:=data[s_1[1]].y1;

a1:=data[s_1[2]].x1;d1:=data[s_1[2]].y1;

a:=round((sqr(a1)+sqr(d1)-sqr(a2)-sqr(d2))/(2*(a1+d1-a2-d2)));

b:=a;

R:=sqrt(sqr(a2-a)+sqr(d2-b));

image2.canvas.pen.color:=clblue;

image2.Canvas.arc(round(a-R),round(a-R),round(a+R),round(a+R),a1,d1,a2,d2);

v:=1;

end;

end;end;

//*******vybor vershin************************************

procedure TForm1.ComboBox1Change(Sender: TObject);

begin

if combobox1.ItemIndex = 0 then

Graph

else

begin

newselect(combobox1.ItemIndex);

duga(combobox1.ItemIndex); end;

end;

end.

Вывод Целью моей дипломной работы была исследовать задачу на построение разреза в графе по вершине z. Был разработан алгоритм, который строит разрез по заданому графу. По данному алгоритму была написанна программа. Алгортм заключался в следующем: задается граф, по нем строится матрица смежности. В матрице суммируется строка и если при делении на два остаток от деления равен нулю, тогда данную вершину удаляют, а те вершины которые были смежные с ней соединяются между собой.

49

Характеристики

Список файлов реферата