Задача остовных деревьев в k–связном графе - реферат

Задача остовных деревьев в k–связном графе - реферат

Министерство Науки и Образования Республики Молдова Молдавский Муниципальный Институт Кафедра Информатики и Дискретной Оптимизации Дипломная работа:

«Задача остовных деревьев в k–связном графе»

работу выполнил

ст. V курса гр.52MI

Жуков В.

Работу приняла:

Dr.физ–мат. наук

Присэкару В.К.

Кишинев–2002

Содержание:

Введение………………………………………………………………………….2

Глава I Главные определения………………………………………………….4

§1 Главные определения теории графов……………………………………...4

§2 Матрицы Задача остовных деревьев в k–связном графе - реферат смежности и инцидентности……………………………………..10

§3 Деревья………………………………………………………………………..13

Глава II Связность ………………………………………………………………18

§4 Вершинная связность и реберная вязность…………………………………18

§5 Двусвязные графы…………………………………………………………....22

§6 Аксиома Менгера………………………………………………………….….32

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

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

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

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

§9 Текст программки……….………………………………………………….…42

Вывод……………………………………………………………………………..51


Введение

Начало теории графов как математической дисциплины было положено Эйлером Задача остовных деревьев в k–связном графе - реферат в его именитом рассуждение о Кенигсбергских мостах. Но эта статья Эйлера 1736 года была единственной в течение практически 100 лет. Энтузиазм к дилеммам теории графов возродился около середины прошедшего столетия и был сосредоточен приемущественно в Великобритании. Имелось много обстоятельств для такового оживления исследования графов. Естественные науки оказали свое воздействие Задача остовных деревьев в k–связном графе - реферат на это благодаря исследованиям электронных цепей, моделей кристаллов и структур молекул. Развитие формальной логики привело к исследованию бинарных отношений в форме графов. Огромное число фаворитных головоломок подавалось формулировкам конкретно в определениях графов, и это приводило к осознанию, что многие задачки такового рода содержат некое математическое ядро, значимость которого выходит за Задача остовных деревьев в k–связном графе - реферат рамки определенного вопроса. Более именитая посреди этих задач–неувязка 4 красок, в первый раз поставленная перед математиками Де Морганом около 1850 года. Никакая неувязка не вызывала настолько бессчетных и смышленых работ в области теории графов. Благодаря собственной обычной формулировке и раздражающей неуловимости она до сего времени остается массивным стимулом исследовательских Задача остовных деревьев в k–связном графе - реферат работ разных параметров графов.

Истинное столетие было очевидцем неуклонного развития теории графов, которая за последние 10 – 20 лет вступила в новый период насыщенных разработок. В этом процессе очевидно приметно воздействие запросов новых областей: теории игр и программирования, теории передачи сообщений, электронных сетей и контактных цепей, также заморочек психологии и биологии.

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

По теории графов имеется сильно мало книжек; основной была книжка Д. Кёнига Задача остовных деревьев в k–связном графе - реферат (1936), которая для собственного времени давала превосходнейшее введение в предмет. Достаточно удивительно, что таких книжек на британском языке до сего времени не было, невзирая на то, что многие важные результаты были получены южноамериканскими и английскими создателями.


Глава I

Главные понятия

§1 Определения.

Предметом первых задач в теории графов были конфигурации, состоящие из точек и Задача остовных деревьев в k–связном графе - реферат соединяющих их линий. В этих рассмотрениях было несущественно, прямые ли это полосы либо же они являются криволинейными непрерывными дугами, соединяющими две концевые точки, где размещены эти полосы, являются ли они длинноватыми либо маленькими. Значительно только то, что они соединяют две данные точки.

Это приводит к определению графа Задача остовных деревьев в k–связном графе - реферат как абстрактного математического понятия. Рассматривая огромное количество V , состоящее из соединенных неким образом точек. Назовем V обилием вершин и элементы v V –верхушками . Граф

G = G ( V ) (1.1)

c обилием вершин V есть некое семейство сочетаний, либо пар вида

E=(a, b), a,b V (1.2)

указывающие, какие верхушки являются примыкающими. В Задача остовных деревьев в k–связном графе - реферат согласовании с геометрическим представлением графа любая определенная пара (1.2) именуется ребром графа; верхушки a и b именуются концевыми точками , либо концами ребра.

Можно использовать и другой подход. Если даны два огромного количества V 1 и V 2 то можно образовать огромное количество всех пар

(v1 ,v2 ), v1 V1 , v2 V2 .

Это огромное количество пар Задача остовных деревьев в k–связном графе - реферат именуется произведением и обозначается через V 1 ´ V 2 . В нашем случае любая пара вершин ( a , b ) есть элемент произведения V ´ V . Таким макаром можно сказать, что граф G из (1.1) с данными ребрами (1.2) есть некое подмножество произведения V ´ V .

Это определение графа должно быть дополнено в Задача остовных деревьев в k–связном графе - реферат одном принципиальном отношении. В определении ребра (1.2) можно принимать либо не принимать во внимание порядок расположения 2-ух его концов. Если этот порядок несуществен, т.е. если

E=(a, b)=(b, a),

то молвят, что Е есть неориентированное ребро ; если же этот порядок существен, то Е именуется нацеленным ребром . В последнем случае Задача остовных деревьев в k–связном графе - реферат а именуется также исходной верхушкой , а b –конечной верхушкой ребра Е . Можно также гласить, что Е есть ребро, выходящее из верхушки а (отходящее от верхушки а , исходящее из верхушки а ) и входящее в верхушку b (подходящее к верхушке b , заходящее в верхушку b ). Как в случае нацеленного, так и в случае Задача остовных деревьев в k–связном графе - реферат неориентированного ребра молвят, что ребро Е из (1.2) инцидентно верхушкам a и b , также что а и b инцидентны Е .

В приложениях граф обычно интерпретируется как сеть , в какой верхушками G являются узлы . Два узла a и b соединяются непрерывной кривой (а именно прямолинейны отрезком) и тогда только Задача остовных деревьев в k–связном графе - реферат тогда, когда имеется пара (1.2). На рисунках узлы будут обозначаться малеханькими кружками, а ориентация, если необходимо, – стрелкой на представляющей ребро кривой (рис. 1.1).

Граф именуется неориентированным , если каждое его ребро не ориентированно, и нацеленным , если ориентированны все его ребра.

На рис.1.2 приведены примеры неориентированных графов. На рис 1.3 изображены ориентированны графы.

