Завдання остовних дерев у k-зв'язковому графі

Министерство Науки і Образования.

Республіки Молдова.

Молдавський Державний Университет.

Кафедра Інформатики і Дискретної Оптимизации.

Дипломна работа:

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

работу виконав ст. V курсу гр.52MI Жуков В.

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

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

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

Кишинев-2002.

Введение

…2 Глава I Основні определения…4 § 1 Основні визначення теорії графов…4 § 2 Матриці суміжності і инцидентности…10 § 3 Деревья…13 Глава II Зв’язність …18 § 4 Верхова зв’язність і реберна вязность…18 § 5 Двусвязные графы…22 § 6 Теорему Менгера…32 Глава III Виділення k непересічних остовных дерев 2k-реберно зв’язковому графе…36 § 7 Побудова k непересічних остовных деревьев…37 § 8 Необхідність умови [pic](G)[pic]2k…40 § 9 Текст программы…42 Вывод…51.

Запровадження Початок теорії графів як математичної дисципліни було покладено Эйлером в його знаменитому розмірковування про Кенигсбергских мости. Однак це стаття Эйлера 1736 року єдиної протягом майже сто років. Інтерес Вільгельма до проблемам теорії графів відродився близько середини минулого століття і він зосереджений головним чином Англії. Було багато причин для такого пожвавлення вивчення графів. Природні науки надали свій вплив це завдяки дослідженням електричних ланцюгів, моделей кристалів і структур молекул. Розвиток формальної логіки призвело до вивченню бінарних взаємин у формі графів. Велика кількість популярних головоломок подавалося формулюванням у термінах графів, і це призводило розумінню, що чимало завдання що така містять деяке математичне ядро, важливість якого за межі конкретного питання. Найбільш знаменита серед цих задач-проблема чотирьох фарб, вперше поставлена перед математиками Де Морганом близько 1850 року. Ніяка проблема не викликала таких численних і дотепних робіт у царині теорії графів. Завдяки своєї простий формулюванні і дратує невловимості вона й досі пір залишається потужним стимулом досліджень різних властивостей графов.

Справжнє століття було свідком неухильного розвитку теорії графів, яка протягом десяти — двадцять років вступив у новий період інтенсивних розробок. У процесі явно помітно вплив запитів нових областей: теорії ігор й програмування, теорії передачі повідомлень, електричних мереж, і контактних ланцюгів, і навіть проблем з психології та біології. У результаті розвитку предмет теорії графів вже є великим, що усі його основних напрямів неможливо викласти щодо одного томі. У цьому першому томі запропонованого двотомної праці зроблено акцепт на основні поняття і результати, викликають особливий систематичний інтерес. За теорією графів є обмаль книжок; основний була книга Д. Кёнига (1936), яка для свого часу давала превосходнейшее введення у предмет. Досить дивно, що таких книжок англійською досі не було, як і раніше, що чимало найважливіші результати отримано американськими і англійськими авторами.

Глава I.

Основні понятия.

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

Предметом перших завдань теоретично графів були конфігурації, які з крапок і що з'єднують їх ліній. У цих розглядах було несуттєво, прямі це лінії або ж є криволинейными безперервними дугами, з'єднуючими дві кінцеві точки, де ці лінії, є вони довгими чи короткими. Істотно тільки те, що вони з'єднують ці дві точки.

Це спричиняє визначенню графа як абстрактного математичного поняття. Розглядаючи безліч V, що складається з з'єднаних деяким чином точок. Назвемо V безліччю вершин і елементи v[pic]V-вершинами. Граф.

G=G (V) (1.1) з безліччю вершин V є певна сімейство поєднань, чи пар вида.

E=(a, b), a, b[pic]V (1.2) що вказують, які вершини є сусідніми. Відповідно до геометричних поданням графа кожна конкретна пара (1.2) називається руба графа; вершини a і b називаються кінцевими точками, чи кінцями ребра.

Можна також використовувати й інший підхід. Якщо дано два безлічі V1 і V2 то можна утворити безліч всіх пар