В ряде Задача остовных деревьев в k–связном графе - реферат всевозможных случаев естественно рассматривать смешанные графы , имеющие как направленные, так неориентированные ребра. К примеру, план городка

можно рассматривать как граф, в каком ребра представляют улицы, а верхушки – перекрестки; при всем этом по одним улицам может допускаться только однобокое движение, тогда и на соответственных ребрах вводится ориентация; по другим улицам Задача остовных деревьев в k–связном графе - реферат движение двухстороннее, и на соответственных ребрах уже никакой ориентации не вводится.

Мы уже отмечали, что при фактическом изображении графа имеется большая свобода в размещении вершин и в выборе формы соединяющих их дуг. Потому возможно окажется, что один и тот же граф представляется совершенно разными чертежами. Будем гласить, что два графа Задача остовных деревьев в k–связном графе - реферат G и G ' изоморфны , если существует такое взаимно однозначное соответствие меж огромными количествами их вершин V и V ’ , что верхушки соединены ребрами в одном из графов в том и только том случае, когда надлежащие им верхушки соединены в другом графе. Если ребра нацелены, то их направления также должны соответствовать друг дружке Задача остовных деревьев в k–связном графе - реферат. На рис 1.2 приведены примеры изоморфных графов, образованных ребрами и верхушками правильных полиэдров.

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

учесть только неизолированные верхушки. Граф, состоящий только из изолированных вершин, именуется нуль–графом и может быть обозначен через 0. другим принципиальным Задача остовных деревьев в k–связном графе - реферат случаем является (неориентированный) полный граф

U=U(V) , (1.3)

ребрами которого являются различные пары (1.2) для 2-ух разных вершин a и b из V . На рис. 1.4 даны схемы полных графов для множеств вершин из 4 и из 5 частей.

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

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

Во–первых, можно получить ребра, у каких обе концевые точки совпадают:

L=(a, a). (1.4)

Такое ребро (1.4) будет называться петлей Задача остовных деревьев в k–связном графе - реферат . При изображении графа петля будет представляться замкнутой дугой, возвращающейся в верхушку а и не проходящей через другие верхушки (рис 1.5). Петля обычно считается неориентированной. Можно расширить полный граф U в (1.3) до полного графа с петлями U 0 , добавляя

петлю в каждой верхушке, так что ребрами U 0 являются все пары (1.2), где допускается и Задача остовных деревьев в k–связном графе - реферат a = b .

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

Ei =(a, b)i , (1.5)

как это изображено на рис. 1.6. Для нацеленного графа две верхушки a и b могут соединяться несколькими ребрами в каждом из направлений:

Ei =(a, b)i , =(a, b)j ,

(рис. 1.7).

Чтоб Задача остовных деревьев в k–связном графе - реферат проиллюстрировать случай, для которого эти понятия оказываются естественными, разглядим какое–или командное соревнование, к примеру турнирную таблицу лиги бейсбола. Верхушками соответственного графа

являются команды. Пара команд А и В связывается ребром всякий раз, когда они сыграли. Если А выиграла у В , то это ребро будем ориентировать от А к Задача остовных деревьев в k–связном графе - реферат В . а если В выиграла у А , то обратном направлении; в случае ничьей ребро будет неориентированным.

Для каждого графа G существует оборотный граф G * , получаемый конфигурацией ориентации каждого из ребер G на обратную. Для

каждого нацеленного графа существует также соотнесенный неориентированный граф Gu , ребрами которого являются ребра G , но уже Задача остовных деревьев в k–связном графе - реферат без ориентаций. Время от времени комфортно перевоплотить неориентированный граф G в направленный граф Gd с помощью процесса удвоения , состоящего в подмене каждого ребра G парой с теми же концами и приписывании им обратных ориентаций.

Граф именуется плоским , если он может быть изображен на плоскости так что все Задача остовных деревьев в k–связном графе - реферат скрещения ребер являются верхушками G . Граф на рис 1.8а тонкий, а на рис 1.8б неплоский.

§2. Матрицы смежности и инцидентности.

В § 1 мы обусловили ребро Е (1.2) графа G (1.1) как элемент либо точку ( a , b ) в произведении V ´ V . Как обычно, элементы этого произведения можно представить в виде клеток квадратной таблицы М Задача остовных деревьев в k–связном графе - реферат с элементами огромного количества V в качестве координат по двум осям (рис 2.1).

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

Если G имеет кратные ребра, то числа 0 и Задача остовных деревьев в k–связном графе - реферат 1 в клеточках ( a , b ) можно поменять кратностями r ( a , b ) ребер, соединяющих а и b . Это дает описание графа G матрицей с целыми неориентированными элементами. Назад, неважно какая такая матрица может быть интерпретирована как граф, так что любые результаты для графов могут быть сформулированы как характеристики таких матриц.

Произнесенное приводит Задача остовных деревьев в k–связном графе - реферат к предстоящему расширению понятия графа, использующему уже все конечные либо нескончаемые матрицы, элементами которых являются вещественные неотрицательные числа. Такие матрицы встречаются в разных областях арифметики. К примеру, стохастические матрицы – в теории вероятностей и в теоретической физике. Где рассматриваемая система имеет некое огромное количество V вероятных состояний, и неважно какая Задача остовных деревьев в k–связном графе - реферат пара состояний ( a , b ) связывается некой вероятностью перехода r ( a , b ). Другим примером является граф, представляющий схему дорог, в каком r ( a , b ) значит соответственное расстояние меж а и b .

Графы могут быть также описаны матрицами другого вида. Всякий граф состоит из объектов 2-ух типов–вершин и ребер. Можно Задача остовных деревьев в k–связном графе - реферат выстроить матицу M 1 ( G ), строчки которой соответствуют верхушкам, а столбцы–ребрам. На месте (а, Е) в этой матрице поместим значение e =1 , если а –исходная верхушка ребра Е, значение e =-1 , если а –конечная верхушка, и e =0 , если а не инцидентно Е. Если G –неориентированный граф, то можно использовать только Задача остовных деревьев в k–связном графе - реферат значения e =1 и e =0 . Эта матрица M 1 ( G ) именуется матрицей инцидентности графа G .

Введем, в конце концов, матрицу смежности ребер I ( G ), в какой и строчки и столбцы отвечают ребрам G . Для простоты представим. Что G не имеет петель, а ребра неориентированные и однократные. На месте ( E , E Задача остовных деревьев в k–связном графе - реферат ’ ) в I ( G ) поместим e =1 , если Е и Е’ –разные ребра с общим концом, и e =0 , если Е=Е’ либо если они не имеют общего конца. Таким макаром, I ( G )– квадратная матрица, определяемая графом G .

Можно встать и на другую точку зрения и рассматривать I ( G ) как матрицу смежности вершин для нового Задача остовных деревьев в k–связном графе - реферат графа, также обозначаемого через I ( G ), верхушками которого являются ребра Е графа G , а ребрами–пары ( E , E ’) с e =1 . Назовем I ( G ) графом смежности ребер либо смежности графом для G . Существование такового графа, в каком бывшие ребра становятся верхушками и напротив, разъясняет двойственность меж верхушками и ребрами, встречающуюся Задача остовных деревьев в k–связном графе - реферат в неких вопросах теории графов.

Фактическое построение смежности графа I ( G ) по чертежу графа G просто. На каждом ребре Е избираем фиксированную точку еЕ , к примеру середину Е . Пару таких вершин (е, е’) соединяем новым ребром, принадлежащим I ( G ), и тогда только тогда, когда надлежащие ребра Е и Е Задача остовных деревьев в k–связном графе - реферат’ имеют общую верхушку в G .

Рис. 2.2 дает это построение для графа тетраэдра; смежностным графом для него является граф октаэдра.

Представим, то в верхушке е сходится r (е) ребер Е=(е, е’) из G . Тогда в I ( G ) середина eE ребра Е соединяется ребрами с r (е Задача остовных деревьев в k–связном графе - реферат)–1 серединами других ребер из G , имеющих конец в е . Таким макаром, вI ( G ) эти новые ребра образуют новый граф U ( e ) сr (е) верхушками. В I ( G ) верхушка eE соединяется ребрами также с r (е’)–1 серединами других ребер из G, из имеющих конец в e’, и эти новые ребра образуют Задача остовных деревьев в k–связном графе - реферат другой полный граф U ( e ’). Два графа U ( e ) и U ( e ’) имеют ровно одну общую верхушку, конкретно верхушку eE , определяемую единственным ребром Е , соединяющим e и e ’ . Таким макаром, I ( G ) имеет такое непересекающееся по ребрам разложение

I ( G )= 2.1

На полные графы U ( e ) с r (е) верхушками, что Задача остовных деревьев в k–связном графе - реферат U ( e ) имеет единственную общую верхушку с каждым из r (е) других полных графов U ( e ’). Исключение составляет случай, когда ( e , e ’)– единственное ребро в e ’ , т.е.r (е’)=1. Тогда не существует графа. U ( e ’).

Представим, что, напротив, для графа G 1 существует такое разложение (2.1) на полные графы, что пара ( U Задача остовных деревьев в k–связном графе - реферат ( e ), U ( e ’)) имеет менее одной общей верхушки. Тогда G1 можно рассматривать как смежностный граф G 1 = I ( G ) некого графа G , считая, что каждое U ( e ) имеет r 1 r (е) общих вершин с другими U ( e ’). Каждому U(e) поставим в соответствие одну верхушку e и Задача остовных деревьев в k–связном графе - реферат соединим e и e ’ ребром в G и тогда только тогда, когда U ( e ) и U ( e ’) имеют общую верхушку. К этим ребрам добавим r (е)– r 1 ребер ( e , e ’’), идущих к новым верхушкам e ’’ , в каких существует только одно это ребро.

§3 Деревья

Деревом именуется связный граф, не содержащий циклов. Хоть Задача остовных деревьев в k–связном графе - реферат какой граф без циклов именуется ациклическим (либо) лесом . Таким макаром, компонентами леса являются деревья. На рис.12 изображены все деревья шестого порядка.

Существует несколько вариантов определения дерева; некие из их отражены в последующей аксиоме.

Аксиома 3.1 Для графа последующие утверждения эквивалентны:

1) G – дерево;

2) G – связный граф и m = n -1;

3) G – ациклический граф Задача остовных деревьев в k–связном графе - реферат и m = n -1;

4) любые две несовпадающие верхушки графа соединяет единственная обычная цепь;

5) G – ациклический граф, владеющий тем свойством, что если каку–или пару его несмежных вершин соединить ребром, то приобретенный граф будет содержать ровно один цикл.

1) 2) Воспользуемся индукцией по n . При n =1 утверждение трививально. Пусть n >1 , е EG . В Задача остовных деревьев в k–связном графе - реферат дереве G нет циклов, как следует, согласно лемме 4.1, граф G – е имеет ровно две составляющие Т1 и Т2 ,

любая из которых есть дерево. Пусть дерево Ti является ( ni , mi ) – графом, i =1, 2 . По индуктивному предположению правильно равенство

mi = ni -1 . (1)

Дальше имеем

m=m1 +m2 +1=(n1 -1)+(n2 -1)+1=(n1 +n2 )-1=n Задача остовных деревьев в k–связном графе - реферат-1 .

2) 3) Граф G связен и m = n -1 . Необходимо обосновать, что в G нет циклов. Пусть, напротив, в графе G есть цикл и пусть ребро е–ребро этого цикла. Тогда граф G – е связен (лемма 4.8) и имеет n -2 ребра, что противоречит аксиоме 4.9. следовадельно, G –ациклический граф.

3) 4) Пусть к –число компонент графа G . Пусть Задача остовных деревьев в k–связном графе - реферат, дальше, компонента Т i является ( ni , mi )– графом. Потому что Т i –дерево, то правильно равенство (1). Сейчас имеем

n -1= m = m 1 + m 2 +…+ mk =( n 1 -1)+( n 2 -1)+…+( nk -1)=( n 1 +…+ nk )- k = n - k ;

т.е. к=1 . Итак, G –связный граф и поэтому любые несовпадающие верхушки u и v соединены в нем просой Задача остовных деревьев в k–связном графе - реферат цепью. Если б в G были две несовпадающие обыкновенные ( u , v ) –цепи, то согласно утверждению 4.3 их объединение содержало бы цикл. Как следует, каждые две верхушки соединены единственной обычный цепью.

4) 5) пара несовпадающих вершин, принадлежащих одному циклу, соединена само мало 2-мя ординарными цепами. Как следует, граф G ациклический. Пусть Задача остовных деревьев в k–связном графе - реферат u и v –две его нечмежные верхушки. Присоединим к графу G ребро e = uv . В G есть обычная ( u , v )– цепь, которая в G + e дополняется до цикла. В силу утверждения 4.4 этот цикл единственный.

5) 1) необходимо докакзать, что граф G связен. Если б верхушки u и v принадлежали различным компонентам графа G Задача остовных деревьев в k–связном графе - реферат , то граф G + uv не имел бы циклов,что потиворечит утверждению 5). Итак, G связен и поэтому является деревом. Подтверждено.