(v1,v2), v1[pic]V1, v2[pic]V2. Це безліч пар називається твором і позначається через V1(V2. У нашому випадку кожне подружжя вершин (a, b) є елементом твори V (V. Таким чином можна сказати, що граф G з (1.1) з цими ребрами (1.2) є деяке підмножина твори V (V.

Цю ухвалу графа має бути доповнене щодо одного важливому відношенні. У визначенні ребра (1.2) можна сприймати або не брати до уваги порядок розташування його кінців. Якщо це порядок несуттєвий, тобто. если.

E=(a, b)=(b, a), то кажуть, що Є є неориентированное ребро; Якщо ж цей порядок істотний, то Є називається орієнтованим руба. У разі а називається також початковій вершиною, а b-конечной вершиною ребра Є. Можна також говорити, що Є є ребро, що виходить з вершини, а (отходящее від вершини а, що виходять із вершини чи яке у вершину b (підходяще до вершині b, заходящее в вершину b). Як у разі орієнтованого, і у разі неориентированного ребра кажуть, що ребро Є з (1.2) инцидентно вершин a і b, і навіть що чи b инцидентны Е.

[pic].

У додатках граф зазвичай інтерпретується як мережу, у якій вершинами G є вузли. Два вузла a і b з'єднуються безупинної кривою (зокрема прямолінійні відрізком) тоді й тільки тоді, коли є пара (1.2). На малюнках вузли будуть позначатися маленькими гуртками, а орієнтація, якщо потрібно, — стрілкою на що становить ребро кривою (рис. 1.1).

Граф називається неориентированным, якщо кожне його ребро не ориентированно, і орієнтованим, якщо ориентированны усі його ребра.

[pic] На рис. 1.2 наведено приклади неориентированных графів. На рис 1.3 зображені ориентированны графы.

Нерідко природно розглядати змішані графи, мають як орієнтовані, так неорієнтовані ребра. Наприклад, план города.

[pic] можна як граф, у якому ребра представляють вулиці, а вершини — перехрестя; у своїй з одних вулицями може допускатися лише одностороннє рух, і тоді на відповідних ребрах вводиться орієнтація; на інших вулицями рух двостороннє, і відповідних ребрах вже ніякої орієнтації не вводится.

Ми вже зазначали, що з фактичному зображенні графа є велика свобода в розміщення вершин у виборі форми що з'єднують їх дуг. Тому може бути, що хоча б граф представляється зовсім різними кресленнями. Говоритимемо, що дві графа G і G «ізоморфні, якщо є таке взаємно однозначне відповідність між множинами їх вершин V і V', що вершини з'єднані ребрами у одному з графів у тому лише тому випадку, коли відповідні їм вершини з'єднані й інші графі. Якщо ребра орієнтовані, їх напрями також має відповідати одна одній. На рис 1.2 наведено приклади ізоморфних графів, освічених ребрами і вершинами правильних многогранников.

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

[pic] враховувати лише неизолированные вершини. Граф, який складається тільки з ізольованих вершин, називається нуль-графом і то, можливо вказано через 0. іншим важливим випадком є (неориентированный) повний граф.

U=U (V), (1.3) ребрами якого є різноманітні пари (1.2) обох різних вершин a і b з V. На рис. 1.4 дано схеми повних графів для множин вершин з чотирьох і з п’яти элементов.

У орієнтованому повному графі U (d) є пари ребер, за одним в кожному напрямі. З'єднуючі будь-які дві різні вершини a і b.

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

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

L=(a, a). (1.4) Таке ребро (1.4) називатиметься петлею. При зображенні графа петля буде представлятися замкнутої дугою, возвращающейся в вершину чи не що проходить через інші вершини (рис 1.5). Зашморг зазвичай вважається неориентированной. Можна розширити повний граф U в (1.3) до графа з петлями U0, добавляя.

[pic] петлю у кожному вершині, отже ребрами U0 є всі пари (1.2), де припускається і a=b.

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

Ei=(a, b) i, (1.5) як і зображено на рис. 1.6. Для орієнтованого графа дві вершини a і b можуть з'єднуватися кількома ребрами у кожному з направлений:

Ei=(a, b) i, [pic][pic]=(a, b) j,.

(рис. 1.7).

Щоб проілюструвати випадок, котрій ці поняття виявляються природними, розглянемо какое-либо командне змагання, наприклад турнірну таблицю ліги бейсболу. Вершинами відповідного графа.

[pic] є команди. Кілька команд Проте й У пов’язується руба щоразу, коли вони грали. Якщо, А виграла у У, це ребро будемо орієнтувати від, А до У. і якщо У виграла у Бо протилежному напрямі; у разі нічиєї ребро буде неориентированным.

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

[pic] кожного орієнтованого графа є також співвіднесений неориентированный граф Gu, ребрами якого є ребра G, але вже настав без орієнтацій. Іноді зручно перетворити неориентированный граф G в орієнтований граф Gd з допомогою процесу подвоєння, який перебуває в заміні кожного ребра G парою з тими самими кінцями і приписуванні їм протилежних ориентаций.

Граф називається пласким, коли може бути зображений на площині так що це перетину ребер є вершинами G. Граф на рис 1.8а плаский, а на рис 1.8б неплоский.

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

У § 1 ми визначили ребро Є (1.2) графа G (1.1) елемент чи точку (a, b) у творі V (V. Як завжди, елементи цього твору можна у вигляді клітин квадратної таблиці М із елементами безлічі V в ролі координат з двох осях (рис 2.1).

У точку з координатами (a, b) помістимо числа 1 чи 0 залежно від того, існує, або немає у G відповідне ребро. Таким чином, ми маємо кінцеву чи нескінченну матрицю суміжності (вершин) М (G), що цілком описує G, коли має однократные ребра. Зазвичай позначення вибираються те щоб елементи (а, а), відповідні петлям, розташовувалися на головною діагоналі матриці М. Якщо G-неориентированный граф, то ребра (a, b) і (b, a) існують одночасно, в такий спосіб, неориентированным графам відповідають симметрические матриці смежности.

Якщо G має кратні ребра, то числа 0 і одну у клітинах (a, b) можна замінити кратностями ((a, b) ребер, що з'єднують чи b. Це дає опис графа G матрицею з цілими неориентированными елементами. Назад, будь-яка така матриця то, можливо інтерпретована як граф, отже будь-які результати для графів можна сформулювати як властивості таких матриц.

Сказане призводить до подальшого розширення поняття графа, котрі використовують вже всі кінцеві чи нескінченні матриці, елементами яких є речові неотрицательные числа. Такі матриці зустрічаються в різних галузях математики. Наприклад, стохастические матриці - теоретично ймовірностей й у теоретичній фізиці. Де розглянута система має деяке безліч V можливих станів, і кожна пара станів (a, b) пов’язується деякою ймовірністю переходу ((a, b). Іншим прикладом є граф, що становить схему доріг, у якому ((a, b) означає відповідне відстань між чи b.

Графи можуть бути і описані матрицями іншого виду. Кожен граф складається з об'єктів двох типов-вершин і ребер. Можна побудувати сволок M1(G), рядки якої відповідають вершин, а столбцы-ребрам. На місці (а, Є) у цій матриці помістимо значення [pic](=1, якщо а-начальная вершина ребра Є, значення (=-1, якщо а-конечная вершина, і (=0, якщо, а чи не инцидентно Є. Якщо G-неориентированный граф, можна використовувати лише значення (=1 і (=0. Ця матриця M1(G) називається матрицею инцидентности графа G.

Введемо, нарешті, матрицю суміжності ребер I (G), де і рядки — і стовпчики відповідають ребрах G. Для простоти припустимо. Що G немає петель, а ребра неорієнтовані і однократные. На місці (E, E') в I (G) помістимо (=1, якщо Є. і Е'-различные ребра із загальним кінцем, і (=0, якщо Е=Е' або якщо вони мають загального кінця. Отже, I (G)-квадратная матриця, обумовлена графом G.

Можна підвестися й в іншу думку і розглядати I (G) як матрицю суміжності вершин для створення нового графа, також обозначаемого через I (G), вершинами якого є ребра Є графа G, а ребрами-пары (E, E') з (=1. Назвемо I (G) графом суміжності ребер чи суміжності графом для G. Існування такого графа, у якому колишні ребра стають вершинами і навпаки, пояснює двоїстість між вершинами і ребрами, котра трапляється нам у питаннях теорії графов.

Фактичне побудова суміжності графа I (G) по кресленню графа G просто. На кожному рубі Є вибираємо фіксовану точку їЇ, наприклад середину Є. Кілька таких вершин (е, е') з'єднуємо новим руба, що належить I (G), тоді і тільки тоді ми, коли відповідні ребра Є. і Є' мають загальну вершину в G.

[pic] Рис. 2.2 дає це побудова для графа тетраедра; смежностным графом для нього є граф октаэдра.

Припустимо, то вершині е сходиться ((е) ребер Е=(е, е') з G. Тоді в I (G) середина їЇ ребра Є з'єднується ребрами з ((е)-1 серединами інших ребер з G, мають кінець в е. Отже, в I (G) нові ребра утворюють новий граф U (e) з ((е) вершинами. У I (G) вершина їЇ з'єднується ребрами і з ((е')-1 серединами інших ребер з G, з мають кінець в e', й інші нові ребра утворюють інший повний граф U (e'). Два графа U (e) і U (e') мають рівно одну загальну вершину, саме вершину їЇ, котру визначаємо єдиним руба Є, що з'єднує e і e'. Отже, I (G) має непересічне по ребрах разложение.

I (G)=[pic] 2.1 На повні графи U (e) з ((е) вершинами, що U (e) має єдину загальну вершину з кожним із ((е) інших повних графів U (e'). Винятком є випадок, коли (e, e')-единственное ребро в e', тобто. ((е')=1. Тоді не існує графа. U (e'). Припустимо, що, навпаки, для графа G1 існує розкладання (2.1) на повні графи, що пара (U (e), U (e')) має більше загальної вершини. Тоді G1 можна як смежностный граф G1=I (G) деякого графа G, вважаючи, що кожен U (e) має (1[pic]((е) загальних вершин коїться з іншими U (e'). Кожному U (e) поставимо у відповідність одну вершину e і з'єднаємо e і e' руба в G тоді й тільки тоді, коли U (e) і U (e') мають загальну вершину. До цим ребрах додамо ((е) — (1 ребер (e, e''), які прямують до новим вершин e'', у яких існує одна це ребро.

[pic] § 3 Деревья.

[pic].

Деревом називається зв’язний граф, він циклів. Будь-який граф без циклів називається ациклическим (чи) лісом. Отже, компонентами лісу є дерева. На рис. 12 зображені все дерева шостого порядка.

Є кілька варіантів визначення дерева; окремі відбито у наступній теоремі. Теорему 3.1 Для графа такі затвердження эквивалентны:

1) G — дерево;

2) G — зв’язний граф і m=n-1;

3) G — ациклический граф і m=n-1;

4) будь-які дві незбіжні вершини графа з'єднує єдина проста цепь;

5) G — ациклический граф, у якого тим властивістю, що й каку-либо пару його несуміжних вершин з'єднати руба, то отриманий граф міститиме рівно один цикл.

1)[pic]2) Скористаємося індукцією по n. При n=1 твердження трививально.

Нехай n>1, е[pic]EG. У дереві G немає циклів, отже, відповідно до лемме.

4.1, граф G — е має дві компоненти Т1 і Т2,.

[pic] кожна з яких є дерево. Нехай дерево Ti є (ni, mi) — графом, i=1, 2. По індуктивному припущенню вірно рівність mi=ni-1. (1).

Далее имеем.

m=m1+m2+1=(n1−1)+(n2−1)+1=(n1+n2)-1=n-1. 2) [pic]3) Граф G зв’язний і m=n-1. Потрібно довести, що у G немає циклів. Нехай, навпаки, в графі G є цикл і нехай ребро е-ребро цього циклу. Тоді граф G — е зв’язний (лема 4.8) і має n-2 ребра, що суперечить теоремі 4.9. следовадельно, G -ациклический граф. 3) [pic]4) Нехай к-число компонент графа G. Нехай, далі, компонента Тi є (ni, mi)-графом. Оскільки Тi-дерево, то вірно рівність (1). Тепер маємо n-1=m=m1+m2+…+mk=(n1−1)+(n2−1)+…+(nk-1)=(n1+…+nk)-k=n-k; тобто. к=1. Отже, G-связный граф і тому будь-які незбіжні вершини u і v з'єднані у ньому просой ланцюгом. Якби G були дві незбіжні прості (u, v)-цепи, відповідно до утвердженню 4.3 об'єднання містив б цикл. Отже, кожні дві вершини з'єднані єдиною простий ланцюгом. 4) [pic]5) пара незбіжних вершин, що належать одному циклу, з'єднана по меншою мірою двома простими ціпами. Отже, граф G ациклический. Нехай u і v-две його нечмежные вершини. Приєднаємо до графу G ребро e=uv. У G є проста (u, v)-цепь, що у G+e доповнюється до циклу. З огляду на затвердження 4.4 цей цикл єдиний. 5) [pic]1) потрібно докакзать, що граф G зв’язний. Якби вершини u і v належали різним компонентами графа G, то граф G+uv у відсутності б циклов, что потиворечит утвердженню 5). Отже, G зв’язний і тому є деревом. Доведено. Слідство 3.2. У кожному дереві порядку n2 є неменш двох кінцевих вершин. Нехай d1, d2, …, dn (2) -статечний послідовність дерева. Тогда.

[pic] (лема про рукостисканнях) і всі di>0. Отже, хоча б два числа з послідовності (2) рівні 1.

Нехай Н-остовный подграф поизвольного гафа G. Коли кожної сфери связности графа G графом М породжує дерево, то М називається кістяком (чи каркасом) графа G. очевидно, що у кожному графі існує остов: руйнуючи у кожному компоненті цикли, тобто. видаляючи зайві ребра, то дійдемо кістяку. Остов в графі легко знайти з допомогою пошуку ширину. Слідство 3.3. число ребер довільного графа G, які потрібно видалити щоб одержати остова, залежить від послідовності їх видалення і одно m (G)-|G|+k (G), де m (G) і k (G)-число ребер і кількість компонент графа G відповідно. Якщо (n1, m1)-граф М є одним із компонент графа G, то тут для перетворення їх у кістяку дерево потрібно видалити m1-(n1−1) підхожих ребер. Підсумовуючи за всі k (G) компонентами, одержимо требуемое.

Кількість ((G)=m (G)-|G|+k (G) називається циклічним рангом (чи цикломатическим числом) графа G. число ребер остова графа G називається коциклическим рангом графа G. таким образом.

Очевидні три слідства 13.4−13.6. Слідство 3.4. Граф G є лісом тоді й тільки тоді, коли ((G)=0. Слідство 3.5. граф G має єдиний цикл тоді й тільки тоді, когда.

((G)=1. Слідство 3.6. Граф, у якому число ребер незгірш від, ніж число вершин, містить цикл. Твердження 3.7. Якщо P. S і Т -два остова графа G, то тут для будь-якого ребра е1 графа P. S існує ребро е2 графа Т, що граф є також остовом.

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

Не обмежуючи спільності, вважатимемо граф G зв’язковим. Граф має рівно дві області связности; нехай навіть це будуть Проте й У. Оскільки граф Т зв’язний, у ньому існує ребро е2, одне із кінців якого входить у А, а інший — в У. Граф Н=S-e1+e2 зв’язний і кількість ребер у ньому таку ж, як і дереві P. S. отже, вона сама є деревом. Отже, Н-остов графа G. Доведено. Теорему 13.8. Центр будь-якого дерева складається з однієї або з цих двох суміжних вершин.

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

Вочевидь, що кінцеві вершини дерева Т є центральними лише для T=K1 чи T=K2. Нехай Т дерево порядку n>2. Видаливши з Т все кінцеві, одержимо дерево Т'. Вочевидь, що ексцентриситет Т на одиницю менше эксцентриситета дерева Т і що центри дерев Т і Т збігаються. Далі доказ легео проводиться індукцією за кількістю веншин.Доказано.

Глава II.

Связность.

Зв’язний граф було визначено як граф, яка має будь-які дві вершини з'єднані ланцюгом. Так, обидва графа Кn і Cn связны, проте інтуїтивно ясно, що при n>3 граф Kn «сильніше» зв’язний, ніж Cn. У цьому главі вводиться й досліджуються поняття, що характеризують ступінь связности графа.

§ 4 Верхова зв’язність і реберна связность.

Перш ніж запровадити поняття верхової і реберної связности, розглянемо одну математичну модель, виникає, зокрема, під час проектування і аналізі мереж ЕОМ. Є мережу, що складається з центрів збереження і переробки інформації. Деякі пари центрів з'єднані каналами. Обмін інформацією між будь-якими двома центрами здійснюється або безпосередньо по що з'єднує їх каналу, якщо є, або через інші канали і центри. Мережа вважається справної, якщо кожне подружжя центрів у стані обмінюватися інформацією. Такий мережі природно зіставити граф: вершины-центры, ребра-каналы мережі. Тоді справної мережі відповідатиме зв’язний граф. Важливим поняттям є надійність (живучість) мережі, під якою зазвичай розуміють здатність мережі функціонувати на виході з ладу одного чи навіть кількох центрів чи (і) каналів. Зрозуміло, що менше надійної слід вважати ту мережу, справність якої порушується при ушкодженні меншого кількості елементів. Виявляється, надійність мережі можна вимірювати з урахуванням впроваджуються нижче определений.

Числом вершин связности (чи навіть числом связности) [pic](G) графа G називається найменше число вершин, видалення яких призводить до незв’язному чи одновершинному графу.

Приміром, [pic](K1)=0, [pic](Kn)=n-1, [pic](Cn)=2. Це дуже цілком узгоджується з інтуїтивним поданням тому, що з n>3 граф Kn сильніше зв’язний, ніж Cn.

Граф G, представлений на рис. 4.1 зв’язний, та його зв’язність можна порушити, видаливши вершину 4. Тому [pic](G)=1. Якщо ж таки спробувати порушити зв’язність цього графа шляхом видалення ребер (а чи не вершин), доведеться видалити щонайменше трьох ребер. Наприклад, G розпадається на дві компоненты.

[pic] під час видалення ребер {4,5}, {4,6}, {4,7}. Щоб врахувати цю обставину, введемо ще одне определение.

Нехай G-граф порядку n>1. Числом реберної связности [pic](G) графа G назвемо найменше число ребер, видалення яких призводить до незв’язному графу. Кількість реберної связности графа вважатимемо рівним нулю, коли цей граф одновершинный.

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

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

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

Отже, точки зчленування і мости — це свого роду «вузькі місця» графа. Граф, зображений на рис. 4.2, має трикрапку зчленування a, b, з і тільки міст ab.

Зрозуміло, що кінцева вершина мосту є точкою зчленування, якщо в графі є інші ребра, инцидентные цієї вершине.

Повертаючись до аналізованої на початку параграфа мережі, неважко помітити, що кількість верхової связности і кількість реберної связности її графа відбивають чутливість мережі до руйнації центрів — і каналів відповідно, а мостам і точкам зчленування відповідають найуразливіші місця мережі. Якщо [pic](G) — мінімальна ступінь вершин графа G, то, очевидно, що [pic](G)[pic][pic](G), оскільки видалення всіх ребер, инцидентных даної вершині, призводить до збільшення кількості компонент графа.

З’ясуємо де тепер співвідношень між числами [pic](G) і [pic](G). Якщо граф G не зв’язний чи має міст, то, очевидно, що [pic](G)= [pic](G). Нехай G- зв’язний граф без мостів. Виберемо у тому графі безліч Е1, що складається з [pic]=[pic](G) ребер, видалення яких призводить до незв’язному графу. Нехай E2[pic] E1, |E2|=[pic]-1. Граф G — E2 зв’язний і має міст, який позначимо через uv. До кожного ребра з багатьох Е2 виберемо какую-либо инцидентную йому вершину, відрізняється від u і v. Видалимо тепер обрані вершини з графа. Цим самим будуть віддалені, разом з іншими, і всі ребра, що входять до Е2. Якщо що залишилося граф не зв’язний, то [pic]=[pic](G)2. Тоді такі затвердження эквивалентны:

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

2) будь-які дві вершини графа належать простому циклу;

3) будь-яка вершина і будь-яка ребро належать простому циклу;

4) будь-які два ребра належать простому циклу;

5) для будь-яких двох вершин a і b і жодного ребра е існує простая.

(a, b)-цепь, що містить е;

6) для будь-яких трьох вершин a, b, c існує проста (a, b)-цепь, через з. 1)[pic]2). Нехай a і b-две вершини графа G. Розглянемо безліч всіх простих циклів графа G, містять а. Означимо через U безліч всіх вершин, які входять у ці цикли. Зрозуміло, що U[pic]Ш. Справді, простий цикл, у якому а, можна було одержати, об'єднати два ребра ax і ay (x?y) і просту (x, y)-цепь, яка через, а (існуючу відповідно до властивості 4)). Припустимо, що b[pic]U, і між іншим [pic]=VGU. Оскільки граф G зв’язний, у ньому знайдеться таке ребро zt, що z[pic]U, t[pic][pic](рис. 5.1). Нехай S-простой цикл, у якому a і z. Оскільки G — 2-связный граф, у ньому є проста (a, t)-цепь P, яка містить z. Нехай v — перша, починаючи з t, вершина, що входить у P. S, тобто. (t, v)-подцепь ланцюга P немає з P. S загальних вершин, відмінних v. Тепер легко побудувати простий цикл, у якому a і t. Він виходить об'єднанням (v, z) — ланцюга, що проходить через чи що є частиною P. S, з руба zt і (t, v)-подцепью ланцюга Р (на рис. 5.1 цей цикл показаний пунктирною лінією). Отже, t[pic]; але ці суперечить вибору ребра zt. Отже, [pic]=Ш, тобто. a і b лежать на загальному простому циклі. 2)[pic]3). Нехай а-вершина і zt-ребро графа G. За умовою G містить цикл P. S, проходить через вершини a і z. Не втрачаючи спільності вважатимемо, що zt[pic]S. Якщо за цьому виявиться, що P. S проходить через вершину t, то необхідний цикл будується вочевидь. Нехай P. S не проходить через t. Тоді розглянемо простий цикл P. S ", проходить через вершини t і a. Такий цикл, за умовою, існує. Частиною цього циклу є проста ланцюг Р, з'єднує t із певною вершиною v[pic]S. Ланцюг Р можна вибрати так, чтобы.