Следствие 3.2 . В любом дереве порядка n 2 имеется неменее 2-ух концевых вершин .

Пусть

d 1 , d 2 , …, dn (2)

–степенная последовательность дерева. Тогда

(лемма о рукопожатиях) и все di >0 . Как следует, хотя Задача остовных деревьев в k–связном графе - реферат бы два числа из последовательности (2) равны 1.

Пусть Н –остовный подграф поизвольного гафа G . Если на каждой области связности графа G графом Н порождает дерево, то Н именуется остовом (либо каркасом ) графа G . разумеется, что в каждом графе существует остов: разрушая в каждой компоненте циклы, т.е. удаляя излишние ребра Задача остовных деревьев в k–связном графе - реферат, придем к остову. Остов в графе просто отыскать при помощи поиска в ширину.

Следствие 3.3. число ребер случайного графа G , которые нужно удалить для получения остова, не находится в зависимости от последовательности их удаления и равно m ( G )-| G |+ k ( G ), где m ( G ) и k ( G )–число ребер и число компонент Задача остовных деревьев в k–связном графе - реферат графа G соответственно .

Если ( n 1 , m 1 )– граф Н является одной из компонент графа G , то для перевоплощения ее в остове дерево необходимо удалить m 1 -( n 1 -1) подходящих ребер. Суммируя по всем k (G) компонентам, получим требуемое.

Число g ( G )= m ( G )-| G |+ k ( G ) именуется повторяющимся рангом (либо цикломатическим числом ) графа Задача остовных деревьев в k–связном графе - реферат G . число ребер остова графа G именуется коциклическим рангом графа G . таким макаром.

Явны три следствия 13.4–13.6.

Следствие 3.4. Граф G является лесом и тогда только тогда, когда g ( G )=0 .

Следствие 3.5. граф G имеет единственный цикл и тогда только тогда, когда g ( G )=1 .

Следствие 3.6. Граф, в каком число ребер не меньше Задача остовных деревьев в k–связном графе - реферат, чем число вершин, содержит цикл .

Утверждение 3.7 . Если S и Т –два остова графа G , то для хоть какого ребра е1 графа S существует такое ребро е2 графа Т, что граф также является остовом.

Подтверждение

Не ограничивая общности, будем считать граф G связным. Граф имеет ровно две области связности; пусть Задача остовных деревьев в k–связном графе - реферат это будут А и В . Так как граф Т связен, то в нем существует ребро е2 , один из концов которого заходит в А , а другой – в В . Граф Н= S - e 1+ e 2 связен и число ребер в нем такое же, как в дереве S . как следует, он сам является Задача остовных деревьев в k–связном графе - реферат деревом. Итак, Н –остов графа G . Подтверждено.

Аксиома 13.8. Центр хоть какого дерева состоит из одной либо из 2-ух смежных вершин.

Подтверждение

Разумеется, что концевые верхушки дерева Т являются центральными только для T=K1 либо T=K2 .

Пусть Т дерево порядка n>2. Удалив из Т все концевые, получим дерево Т Задача остовных деревьев в k–связном графе - реферат’. Разумеется, что эксцентриситет Т на единицу меньше эксцентриситета дерева Т и что центры деревьев Т и Т совпадают. Дальше подтверждение легео проводится индукцией по числу веншин.Подтверждено.


Глава II

Связность

Связный граф был определен как граф, у которого любые две верхушки соединены цепью. Так, оба графа К n и Задача остовных деревьев в k–связном графе - реферат Cn связны, но интуитивно ясно, что при n>3 граф Kn «сильнее» связен, чем Cn . В этой главе вводится и исследуются понятия, характеризующие степень связности графа.

§4 Вершинная связность и реберная связность.

До того как ввести понятия вершинной и реберной связности, разглядим одну математическую модель, возникающую, а именно, при проектировании Задача остовных деревьев в k–связном графе - реферат и анализе сетей ЭВМ. Имеется сеть, состоящая из центров хранения и переработки инфы. Некие пары центров соединены каналами. Обмен информацией меж хоть какими 2-мя центрами осуществляется или конкретно по соединяющему их каналу, если он есть, или через другие каналы и центры. Сеть считается исправной, если любая пара Задача остовных деревьев в k–связном графе - реферат центров в состоянии обмениваться информацией. Таковой сети естественно сравнить граф: верхушки–центры, ребра–каналы сети. Тогда исправной сети будет соответствовать связный граф. Принципиальным понятием является надёжность (живучесть) сети, под которой обычно предполагают способность сети работать при выходе из строя 1-го либо нескольких центров либо (и) каналов. Ясно, что наименее надежной следует Задача остовных деревьев в k–связном графе - реферат считать ту сеть, исправность которой нарушается при повреждении наименьшего количества частей. Оказывается, надежность сети можно определять на базе вводимых ниже определений.

Числом вершин связности (либо просто числом связности ) ( G ) графа G именуется меньшее число вершин, удаление которых приводит к бессвязному либо одновершинному графу.

Так, к примеру, ( K Задача остовных деревьев в k–связном графе - реферат 1 )=0, ( Kn )= n –1, ( Cn )=2.

Это полностью согласуется с интуитивным представлением том, что при n>3 граф Kn посильнее связен, чем Cn .

Граф G , представленный на рис. 4.1 связен, но его связность можно нарушить, удалив верхушку 4. Потому ( G )=1 . Если же попробовать нарушить связность этого графа методом удаления ребер (а не вершин), то придется удалить Задача остовных деревьев в k–связном графе - реферат более 3-х ребер. К примеру, G распадается на две составляющие

при удалении ребер {4,5}, {4,6}, {4,7} . Чтоб учитывать это событие, введем очередное определение.

Пусть G –граф порядка n>1. Числом реберной связности ( G ) графа G назовем меньшее число ребер, удаление которых приводит к бессвязному графу. Число реберной связности графа будем считать равным нулю, если Задача остовных деревьев в k–связном графе - реферат этот граф одновершинный.

В качестве иллюстрации опять обратимся к графу G на рис. 4.1 Тут ( G )=3 и, как следует, (G)> (G). Ниже будет показано, что обратное неравенство нереально ни для какого графа.

Определим некие элементы графа, играющие необыкновенную роль в последующих рассмотрениях.

Верхушка v графа G именуется точкой сочленения Задача остовных деревьев в k–связном графе - реферат ( либо разделяющей верхушкой) , если граф G –v имеет больше компонент, чем G . А именно, если G связен и v – точка сочленения, то G –v не связен. Аналогично ребро графа именуется мостом , если его удаление наращивает число компонент.

Таким макаром, точки сочленения и мосты – это собственного рода «узкие места» графа. Граф Задача остовных деревьев в k–связном графе - реферат, изображенный на рис. 4.2, имеет три точки сочленения a , b , c и один мост ab .

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

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

Если ( G ) – малая степень вершин графа G , то разумеется, что ( G ) ( G ) , так как удаление всех ребер, инцидентных данной верхушке, приводит к повышению числа компонент графа.

Выясним сейчас соотношения меж Задача остовных деревьев в k–связном графе - реферат числами ( G ) и ( G ) . Если граф G не связен либо имеет мост, то разумеется, что ( G )= ( G ) . Пусть G – связный граф без мостов. Выберем в этом графе огромное количество Е1 , состоящее из = ( G ) ребер, удаление которых приводит к бессвязному графу. Пусть E 2 E 1 , | E 2 |= –1 . Граф G – E 2 связен и Задача остовных деревьев в k–связном графе - реферат имеет мост, который обозначим через uv . Для каждого ребра из огромного количества Е2 выберем какую–или инцидентную ему верхушку, хорошую от u и v . Удалим сейчас избранные верхушки из графа. Этим самым будут удалены, в числе иных, и все ребра, входящие в Е2 . Если оставшийся граф не связен Задача остовных деревьев в k–связном графе - реферат, то = ( G ) < . Если же он связен, то ребро uv является мостом. Потому удаление одной из вершин u либо v приводит к бессвязному либо одновершинному графу, а это значит, что .

Таким макаром, подтверждена

Аксиома 4.1 : Для хоть какого графа G верны неравенства

( G ) .

Граф именуется к–связным , если , и реберно–к–связным , если Задача остовных деревьев в k–связном графе - реферат . Таким макаром, хороший от К1 граф 1–связен (односвязен) и тогда только тогда, когда он связен, а 2–связные (двусвязные) графы – это связные графы без точек сочленения, не являющиеся одновершинными.

Граф G , изображенный на рис. 4.1 1–связен и реберно–3–связен. Просто созидать, что этот граф содержит подграфы, являющиеся «более связными Задача остовных деревьев в k–связном графе - реферат», чем сам граф. Такой, к примеру, подграф, порожденный обилием вершин {1, 2, 3, 4, 8} . Он 3–связен.

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

Это определение иллюстрируется на рис. 4.3. На этом рисунке граф G 1 имеет две Задача остовных деревьев в k–связном графе - реферат 2–составляющие, а G 2 –две 3–составляющие. Сами графы G 1 и G 2

являются 1–компонентами графа G 1 G 2 . просто увидеть, что 2–составляющие графа G 1 имеют одну огромную верхушку, а 3–составляющие графа G 2 –две общие верхушки. Последующая аксиома указывает, что это событие не случаем.

Аксиома 4.2 : Две разные к–составляющие графа имеют менее чем к Задача остовных деревьев в k–связном графе - реферат–1 общих вершин .

Подтверждение

Пусть G 1 и G 2 –разные k –составляющие графа G и VG 1 VG 2 = X . Представим, что | X | k , и докажем, что тогда граф G 1 G 2 должен быть к–связным. Для этого в этом случае довольно показать, что он остается связным после удаления всех k –1 вершин, т.е. Y Задача остовных деревьев в k–связном графе - реферат V ( G 1 G 2 ), | Y |= k -1 , то граф ( G 1 G 2 ) – Y связен. Положим

Yi =(VGi \X) Y, i=1,2, Y3 =X Y.

Ясно, что

|Yi | k–1, i=1,2,3, Y=Y1 Y2 Y3 .

Так как

| Yi Y 3 | k –1, i =1,2,

и графы G 1 и G 2 k –связны, то графы

Hi =Gi –(Yi Y3 ), i Задача остовных деревьев в k–связном графе - реферат=1,2,

связны. Потому что по предложению | X | k , то X \ Y 3 Ø , т.е. связны графы H 1 и H 2 имеют хотя бы одну общую верхушку. Как следует, связен граф H 1 H 2 =( G 1 G 2 )– Y . Последнее значит, что граф G 1 G 2 k –связен. Потому, вопреки предположению, ни G 1 не являются k –компонентами графа Задача остовных деревьев в k–связном графе - реферат G .

§5 Двусвязные графы

Случаям, когда k =2 либо k =3 , в теории графов отведена особенная роль. Это разъясняется последующими причинами. Во–первых. 2– и 3–связные графы бытуют в почти всех теоретических и прикладных вопросах, а именно, ряд задач довольно уметь решать для 2–связных компонент. Во–вторых, при к=3 и, в особенности, при к=2 удается Задача остовных деревьев в k–связном графе - реферат дать в некой степени обозримое описание соответственных графов.

Разглядим сначала некие обыкновенные характеристики 2–связных графов, вытекающие конкретно из определений:

1) степени вершин 2–связного графа больше единицы;

2) если графы G 1 и G 2 2–связны и имеют более 2-ух общих вершин, то граф G 1 G 2 также 2–связен;

3) если граф G Задача остовных деревьев в k–связном графе - реферат 2–связен и Р–обычная цепь, соединяющая две его верхушки, то граф G P также 2–связен;

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

Этими качествами мы будем воспользоваться без каких–или пояснений и дополнительных ссылок на их.

Аксиома 5.1 пусть G –связный граф и | G |>2. Тогда последующие утверждения эквивалентны:

1) граф 2–связен;

2) любые две верхушки графа принадлежат обычному циклу;

3) неважно какая верхушка и хоть какое ребро принадлежат обычному циклу Задача остовных деревьев в k–связном графе - реферат;

4) любые два ребра принадлежат обычному циклу;

5) для всех 2-ух вершин a и bи хоть какого ребра е существует обычная ( a , b )–цепь, содержащая е;

6) для всех 3-х вершин a , b , c существует обычная ( a , b )–цепь, проходящая через с.