[pic] VP[pic]VS={v}. шуканий цикл тепер будується точно як і, як у минулому пункті. 3)[pic]4). Нехай ab і tz-два ребра графа G. За умовою G має прості цикли P. S і P. S ", перший із містить ab і z, а другий — ab і t. Далі шуканий цикл будується як і, як у попередніх пунктах. 4)[pic]5). Нехай a, b [pic]VG, tz[pic]EG. Будучи зв’язковим, граф G містить просту ланцюг P=(a, x,…, b). Відповідно до твердження 4) а графі G є простий цикл P. S, у якому ребра ax, tz. Легко бачити, що у об'єднанні S[pic]P є необхідна ланцюг. 5)[pic]6). Нехай a, b, c[pic]VG, cd[pic]EG. За умовою в графі є проста (a, b)-цепь, через cd і, отже, що містить з. 6)[pic]1). Нехай v[pic]VG. Покажемо. Що граф G — v зв’язний, тобто. будь-яка a, b його вершин з'єднана ланцюгом. Справді, за твердженням 6) в графі G є проста (v, b)-цепь, яка, очевидно, не проходить через v і, отже, є (a, b)-цепью й у графі G — v. Доказано.

Якщо формулюванні теореми 34.1 замінити скрізь слова «проста ланцюг» і «простий цикл» відповідно на свої слова «ланцюг» і «цикл», одержимо аналогічну теорему про 2-реберно-связном графах.

Як уже відзначалося вище, під час вирішення багатьох завдань на графах досить вміти вирішувати ці завдання кожної 2-связной компоненти графа. Тому цікавить взаємне розташування 2-компонент в графе.

Максимальні відносне включення елементи безлічі зв’язкових подграфов графа G, які мають точок зчленування, називаються його блоками. Отже, кожен блок графа або 2-связен, або збігаються з К2 чи К1 (граф К1 — блок тоді й тільки тоді, коли є зв’язковою компонентом). Зв’язний граф без точок зчленування також називають блоком.

[pic] Безліч вершин блоку називатимемо блоковым множеством.

Наприклад, граф, зображений на рис. 5.2, містить п’ять блоків Bi (i=1,2,3,4,5) (вони обведені пунктирними лініями). Серед цих блоків В1, В2 і В3 -2-связные графи, а кожен із двох решти є ребром.

Твердження 5.2. Будь-які два блоку графа мають трохи більше однієї загальної вершини. Зокрема, всяке ребро графа входить лише у один його блок.

Твердження 5.3. Якщо блок графа містить вершини a і b, він містить і будь-яку просту (a, b)-цепь цього графа.

Їх твердження безпосередньо взято з переказаних у початку параграфа властивостей 2-связных графів і теореми 5.1.