1) 2). Пусть a и b –две верхушки графа G . Разглядим огромное количество всех Задача остовных деревьев в k–связном графе - реферат обычных циклов графа G , содержащих а . Обозначим через U огромное количество всех вершин, входящих в эти циклы. Ясно, что U Ø . Вправду, обычный цикл, содержащий а , можно получить, соединить два ребра ax и ay ( x ≠ y ) и ординарную ( x , y ) –цепь, не проходящую через а (существующую согласно свойству 4)). Представим Задача остовных деревьев в k–связном графе - реферат, что b U , и положим =VG \ U . Так как граф G связен, то в нем найдется такое ребро zt , что z U , t (рис. 5.1). Пусть S –обычный цикл, содержащий a и z . Потому что G – 2 -связный граф, то в нем имеется обычная ( a , t ) -цепь P , не содержащая z . Пусть Задача остовных деревьев в k–связном графе - реферат v – 1-ая, считая от t , верхушка, входящая в S , т.е. ( t , v ) -подцепь цепи P не имеет с S общих вершин, хороших от v . Сейчас просто выстроить обычной цикл, содержащий a и t . Он выходит объединением ( v , z ) - цепи, проходящей через а и являющейся частью Задача остовных деревьев в k–связном графе - реферат S , с ребром zt и ( t , v ) -подцепью цепи Р (на рис. 5.1 этот цикл показан пунктирной линией). Как следует, t ; но это противоречит выбору ребра zt . Таким макаром, =Ø, т.е. a и b лежат на общем ординарном цикле.

2) 3). Пусть а–верхушка и zt –ребро графа G . По условию G Задача остовных деревьев в k–связном графе - реферат содержит цикл S , проходящий через верхушки a и z . Не теряя общности будем считать, что zt S . Если при всем этом окажется, что S проходит через верхушку t , то требуемый цикл строится естественным образом. Пусть S не проходит через t . Тогда разглядим обычной цикл S ' , проходящий через верхушки t и a Задача остовных деревьев в k–связном графе - реферат . Таковой цикл, по условию, существует. Частью этого цикла является обычная цепь Р , соединяющая t с некой верхушкой v S . Цепь Р можно избрать так, чтоб

VP VS ={ v } . разыскиваемый цикл сейчас строится точно так же, как в прошлом пт.

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

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

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

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

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

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

Наибольшие относительное включения элементы Задача остовных деревьев в k–связном графе - реферат огромного количества связных подграфов графа G , не имеющих точек сочленения, именуются его блоками. Таким макаром, каждый блок графа или 2–связен, или совпадает с К2 либо К1 (граф К1 – блок и тогда только тогда, когда он является связной компонентой). Связный граф без точек сочленения также именуют блоком.

Огромное Задача остовных деревьев в k–связном графе - реферат количество вершин блока будем именовать блоковым обилием.

К примеру, граф, изображенный на рис. 5.2, содержит 5 блоков Bi ( i =1,2,3,4,5) (они обведены пунктирными линиями). Посреди этих блоков В1 , В2 и В3 –2-связные графы, а любой из 2-ух оставшихся является ребром.

Утверждение 5.2. Любые два блока графа имеют менее одной общей верхушки. А именно Задача остовных деревьев в k–связном графе - реферат, всякое ребро графа заходит исключительно в один его блок.

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

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

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

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

Утверждение 5.5. Если граф G связен Задача остовных деревьев в k–связном графе - реферат, то bc ( G )–дерево.

Подтверждение:

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

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

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

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

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

На рис. 5.4 граф G имеет 5 листов L 1 , L 2 , L 3 , L 4 , L 5 и 4 моста, а граф G ' указывает, как связаны меж собой листы графа G .

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

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

v1 VH, vk VH, vi VH, i=

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

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

Подтверждение

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

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

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

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

Подтверждение

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

1) если а – висящая верхушка графа Guv Задача остовных деревьев в k–связном графе - реферат , то av EG , au EG ;

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

3) всякий блок графа Guv , имеющий ровно две точки сочленения и хороший от ребра, содержит такую верхушку l Задача остовных деревьев в k–связном графе - реферат, не являющуюся точкой сочленения графа Guv , что либо ul EG .

Обозначим через Buv наибольший по числу вершин блок графа Guv , а через tuv – число вершин в этом блоке . Сейчас выберем ребро uv так, чтоб число tuv было большим.

Покажем, что в данном случае tuv 3 . Пусть tuv =2 и а – висящая верхушка графа Задача остовных деревьев в k–связном графе - реферат Guv (являющегося деревом). Потому что n 5 , то существует ребро cd EGuv . Из характеристики 1) вытекает, что в графе Gcd существует цикл ( u , a , v , u ) , т.е. tcd > tuv . Получено противоречие, как следует, tuv 3 .

Через Duv обозначим bc -дерево графа Guv и разглядим последующие случаи.

1. Дерево Duv не Задача остовных деревьев в k–связном графе - реферат является цепью. Выберем в этом дереве цепь, соединяющую пару висящих вершин и проходящую через верхушку, подобающую блоку Buv . Этой цепи соответствует последовательность B1 ,…, Bp блоков графа Guv , посреди которых содержится блок Buv , при этом блоки B1 и Bp являются висящими (рис. 5.6).

Пусть B' – случайный висящий блок графа Guv , хороший от B Задача остовных деревьев в k–связном графе - реферат1 и Bp . Из параметров 1) и 2) вытекает существование таких хороших от точек сочленения графа Guv вершин a VB1 , b VBp , c VB', uc EG, va EG, vb EG . Тогда в графе Guc верхушки огромного количества входят в один блок и, как следует, tuv < tuc . Последнее противоречит выбору ребра uv Задача остовных деревьев в k–связном графе - реферат .

2. Дерево Duv –цепь и Buv –блок графа Guv , не являющийся висящим. Пусть B 1 ,…, Bp – последовательность всех блоков графа G , при этом блоки B 1 и Bp –висящие, Bi Bi +1 Ø ( i = ), Buv = Bk (1< k < p ) (рис. 5.7). Cогласно свойству 3) найдется верхушка b VBuv хорошая от точек сочленения графа Guv , смежная с u Задача остовных деревьев в k–связном графе - реферат либо с v . Пусть ub EG . Согласно свойствам 1) и 2)

существует такие хорошие от точек сочленения графа Guv верхушки a VB 1 , c VBp , чтоua EG , vc EG . Просто созидать, что в графе Gvc имеется блок, содержащий все верхушки огромного количества . Потому tvc > tuv , и опять получаем противоречие.

3. Дерево Duv – цепь и Buv Задача остовных деревьев в k–связном графе - реферат – висячий блок графа Guv . Если граф Guv содержит такое ребро xy, что VBuv { x , y }=Ø , то, используя свойство 2), просто показать, что в графе Gxy есть блок, содержащий огромное количество вершин VBuv { x , y } , а, означает tuv < txy . Потому что Buv – висящий блок графа