Слідство 5.4. Система блокових множин графа є покриттям множин його вершин. Кожна пара блокових множин або перетинаються, або мають єдину загальну вершину, і це вершина є точкою зчленування графа.

Наступна конструкція дає чітке уявлення про структуру графа «з точністю до блоків». Нехай В=В{Bi} і С={ci} - відповідно безлічі блоків і точок зчленування графа G. Порівняємо з G граф bc (G), яка має B[pic]C — безліч вершин і {Bici: B[pic]B, ci[pic]C, ci[pic]Bi} - безліч ребер. Тим самим було, ребра двудольного графа bc (G) свідчить про приналежність точок зчленування блоками. На рис. 5.3 представлені графи G і bc (G).

Твердження 5.5. Якщо граф G зв’язний, то bc (G)-дерево.

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

Вочевидь, що з связности графа G випливає зв’язність графа bc (G).

[pic] Припустимо, що bc (G) містить цикл З. Нехай це цикл имет вид С=(c[pic], b[pic], c[pic], b[pic],…, c[pic], b[pic], c[pic]). Кожен із блоків B[pic] містить (с[pic], с[pic]) — ланцюг й «об'єднання цих ланцюгів дає простий цикл в графі G. Означимо цей цикл через З ». Зрозуміло, що З «містить по вкрай мері дві вершини кожного з блоків B[pic]. Тому з затвердження 34.3 слід, що цикл З «має бути у кожному із цих блоків. Останнє означає, кожна пара блоків B[pic] має менш |З «|[pic]3 загальних вершин. Отримуємо в протиріччя з твердженням 5.2. доказано.

Граф bc (G) називається bc-деревом зв’язкового графа G. Блоки графа G, відповідні концевым вершин його bc-дерева, називаються кінцевими блоками.

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

На рис. 5.4 граф G має 5 аркушів L1, L2, L3, L4, L5 і 4 мосту, а граф G «показує, як пов’язані між собою листи графа G.

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

[pic].

Нехай G-связный граф, H-некоторый його подграф. Просту відкриту ланцюг. графа G назвемо H-цепь, якщо виконуються умови v1[pic]VH, vk[pic]VH, vi[pic]VH, i=[pic] ребро e=uv графа G також називатимемо Н-цепь, якщо u[pic]VH, v[pic]VH, e[pic]EH.

Лема 5.6. Нехай G-двусвязный граф. Тоді будь-кого його подграфа М, що містить більше вершини і відмінного від G, існує Н-цепь графа G.

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

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

Нехай подграф перестав бути остовным. Розглянемо три попарно різні вершини u[pic]VH, v[pic]VH, w[pic]VH. По теоремі 5.1 в графі G є проcтая (u, v) — ланцюг, через w. Вочевидь існування подцепи цьому ланцюзі, що є М — ланцюгом графа G. Доказано.

Нижче для u, v[pic]VG між іншим Guv = G-u-v.