Guv , то последнее значит Задача остовных деревьев в k–связном графе - реферат, что граф Guv состоит из блока Buv и ребер ab 1 , ab 2 ,… abl (рис 5.8). Из 3–связности графа G следует, что граф G – а не имеет точек сочленения. Так как в графе G – a верхушка b 1 смежна только с верхушками u и v , auv EG , то граф также не имеет точек сочленения Задача остовных деревьев в k–связном графе - реферат, что противоречит предположению.

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

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

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

Отметим без подтверждения последующую аксиому.

Аксиома 5.9 . Практически все ребра двусвязны Задача остовных деревьев в k–связном графе - реферат .

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

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

§6 Аксиома Менгера.

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

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

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

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

Приведем подтверждение принадлежащее В. Маквайгу (1982 г Задача остовных деревьев в k–связном графе - реферат.).

Ясно, что если k вершин делят a иb , то существует менее k попарно непересекающихся ( a, b) –цепей. Остается показать, что если в графе G нет огромного количества, содержащего наименее чем k вершин, разделяющих несмежные верхушки a иb , то в нем имеется k попарно непересекающихся цепей. Используем индукцию по k Задача остовных деревьев в k–связном графе - реферат . утверждение верно при k =1. Представим, что оно правильно для некого k 1. Разглядим граф G , в каком несмежные верхушки a иb нельзя поделить обилием, содержащим наименее чем k+1 вершин. По предположению индукции в G имеется k попарно непересекающихся ( a, b) –цепей P1 , P2 , …, Pk . Разглядим огромное количество вторых (считая а первой Задача остовных деревьев в k–связном графе - реферат) вершин в этих цепях. Это огромное количество состоит из k вершин и, как следует, но оно не делит верхушки a иb . Означает, имеется ( a, b) –цепь Р , 1-ое ребро которой не принадлежит ни одной из цепей Pi (i= ). Пусть v –1-ая, считая от а , верхушка Р , принадлежащая одной из Pi Задача остовных деревьев в k–связном графе - реферат (i= ), и пусть Pk +1 обозначает ( a, v) –подцепь цепи Р . Цепи P1 , …, Pk , Pk +1 могут быть выбраны, вообщем говоря, многими разными методами. Выберем их так, чтоб в графе G – a расстояние v доb было мало. Если окажется, что v= b , то P1 , P2 , …, Pk +1 будет требуемым набором k Задача остовных деревьев в k–связном графе - реферат+1 цепей. Допустим, что v b . Тогда в графе G – v верхушки a иb нельзя поделить обилием, содержащим наименее чем k вершин. По индуктивному предположению в этом имеется k непересекающихся ( a, b) – цепей Q1 , Q2 , …, Qk , которые могут быть выбраны различными методами. Выберем их так, чтоб огромное количество

включало малое число ребер Задача остовных деревьев в k–связном графе - реферат этих цепей. По другому говоря, цепи Qi должны состоять «в основном» из ребер цепей Pi . Разглядим сейчас граф H , состоящий из вершин и ребер цепей Q1 , Q2 , …, Qk и верхушки v (эта верхушка будет в графе H изолированной). Пусть Pr – одна из цепей Pi ( i= ) , у которой ребро, инцидентно Задача остовных деревьев в k–связном графе - реферат верхушке а , не принадлежит EH . Ясно, что такая цепь посреди Pi ( i= ) найдется, так как число их равно k+1 , а цепей Qi , составляющих H , только k . Пусть, дальше, x –1-ая, считая от а , верхушка Pr , входящая в VH .

Если x= b , то, добавив цепь Pr к Задача остовных деревьев в k–связном графе - реферат Q1 , Q2 , …, Qk , получим требуемый набор из k+1 (a, b ) цепей. Допустим, что x b , и разглядим другие способности дляx .

Если x=v , то обозначим через R кратчайшую ( v, b) – цепь и G – a . Пусть z – 1-ая, считая от v , верхушка цепи R , лежащая на некой Qj ( j= ) . Объединим цепь Pr Задача остовных деревьев в k–связном графе - реферат c( v, z) – подцепью цепи R и обозначим полученную ( a, z) – цепь через Qk +1 . Цепи Q1 , Q2 , …, Qk , Qk +1 владеют тем свойством, что расстояние в графе G – a от z до b меньше, чем расстояние от v до b , а это противоречит выбору P1 , P2 , …, Pk , Pk +1 .

Разглядим сейчас последнюю Задача остовных деревьев в k–связном графе - реферат возможность: x принадлежит некой цепи Qj ( j= ) . В данном случае ( a, x) – подцепь цепи Qi имеет ребра в L , по другому бы две цепи в {P1 , P2 , …, Pk , Pk +1 } пересекались в верхушках, хороших от a, b, v . Заменив сейчас ( a, x) – подцепь Qi на ( a, x) – подцепь Pr Задача остовных деревьев в k–связном графе - реферат , получим непересекающиеся (a, b) – цепи в графе G – v , и эти цепи будут использовать меньше ребер из L , чем Q1 , …, Qk . Опять получаем противоречие, которое и завершает подтверждение аксиомы.

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

Аксиома 6.1 . (Х. Уитни, 1932 г.). граф k–связен и тогда только тогда, когда неважно какая пара Задача остовных деревьев в k–связном графе - реферат его несовпадающих вершин соединена по очень мере k непересекающимися цепями .

Есть некоторое количество аналогов и обобщений аксиомы Менгера. Тут мы остановимся на реберном варианте этой аксиомы.

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

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

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

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

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


Глава III

Выделение k непересекающихся остовных деревьев 2 k –реберно связном графе

Из традиционного Задача остовных деревьев в k–связном графе - реферат результата теории графов – аксиомы Менгера– понятно, что для всех 2-ух вершин x и y графа G локальная реберная связность (x, y, G) приравнивается большему количеству непересекающихся по ребрам путей от x до y в графе G . Но, при k>1 не во всяком графе G с реберной связностью (G) k Задача остовных деревьев в k–связном графе - реферат есть k непересекающихся по ребрам связных остовов. Из ранее узнаваемых результатов «глобальным ананлогом» аксиомы Менгера в некой степени является доказанный итог: в графе G с реберной связностью (G) k есть k остовных деревьев T1 , T2 , …, Tk такие, что для хоть какого j от 1 до k объединение деревьев T1 , T2 , …, Tj Задача остовных деревьев в k–связном графе - реферат дает j–реберно связный граф.

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

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

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

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

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

§7. Построение k непересекающихся Задача остовных деревьев в k–связном графе - реферат остовных деревьев.

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