Теорему 5.7. У всякому 3-связном графі G є таке ребро uv, що граф Guv немає точок сочленения.

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

Якщо |G|=n=4, то твердження теореми очевидно. Тому вважатимемо, що n[pic]5. Припустимо гидке, тобто. що з будь-якого ребра uv[pic]EG граф Guv має хоча б одну точку зчленування. Тоді на 3-связности графа G слід, що за будь-якого виборі ребра uv[pic]EG граф Guv має такими властивостями (рис. 5.5):

1) якщо, а — висяча вершина графа Guv, то av[pic]EG, au[pic]EG;

2) всякий висячий блок графа Guv, який є руба, містить таку пару вершин сек. і d, відмінних точок зчленування графа Guv, що uc[pic]EG, vd[pic]EG.

3) всякий блок графа Guv, має рівно дві точки зчленування чудовий від ребра, містить таку вершину l, не що є точкою зчленування графа Guv, що або ul[pic]EG.

[pic].

Означимо через Buv максимальний за кількістю вершин блок графа Guv, а через tuv- число вершин у цьому блоці. Тепер виберемо ребро uv те щоб число tuv було наибольшим.

Покажемо, у цьому разі tuv[pic]3. Нехай tuv=2 і а — висяча вершина графа Guv (що є деревом). Оскільки n[pic]5, що існує ребро cd[pic]EGuv. З властивості 1) випливає, що у графі Gcd існує цикл (u, a, v, u), тобто. tcd>tuv. Отримано протиріччя, отже, tuv[pic]3. Через Duv позначимо bc-дерево графа Guv і розглянемо такі случаи.

1. Дерево Duv перестав бути ланцюгом. Виберемо у тому дереві ланцюг, з'єднуючу пару висячих вершин і яка стелиться через вершину, відповідну блоку.

Buv. Цією ланцюга відповідає послідовність B1,…, Bp блоків графа.

Guv, серед яких міститься блок Buv, причому блоки B1 і Bp є висячими (рис. 5.6).

Нехай B «- довільний висячий блок графа Guv, відмінний від B1 і Bp. З властивостей 1) і 2) випливає існування таких відмінних точок зчленування графа Guv вершин a[pic]VB1, b[pic]VBp, c[pic]VB », uc[pic]EG, va[pic]EG, vb[pic]EG. Тоді, у графі Guc вершини безлічі [pic] входить у один блок і, отже, tuv0, тобто дерево Ti містить нові ребра. Поставимо у відповідність дереву Ti подграф Ti* графа G, у якому кожне нове ребро xy дерева Ti замінимо на два ребра xy і yz графа G. Кожна нова ребро в дереві Ti відповідає двом ребрах в графі Ti*, у своїй, до вершин дерева додається вершина z. Отже, ми маємо зв’язний остовный подграф Ti* графа G, у якому кількість ребер на mi-1 більше, ніж у дереві. Отже, в графі Ti* рівно mi-1 цикл, причому неважко помітити, що з цих циклів проходить через вершину z. Отже, з графа Ti* можна видалити mi-1 инцидентных вершині z ребер отже вийде отстовное дерево Ti «графа G. У дерево Ti «входить mi+1 ребро, инцидентное вершині z. За побудовою очевидно, що з i[pic]j, mi>0 і mj>0 остовные дерева Ti «і Tj «графа немає загальних ребер.

Пронумеруємо k непересічних по ребрах остовных дерев графа G в такий спосіб, щоб дерева T1, …, Tn містили нові ребра, а дерева Tn+1, …, Tk не містили нових ребер (де 0[pic]). З допомогою описаного вище способу побудуємо по остовным деревах T1, …, Tn графа G1 остовные дерева T «1, …, T «n графа G, ніякі дві з цих дерев ні мати загальних ребер. Загалом під час побудові цих n дерев використано (m1+1)+…+(mn+1) ребер графа G, инцидентных вершині z. З огляду на нерівності (1), ми маємо, что.

(m1+1)+…+(mn+1)=(m1+m1+…+m1)+n[pic] (2) Отже, з нерівності (2), й, оскільки dG (z)[pic], залишилися невикористаними ще хоча б n-k ребер графа G, инцидентных вершині z. Для доповнення кожного які залишилися дерев Tn+1, …, Tk до остовного дерева графа G потрібно ще у одному ребру, инцидентному вершині z, і ребро можна вибрати довільно. Отже, ми можемо побудувати попарно k непересічних по ребрах отстовных дерева графа G.

§ 8 Необхідність умови [pic](G)[pic]2k.

Ми покажм необхідність умови [pic](G)[pic]2k виділення k попарно непересічних по ребрах остовных дерев з графа G. Більше того, при n>1 нічого для будь-якого n ми побудуємо (2k-1)-вершинно зв’язний граф Gn, у якого ступеня всіх вершин більш n, але серед будь-яких k зв’язкових кістяків графа Gn какие-то два мають загальне ребро. Отже, ослаблення умови реберної 2k-связности не можна «компенсувати», накладаючи допoлнительно умови на мінімальну ступінь вершини і умова верхової (2k- 1)-связности. Перейдемо побудувати серії прикладів. Определение.8.1. Нехай A[pic]V-множество з некотрорых вершин графа G (V, E). Визначимо граф GA з безліччю вершин (VA)[pic] (де a[pic]). Видалимо в графі G все ребра між вершинами з множеcтва А, об'єднаємо все вершини множемтва На одну нову вершину а. Для будь-який вершини b[pic], ми додамо рівно dG (b, A) ребер ab. Усі вершини з VA і що з'єднують їх ребра в графі GA будуть ж, як й у графі G. Назвемо побудований граф GA стягиванием графа G на багато А. Лема 8.2. нехай у графі G (V, E) є k попарно непересічних по ребрах остовных дерева. Тоді нічого для будь-якого A[pic]V в графі GA також є k попарно непересічних по ребрах остовных дерева. Доказ. Нехай T1, T2,…, Tk -остовные дерева графа G. По визначенню стягування неважко помітити, що графи TA1, TA2,…, TAk связны і ні дві з них мають загальних ребер. Определние 8.3. Нехай граф H (V, E) немає кратних ребер, a[pic]V, n>dH (a). Нехай граф H[pic] отримано з М внаслідок заміни вершини але в повний грaф Kn, причому всі ребра, инцидентные вершині а графі М, в H[pic] переведуть зі різних вершин відповідного М повного графа Kn.

Для n>[pic] визначимо граф Hn, у якому кожну вершину, а графа H замінимо повним графом Kn (інших вершин в Hn немає). До кожного ребра ab графа М проведемо в графі Hn ребро, з'єднуюче какие-то дві вершини з відповідних a і b повних графів (такі ребра графа Hn ми назвемо головними). У цьому, ми проведемо головні ребра те щоб ніякі дві з них мали загального кінця (може бути оскільки n>[pic]).

Текст програми 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 і do if (sqr (X-data[k]. x1)+sqr (Y-data[k].y1).