Замечание. Подтверждение обобщается на случай , когда верхушка z –точка сочленения, но ни одно из ребер с концами в z не является мостом. А именно, при (G) 2 для хоть какой верхушки z существует разрез по z таковой, что (Gz ) (G) .

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

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

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

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

Перейдем к подтверждению основного результата истинной работы.

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

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

Назовем новыми ребра графа G1 , добавленные при разрезе по верхушке z . Пусть этo ребра e Задача остовных деревьев в k–связном графе - реферат1 , …, em . Так как при построении разреза было добавлено k ребер, после этого были удалены петли, то m k. По индукционному предположению, у графа G1 есть непересекающиеся по ребрам остовные деревья T1 , T2 , …, Tk . Опишем способ построения по каждому из этих k деревьев остовного графа G. Все ребра, которые могут Задача остовных деревьев в k–связном графе - реферат заходить в деревья T1 , T2 , …, Tk , или являются ребрами графа G, или новыми ребрами. Пусть дерево Ti содержит mi новых ребер, тогда

m1 +m2 +…+mk m k (1)

Если дерево Ti не содержит ни 1-го нового ребра, то оно является подграфом мультиграфа G . Так как огромное количество вершин дерева Ti Задача остовных деревьев в k–связном графе - реферат содержит все верхушки графа G , не считая z , то добавив к Ti верхушку z и хоть какое ребро графа G с концом в z , мы получим остовное дерево T'i графа G . Отметим, что в данном случае для построения дерева T'i потребовалось одно ребро графа G , инцидентное верхушке z (при Задача остовных деревьев в k–связном графе - реферат этом это ребро можно избрать произвольно).

Представим, что mi >0 , другими словами дерево Ti содержит новые ребра. Поставим в соответствие дереву Ti подграф Ti * графа G , в каком каждое новое ребро xy дерева Ti заменим на два ребра xy и yz графа G . Каждое новое ребро в дереве Ti соответствует Задача остовных деревьев в k–связном графе - реферат двум ребрам в графе Ti * , при всем этом, к верхушкам дерева добавляется верхушка z . Как следует, мы получили связный остовный подграф Ti * графа G , в каком количество ребер на mi -1 больше , чем в дереве. Таким макаром, в графе Ti * ровно mi -1 цикл, при этом не тяжело увидеть, что любой Задача остовных деревьев в k–связном графе - реферат из этих циклов проходит через верхушку z . Как следует, из графа Ti * можно удалить mi -1 инцидентных верхушке z ребер так, что получится отстовное дерево Ti ' графа G . В дерево Ti ' заходит mi +1 ребро, инцидентное верхушке z . По построению разумеется, что при i j , mi >0 и mj >0 остовные деревья Ti Задача остовных деревьев в k–связном графе - реферат ' и Tj ' графа не имеют общих ребер.

Пронумеруем k непересекающихся по ребрам остовных деревьев графа G таким макаром, чтоб деревья T1 , …, Tn содержали новые ребра, а деревья Tn+1 , …, Tk не содержали новых ребер (где 0 ). При помощи описанного чуть повыше метода построим по остовным деревьям T1 , …, Tn графа G Задача остовных деревьев в k–связном графе - реферат1 остовные деревья T'1 , …, T'n графа G , никакие два из этих деревьев не будут иметь общих ребер. Всего при построении этих n деревьев применено (m1 +1)+…+(mn +1) ребер графа G, инцидентных верхушке z . В силу неравенства (1), мы получаем, что

(m1 +1)+…+(mn +1)=(m1 +m1 +…+m1 )+n (2)

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

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

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

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

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

Подтверждение. Пусть T1 , T2 ,…, Tk –остовные деревья графа G . По определению стягивания несложно увидеть, что графы TA 1 , TA 2 ,…, TA k связны и никакие два из их не имеют общих ребер.

Определние Задача остовных деревьев в k–связном графе - реферат 8.3. Пусть граф H(V, E) не имеет кратных ребер, a V, n>dH (a). Пусть граф H получен из Н в итоге подмены верхушки а на полный грaф Kn , при этом все ребра, инцидентные верхушке а в графе Н , в H будут из различных вершин соответственного Н полного графа Задача остовных деревьев в k–связном графе - реферат Kn .

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

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

unit diplom;

interface

uses

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

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

type

masiv = set of byte Задача остовных деревьев в k–связном графе - реферат;

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 Задача остовных деревьев в k–связном графе - реферат

{ 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 Задача остовных деревьев в k–связном графе - реферат_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 Задача остовных деревьев в k–связном графе - реферат

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;

combobox Задача остовных деревьев в k–связном графе - реферат1.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].y Задача остовных деревьев в k–связном графе - реферат1+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 Задача остовных деревьев в k–связном графе - реферат

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 Задача остовных деревьев в k–связном графе - реферат;

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

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 Задача остовных деревьев в k–связном графе - реферат*********

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 Image Задача остовных деревьев в k–связном графе - реферат2.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 Задача остовных деревьев в k–связном графе - реферат[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[i Задача остовных деревьев в k–связном графе - реферат1].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 Задача остовных деревьев в k–связном графе - реферат

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[i Задача остовных деревьев в k–связном графе - реферат1].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 Задача остовных деревьев в k–связном графе - реферат: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 (indi2)) then

begin

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

end;

if v=3 then

begin

a2:=data[s Задача остовных деревьев в k–связном графе - реферат_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 Задача остовных деревьев в k–связном графе - реферат(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.




Вывод Целью моей дипломной работы была изучить задачку на Задача остовных деревьев в k–связном графе - реферат построение разреза в графе по верхушке z. Был разработан метод, который строит разрез по заданому графу. По данному методу была написанна программка. Алгортм заключался в последующем: задается граф, по нем строится матрица смежности. В матрице суммируется строчка и если при делении на два остаток от деления равен нулю, тогда Задача остовных деревьев в k–связном графе - реферат данную верхушку убирают, а те верхушки которые были смежные с ней соединяются меж собой .
zadachi-duhovno-nravstvennogo-vospitaniya-i-stanovleniya-shkolnikov-v-obrazovatelnih-uchrezhdeniyah-dmitrovskogo-municipalnogo-rajona-v-usloviyah-vvedeniya-novogo-kursa-osnovi-religioznoj-kulturi-i-svetskoj-etiki.html
zadachi-ekonomicheskogo-analiza-reshaemie-na-osnove-regressionnih-ekonometricheskih-modelej.html
zadachi-etnopsihologii-kak-nauki.html