В графе 18 вершин, причём степень каждой вершины равна 2 или 5, вершины обеих степеней присутствуют. Сколько компонент связности может быть в таком графе?
Так как в графе есть хотя бы одна вершина степени 5, есть хотя бы одна компонента с вершиной данной степени. Рассмотрим её. Кроме вершины степени 5 в этой компоненте не менее 5 вершин. Значит, в компоненте связности с вершиной степени 5 не менее шести вершин. Аналогично, в компоненте связности с вершиной степени 2 не менее трёх вершин. Значит, компонент не более 1 + (18 — 6) : 3 = 5.
Докажем, что любое количество компонент от 1 до 5 быть может. Сперва построим пример для 5 компонент. Пусть в одной компоненте две вершины степени 5 соединены ребром, а остальные вершины — вершины степени 2, присоединённые к обоим. Итого 6 вершин на одну компоненту. Остальные компоненты связности представлены циклами длины 3 из вершин степени 2.
Если требуется от 2 до 4 компонент, «склеим» две компоненты-цикла в одну, увеличив цикл.
Если требуется одна компонента, построим компоненту из шести вершин по примеру выше, а затем вместо ребра, соединяющего вершины степени 5, проложим путь из вершин степени 2.
Связный граф, Не связный граф, сильносвязный граф определения и теоремы
Привет, сегодня поговорим про связный граф, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое связный граф, не связный граф, сильносвязный граф , настоятельно рекомендую прочитать все из категории Дискретная математика. Теория множеств . Теория графов . Комбинаторика..
связный граф — граф, содержащий ровно одну компоненту связности. Это означает, что между любой парой вершин этого графа существует как минимум один путь.
Определение 11.1. Маршрутом в графе называется последовательность вершин и ребер, которая обладает следующими свойствами:
1. она начинается и заканчивается вершиной;
2. вершины и ребра в ней чередуются;
3. любое ребро последовательности имеет своими концами две вершины: непосредственно предшествующую ему в этой последовательности и следующую сразу за ним.
Первая и последняя вершины в этой последовательности называются началом и концом маршрута. Проиллюстрировать данное определение можно на примере путешествия между городами: сначала мы записываем начальный город нашего путешествия, потом дорогу, по которой из него выезжаем, потом город, в который прибываем, потом следующую дорогу, по которой едем дальше и т.д., пока не закончим путешествие в каком-нибудь городе, который и будет записан последним. Заметим, что согласно определению маршрута в нем одна и та же вершина или ребро могут встречаться несколько раз. Также можно отметить, что для задания маршрута достаточно указать только последовательность вершин, поскольку по ней последовательность ребер восстанавливается однозначно. Хотя в случае мультиграфа определение маршрута не меняется, но задать сам маршрут одной лишь последовательностью вершин может не получиться, поскольку для некоторых пар вершин ребро, соединяющее их, однозначно не определяется.
Определение 11.2. Путем называется такой маршрут, в котором никакое ребро не встречается дважды. Иногда его также называют цепью.
Определение 11.3. Граф называется связным если между любыми двумя его вершинами существует маршрут. В противном случае граф называется несвязным.
Определение 11.4. Любой несвязный граф состоит из нескольких связных графов, каждый из которых называется компонентой связности графа. В частности у связного графа ровно одна компонента связности.
Теорема 1. Граф на n вершинах, степень каждой из которых не менее (n − 1)/2, связен.
Доказательство. Предположим, что данный граф не является связным. Рассмотрим одну из его компонент связности и выберем в ней произвольную вершину. Поскольку эта вершина соединена не менее, чем с 
другими вершинами, то всего вместе с ней в этой компоненте связности не менее
вершин. Аналогично в любой другой компоненте связности не менее 
вершин. Поскольку несвязный граф имеет хотя бы две компоненты связности, то количество вершин в этих двух компонентах не менее 
, а это противоречит условию, что в графе n вершин. Значит сделанное предположение неверно и граф является связным.
Теорема 2. Связный граф, в котором степень каждой вершины четна, при удалении любого ребра остается связным.
Доказательство. Пусть мы удалили ребро, которое соединяло вершины A и B. Если после этого вершины A и B оказались в разных компонентах связности, то рассмотрим компоненту связности alt=»Связный граф, Не связный граф, сильносвязный граф определения и теоремы» />, содержащую вершину A. Поскольку количество ребер, выходящих из вершины A, уменьшилось на единицу, то степень вершины A также уменьшилась на единицу и стала нечетной, а степени всех остальных вершин в alt=»Связный граф, Не связный граф, сильносвязный граф определения и теоремы» />остались четными. Но это противоречит тому, что в любом графе количество нечетных вершин четно. (Это утверждение верно и для любой компоненты связности графа, поскольку сама по себе она тоже является графом.) А значит вершины A и B не могли оказаться в разных компонентах связности. Однако если вершины A и B оказались в одной компоненте связности, то существует маршрут M их соединяющий. Пусть X и Y — две произвольные вершины графа. Тогда между ними до удаления ребра существовал маршрут. Если в этом маршруте не содержалось ребра AB, то и в получившемся графе эти вершины связаны тем же маршрутом. Если же в в нем содержалось ребро AB один или несколько раз, то в любом месте, где оно появлялось, его вместе с вершинами A и B можно заменить на маршрут M, проходимый в прямом или обратном порядке в зависимости от того, проходилось ли ребро AB от вершины A к вершине B или наоборот. Но это означает, что граф остался связным.
Теорема 3. Если из полного графа на n вершинах удалить не более n − 2 ребер, то граф останется связным.
Доказательство. Докажем, что для разделения полного графа на несколько компонент связности необходимо удалить более n − 2 ребер, из этого и будет следовать утверждение теоремы. Предположим, что мы удалили некоторое количество ребер, в результате чего образовалось несколько компонент связности. Пусть в одной из них оказалось k вершин, где 1 6 k 6 n − 1. Во всех остальных компонентах (может одной, может нескольких) оказалось n − k вершин. В полном графе каждая из k вершин была соединена ребром с каждой из этих n − k вершин . Об этом говорит сайт https://intellect.icu . Поскольку теперь эти ребра исчезли, то количество ребер, выходящих из каждой из k вершин уменьшилось хотя бы на n − k, а общее количество ребер уменьшилось на k(n − k). Осталось показать, что пришлось удалить более n − 2 ребер, т.е. k(n − k) > n − 2. Для этого рассмотрим разность k(n − k) − (n − 2).
Поскольку 1 ≤ k ≤ n − 1, то каждая из скобок (k − 1) и (n − k − 1) неотрицательна, а значит разность k(n−k)−(n−2) больше 0. Тем самым мы доказали, что количество ребер, которое необходимо удалить из полного графа, чтобы сделать его несвязным, больше n−2, откуда и следует утверждение теоремы.
Примеры применения
Прямым применением теории графов является теория сетей — и ее приложение — теория электронных сетей. Например, все компьютеры, включенные в сеть Интернет, образуют связный граф, и хотя отдельная пара компьютеров может быть не соединена напрямую (в формулировке для графов — не быть соединены ребром), от каждого компьютера можно передать информацию к любому другому (есть путь из любой вершины графа в любую другую).
Связность для ориентированных графов
В ориентированных графах различают несколько понятий связности.
Ориентированный граф называется сильно-связным, если в нем существует (ориентированный) путь из любой вершины в любую другую, или, что эквивалентно, граф содержит ровно одну сильно связную компоненту.
Ориентированный граф называется слабо-связным, если является связным неориентированный граф, полученный из него заменой ориентированных ребер неориентированными.
Некоторые критерии связности
Здесь приведены некоторые критериальные (эквивалентные) определения связного графа:
Граф называется односвязным (связным), если:
- У него одна компонента связности
- Существует путь из любой вершины в любую другую вершину
- Существует путь из заданной вершины в любую другую вершину
- Содержит связный подграф, включающий все вершины исходного графа
- Содержит в качестве подграфа дерево, включающее все вершины исходного графа (такое дерево называется остовным)
- При произвольном делении его вершин на 2 группы всегда существует хотя бы 1 ребро, соединяющее пару вершин из разных групп
Сильно связные графы и компоненты графа
Ориентированный граф называется сильно связным или сильным, если для любых двух различных вершин Xi и Xj существует по крайней мере один путь, соединяющий Xi с 
. Это определение означает также, что любые две вершины такого графа взаимно достижимы.
Ориентированный граф называется односторонне связным или односторонним, если для любых двух различных вершин Xi и Xj существует по крайней мере один путь из Xi в Xj или из Xj в Xi (или оба одновременно).
Ориентированный граф называют слабо связным или слабым, для любых двух различных вершин графа существует по крайней мере один маршрут, соединяющий их.
Если для некоторой пары вершин орграфа не существует маршрута, соединяющего их, то такой орграф называется несвязным.
Граф приведенный на рис. 1.7(а), как легко проверить, сильно связанный. Граф, показанный па рис. 1.7(б), не является сильным (так как в нем нет пути из х1, в х3), но односторонне связный. Граф, изображенный на рис. 1.7(в), не является ни сильным, ни односторонним, поскольку в нем не существует путей от х2 к х5 и от х5 к х2. Он — слабо связный. Наконец, граф, приведенный на рис. 1.7(г), является несвязным.
Пусть дано некоторой свойство Р, которым могут обладать графы. Максимальным подграфом графа G относительно свойства Р называется порожденный подграф 
графа G, обладающий этим свойством и такой, что не существует другого порожденного подграфа , у которого 
, и который также обладает свойством Р. Так, например, если в качестве свойства Р взята сильная связность, то максимальным сильным подграфом графа С является сильный подграф, который не содержится в любом другом сильном подграфе. Такой подграф называется сильной компонентой графа С. Аналогично, односторонняя компонента представляет собой односторонний максимальный подграф, а слабая компонента — максимальный слабый подграф.
Рис. 1.7. (а) Сильно связанный граф, (б) Односторон не связный граф , (в) Слабо связный граф, (г) Несвязный граф.
Например, в графе G, приведенном на рис. 1.7(6), подграф 
является сильной компонентой графаG. С другой стороны, подграфы 
и
не являются сильными компонентами (хотя и являются сильными подграфами), поскольку они содержатся в графе
и, следовательно, не максимальные. В графе, показанном на рис. 1.7(в). подграф
является односторонней компонентой. В графе, приведенном на рис. 1.7(г), оба подграфа 
и 
являются слабыми компонентами, и у этого графа только две такие компоненты.
Из определений сразу же следует, что односторонние компоненты графа могут иметь общие вершины. Сильная компонента должна содержаться по крайней мере в одной односторонней компоненте, а односторонняя компонента содержится в некоторой слабой компоненте данного графа G.
Задачи
1 Докажите, что если в графе от некоторой вершины существует маршрут до любой другой, то граф связен.
2 Докажите, что если в графе между некоторыми двумя вершинами существует маршрут, то существует также и путь, соединяющий эти две вершины.
3 В государстве 50 городов, причем от каждого города можно доехать до любого другого, возможно с пересадками. Какое наименьшее число дорог может быть в этом государстве?
4 На плоскости нарисованы вершины графа, пронумерованные числами от 2 до 30. При этом две вершины с номерами a и b соединены ребром только в том случае, если одно из чисел a или b делится на другое. Сколько компонент связности имеет этот граф?
5. Летом Иван отдыхал в молодежном лагере «Восход», где вместе с ним находилось всего 53 школьника. После окончания отдыха некоторые пары обменялись адресами, причем у каждого из отдыхающих оказалось не менее 26 адресов. Через некоторое время Ивану понадобился адрес Николая, с которым он адресом не обменивался. Докажите, что Иван может узнать адрес Николая, т.е. существует цепочка из школьников, которая начинается с Ивана и оканчивается Николаем и в которой каждая пара соседей обменялась адресами.
6. Степень каждой вершины связного графа – не менее 100. Одно ребро выкинули. Может ли получиться несвязный граф?
7. В локальной компьютерной сети от сервера отходит 21 провод, от остальных компьютеров – по 4 провода, а от принтера – один провод. Докажите, что с сервера можно послать документ на принтер.
8. В стране из каждого города выходит 100 дорог и от любого города можно добраться до любого другого. Одну дорогу закрыли на ремонт. Докажите, что и теперь от любого города можно добраться до любого другого.
9. На конференции присутствуют 50 ученых, каждый из которых знаком по крайней мере с 25 участниками конференции. Докажите, что найдутся четверо из них, которых можно усадить за круглый стол так, чтобы каждый сидел рядом со знакомыми ему людьми.
10. В стране любые два города соединены или железной дорогой, или авиалинией. Доказать, что один из видов транспорта позволяет добраться из любого города в любой.
11. На листе бумаги отмечено 2011 точек. Двое играют в следующую игру: каждый своим ходом соединяет две отмеченные точки линией. Запрещается соединять пару точек повторно. Проигрывает тот, после хода которого из любой точки можно пройти в любую другую, двигаясь от вершины к вершине по проведенным линиям. Кто выигрывает при правильной игре?
12. В стране, кроме столицы, больше 100 городов. Столица страны соединена авиалиниями со 100 городами. Каждый из остальных городов соединен авиалиниями ровно с 10 городами. Известно, что из любого города можно перелететь в любой другой (может быть, с пересадками). В связи с экономическим кризисом было принято решение закрыть половину дорог из столицы. Докажите, что это можно сделать таким образом, чтобы после этого снова можно было бы из любого города перелететь в любой другой.
13. В стране 15 городов, некоторые из них соединены авиалиниями, принадлежащими трем авиакомпаниям. Известно, что даже если любая из авиакомпаний прекратитполеты, можно будет добраться из любого города в любой другой (возможно, с пересадками), пользуясь рейсами оставшихся двух компаний. Какое наименьшее количество авиалиний может быть в стране?
14. Между некоторыми из 2n городов установлено воздушное сообщение, причем каждый город связан (беспосадочными рейсами) не менее чем с n другими. Докажите, что если отменить любые n − 1 рейсов, то все равно из любого города можно добраться в любой другой на самолетах (с пересадками).
15. В некотором государстве города соединены дорогами. Длина любой дороги меньше 500 км, и из любого города в любой другой можно попасть, проехав по дорогам меньше 500 км. Когда одна дорога оказалась закрытой на ремонт, выяснилось, что из каждого города можно проехать по оставшимся дорогам в любой другой. Доказать, что при этом можно проехать меньше 1500 км.
16. Какое наименьшее число соединений требуется для организации проводной сети связи из 10 узлов, чтобы при выходе из строя любых двух узлов связи сохранялась возможность передачи информации между любыми двумя оставшимися (хотя бы по цепочке через другие узлы)?
17. На турбазе 12 домиков, между которыми крот прокопал 56 непересекающихся подземных ходов (два домика соединяются не более чем одним ходом). Докажите, что крот из любого домика может попасть в любой другой, передвигаясь по этим ходам.
18. Докажите, что граф на n вершинах, имеющий более (n − 1)(n − 2)/2 ребер, связный.
19. Каждая пара депутатов парламента либо дружит, либо враждует, причем имеется хотя бы одна пара враждующих депутатов. При этом неукоснительно соблюдаются условия «друг моего друга — мой друг» и «друг моего врага — мой враг». Известно, что в парламенте 50 депутатов, и что каждый из них послал открытки всем своим друзьям из числа коллег.
а) Какое наименьшее число открыток могло быть послано?
20. Числом связности χ графа называется наименьшее число вершин, удаление которых (вместе с выходящими из них ребрами) приводит к несвязному или одновершинному графу. Числом реберной связности λ графа называется наименьшее число ребер, удаление которых приводит к несвязному графу. Данные величины показывают, насколько граф «прочен», как много вершин и ребер нужно из него удалить, чтобы он «распался» на части.
а) Приведите примеры графа, для которого χ = 2, λ = 3.
б) Докажите, что для любого связного графа выполняется соотношение χ ≤ λ ≤ δ, где δ — минимальная из степеней вершин графа.
Вау!! 😲 Ты еще не читал? Это зря!
- Теорема Менгера
- Алгебраическая связность
- Константа Чигера ( теория графов )
- Динамическое соединение , несвязанная структура данных
- Граф расширителя (Экспандер )
- Сила графа
Напиши свое отношение про связный граф. Это меня вдохновит писать для тебя всё больше и больше интересного. Спасибо Надеюсь, что теперь ты понял что такое связный граф, не связный граф, сильносвязный граф и для чего все это нужно, а если не понял, или есть замечания, то нестесняся пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Дискретная математика. Теория множеств . Теория графов . Комбинаторика.
Связность, компоненты связности
Говорят, что вершина w орграфа D (графа G) достижима из вершины v, если существует путь из v в w (маршрут, соединяющий v, w).
Граф (орграф) называется связным (сильно связным), если для любых двух его вершин v, w существует маршрут (путь), соединяющий v, w (из v в w). Орграф называется односторонне связным, если для любых двух его вершин, по крайней мере одна достижима из другой.
Псевдографом ассоциированным с ориентированным псевдографом D = (V, E), называется псевдограф G = (V, E 0), в котором E 0 получается из Е заменой всех упорядоченных пар (v, w) на неупорядоченные < v, w > (рис. 14).
Рис. 14: а – ориентированный псевдограф, б – ассоциированный с ним псевдограф
Орграф называется слабо связным, если связным является ассоциированный с ним псевдограф. Если граф (орграф) не является связным (слабо связным), то он называется несвязным.
Компонентой связности (сильной связности) графа G (орграфа D) называется его связный (сильно связный) подграф, не являющийся собственным подграфом никакого другого связного (сильно связного) подграфа графа G (орграфа D).
Примеры: 1. У графа, изображенного на рис. 15, три компоненты связности.
2. У графа, изображенного на рис. 16, три компоненты сильной связности, показанные на рис. 17 а, 17 б.
Рис. 15 Рис. 16 Рис. 17
3. На рис. 18 показаны диаграммы сильно, односторонне и слабо связных графов.
Утверждение 1. Пусть G = (V, E) – псевдограф с p компонентами связности: G 1 = (V 1, E 1), …, Gp = (Vp, Ep), тогда
1) V = V 1È … È Vp, E = E 1È … È Ep, то есть G = G 1 È … È Gp;
2) Vi Ç Vj = Æ, Ei Ç Ej = Æ при i ¹ j.
Утверждение 2. Пусть D = (V, E) – ориентированный псевдограф с p компонентами сильной связности: D 1 = (V 1, E 1), …, Dp = (Vp, Ep), тогда
1) V = V 1È … È Vp, E = E 1È … È Ep, то есть D = D 1È … È Dp;
2) Vi Ç Vj = Æ, Ei Ç Ej = Æ при i ¹ j.
Утверждение 3. Пусть r – отношение достижимости на множестве V вершин псевдографа G, то есть v rw тогда и только тогда, когда либо v = w, либо существует маршрут, соединяющий v, w, тогда:
1) r – эквивалентность на V;
2) v rw тогда и только тогда, когда вершины v, w принадлежат одной компоненте связности псевдографа G;
3) для любого класса эквивалентности Vi Î V / r псевдограф Gi, порожденный множеством Vi, является компонентой связности псевдографа G;
4) для любой компоненты связности псевдографа Gi = (Vi, Еi) псевдографа G выполняется Vi Î V / r.
Утверждение 4. Пусть r 1 – отношение достижимости на множестве V вершин ориентированного псевдографа D, то есть v r 1 w тогда и только тогда, когда вершина w достижима из вершины v. Пусть r2 – отношение двусторонней достижимости на множестве V, то есть r 2 = r 1 ∩ r 1 -1 , тогда:
1) r 1 рефлексивно, транзитивно;
2) r 2 – эквивалентность на V;
3) v r 2 w только тогда, когда вершины v, w принадлежат одной компоненте сильной связности ориентированного псевдографа D;
4) для любого класса эквивалентности Vi Î V / r 2 ориентированный псевдограф Di, порожденный множеством Vi, является компонентой сильной связности ориентированного псевдографа D;
5) для любой компоненты сильной связности Di = (Vi, Еi) ориентированного псевдографа D выполняется Vi Î V / r 2.
Под операцией удаления вершины из графа (орграфа) понимают операцию, заключающуюся в удалении некоторой вершины вместе с инцидентными ей ребрами (дугами).
Вершина графа, удаление которой увеличивает число компонент связности, называется разделяющей или точкой сочленения.
Матрица связности
Пусть D = (V, E) – орграф, где V = < v 1, …, vn >. Матрицей достижимости орграфа D называется квадратная матрица Т(D) = [ ti,j ] порядка n, у которой ti,j =1, если вершина vj достижима из vi и ti,j = 0 – в противном случае. Матрицей сильной связности орграфа D называется квадратная матрица S(D) = [ si,j ] порядка n, у которой si,j =1, если вершина vi достижима из vj и одновременно вершина vj достижима из vi и si,j = 0 – в противном случае, то есть si,j = 1 тогда и только тогда, когда вершины vi, vj принадлежат одной компоненте сильной связности орграфа D.
Пусть G = (V, E) – орграф, где V = < v 1, …, vn >. Матрицей связности графа G называется квадратная матрица S(D) = [ si,j ] порядка n, у которой si,j = 1, если i = j или существует маршрут, соединяющий вершину vi, vj и si,j = 0 – в противном случае (то есть si,j = 1 тогда и только тогда, когда вершины vi, vj принадлежат одной компоненте связности орграфа G).
Задания
Для аудиторных занятий
1. Для графов, изображенных на рис. 4, записать последовательности, состоящие из вершин и ребер, являющиеся маршрутами длины 5, 4, 3 и 2 соответственно.
2. Для графов, изображенных на рис. 9 а, 9 б, 9 в, записать последовательности, состоящие из вершин и ребер, являющиеся цепью, простой цепью.
3. Для графов, изображенных на рис. 9 а, 9 б, 9 в, записать последовательности, состоящие из вершин и ребер, являющиеся циклом, контуром.
4. Для орграфа D, представленногона рис. 19, записать матрицу достижимости и матрицу сильной связности.
5. Для графа G (рис. 20) записать матрицу связности.
6. Можно ли утверждать, что сильно связный граф всегда содержит контур?
7. Сколько компонент связности содержит граф G (рис. 20)?
8. Какие вершины графа (рис. 21) являются точками сочленения?
9. Задано отношение достижимости r на множестве V. Какими свойствами обладает отношение r (рефлексивность, симметричность, транзитивность)?
10. Доказать, что в связном графе, содержащем по крайней мере две вершины, найдется вершина, не являющаяся точкой сочленения.
Для самостоятельной работы
1. Сколько компонент связности содержит граф D (рис. 19)?
2. Какие вершины графа (рис. 20) являются точками сочленения?
3. Сколько компонент связности содержит граф G (рис. 21)?
4. Для графа G, изображенного на рис. 21, записать матрицу связности.
5. Какие из следующих графов являются полно связными (рис. 22)?
6. Сколько компонент связности у заданного графа?
7. Определить матрицы достижимости для орграфов с матрицами смежности.
8. Определить матрицы сильной связности для орграфов с матрицами смежности.
9. Сколько компонент связности у орграфов из заданий 7 и 8?
10. Какими свойствами обладают графы из заданий 7 и 8 (рефлексивность, симметричность, транзитивность)?
Литература
1. Новиков, Ф. А. Дискретная математика для программистов: учебник для вузов / Ф. А. Новиков. – СПб.: Питер, 2001. – 304 с.
2. Акимов, О. Е. Дискретная математика. Логика, группы, графы – 2-е изд., доп. / О. Е. Акимов. – М.: Лаборатория базовых знаний, 2001. – 367 с.
3. Гаврилов, Г. П. Задачи и упражнения по курсу дискретной математики: учеб. пособие / Г. П. Гаврилов, А. А. Сапоженко. – М.: Наука, 1992. – 408 с.
Практическое занятие № 8
Тема: «Планарные графы»
Цель занятия:
усвоение таких понятий, как планарный граф, плоский граф, грани графа, эйлерова характеристика, гамма-алгоритм укладки графа.
Пояснение к работе
Время выполнения практического задания – 2 часа.
Последовательность выполнения
1. Руководствуясь приведенным теоретическим материалом, ответить на следующие вопросы:
Какое соотношение называется эйлеровой характеристикой поверхности?
Какой граф является планарным?
Какие вершины называются контактными?
Что такое сегмент плоского графа?
В чем заключается гамма-алгоритм укладки графа?
2. Дать определение следующих понятий:
– грань в плоском графе:
– внешняя грань в плоском графе.
3. Записать первое и второе следствие из формулы Эйлера.
4. Выполнить задания для аудиторных занятий.
5. Выполнить задания для самостоятельной работы.
Планарные графы
Помимо использования в дискретной математике, графы находят применение и в непрерывной математике, особенно в топологии. При этом графы представляют геометрические объекты на некоторой поверхности (часто на плоскости или на поверхности сферы).
Существует правило изображения графов на поверхности: рёбра графа должны пересекаться только своими концами, то есть в точках, представляющих вершины графа. Для графа, который может быть изображён подобным образом на плоскости, существует название: плоский граф.
Рассмотрим задачу о возможности нарисовать тот или иной граф без самопересечений, то есть нарисовать граф так, чтобы его ребра не имели общих внутренних точек. Поставленную задачу принято называть задачей о плоской укладке графа. Область применения результата, который мы получим, очень обширна. Одна из них – это изготовление электронных схем. Электрические цепи печатным способом наносятся на плату из изолирующего материала. Так как наносимые цепи не изолированы, то они не должны пересекаться. Отсюда вытекает вопрос, как расположить контакты на схеме, чтобы можно было без пересечений нанести цепи на плату. А если так сделать нельзя, то каким минимальным числом плат (слоев графа) можно обойтись?
Плоский граф – это граф, нарисованный таким образом, что его ребра не пересекаются. Говорят, что граф допускает плоскую укладку, если его можно нарисовать как плоский. Также плоские графы называют планарными (рис. 23).
Существуют и непланарные графы. На рис. 24 показаны два таких графа: полный пятивершинник и полный двудольный граф. Для них есть специальные обозначения: K 5 и K 3,3, соответственно.
 |
 |
| Рис. 23 | Рис. 24 |
В планарном графе можно говорить не только о вершинах и ребрах, но и о гранях.
Грань – это часть плоскости, окруженная простым циклом и не содержащая внутри себя других элементов графа. Внешняя грань – это вся плоскость, окружающая плоский граф.
Эйлерова характеристика
Для графов, уложенных на некоторой поверхности, справедливо определенное соотношение между числом вершин, ребер и граней. Это соотношение называется эйлеровой характеристикой поверхности.
Теорема (формула Эйлера). В связном планарном графе справедливо следующее соотношение: p – q + r = 2, где р – число вершин, q – число ребер, r – число граней с учетом внутренних и внешних граней.
Следствие. Если G – связный планарный граф (р > 3), то q £ 3 p — 6.
Каждая грань ограничена по крайней мере тремя ребрами, каждое ребро ограничивает не более трех граней, отсюда 3 r £ 2 q. Имеем:
2 = p – q + r £ p — q + 2 q /3 Þ 3 p — 3 q + 2 q ³ 6 Þ q £ 3 p – 6.
Следствие: К 5 и К 3,3 непланарны.
1. Рассмотрим К 5. Имеем: p = 5, q = 10. Если К 5 планарен, то по предыдущему следствию q = p (p — 1)/2 = 10 £ 3 p – 6 = 3×5 – 6 = 9 – противоречие.
2. Рассмотрим К 3,3. Имеем: p = 6, q = 9. В этом графе нет треугольников, значит, если этот граф планарен, то в его плоской укладке каждая грань ограничена не менее чем четырьмя ребрами и, следовательно, 4 r £ 2 q или 2 r £ q. По формуле Эйлера, 6 – 9 + r = 2, откуда r = 5. Имеем: 2 r = 2×5 = 10 £ q = 9 – противоречие.
Замечание. Граф планарен тогда и только тогда, когда он не содержит в качестве подграфов ни К 5, ни К 3,3.
Следствие. В любом планарном графе существует вершина, степень которой не больше 5.
От противного. Пусть " ν Î V d(v) ³ 6. Тогда 6 p £ = 2 q Þ 3 p £ q, но q £ 3 p — 6. Имеем: 3 p £ 3 p — 6, противоречие.
Задача о плоской укладке
Задача. Определить, является ли граф планарным, и, если да, то произвести его плоскую укладку.
Если на ребра планарного графа нанести произвольное число вершин степени 2, то он останется планарным; равным образом, если на ребра непланарного графа нанести вершины степени 2, то он планарным не станет.
Теорема (Понтрягин-Куратовский). Граф планарен тогда и только тогда, когда он не содержит в качестве частей графы К 5 и К 3,3 (быть может, с добавочными вершинами степени 2).
Гамма-алгоритм
Для плоской укладки графа и попутной проверки, планарен ли он, удобно пользоваться гамма-алгоритмом. На вход подаются графы, обладающие следующими свойствами: 1) граф связный; 2) граф имеет хотя бы один цикл; 3) граф не имеет мостиков, т. е. ребер, после удаления которых граф распадается на две компоненты связности.
Если нарушено свойство (1), то граф нужно укладывать отдельно по компонентам связности. Если нарушено свойство (2), то граф – дерево и нарисовать его плоскую укладку тривиально.
Случай нарушения свойства (3) рассмотрим более подробно. Если в графе есть мостики, то их нужно разрезать, провести отдельно плоскую укладку каждой компоненты связности, а затем соединить их мостиками. Здесь может возникнуть трудность: в процессе укладки концевые вершины мостика могут спрятаться внутри плоского графа. Нарисуем одну компоненту связности и будем присоединять к ней другие последовательно. Каждую новую компоненту связности будем рисовать в той грани, в которой лежит концевая вершина соответствующего мостика. Так как граф связности мостиками компонент связности является деревом, мы сумеем получить плоскую укладку.
Сначала изложим алгоритм на конкретном примере. Пусть дан граф G (рис. 25). Инициализация алгоритма производится так: выбираем любой простой цикл; в нашем примере <1, 2, 3, 4, 5, 6, 7, 8>и получаем две грани: Γ 1 – внешнюю и Γ 2 – внутреннюю (рис. 26). Обозначим выбранный цикл как G′. На каждом шаге будем строить множество сегментов. Каждый сегмент S относительно уже построенного графа G′ представляет собой одно из двух: ребро, оба конца которого принадлежат G′, но само оно не принадлежит G′; связную компоненту графа G–G′, дополненную всеми ребрами графа G, один из концов которых принадлежит связной компоненте, а второй из графа G′.
Те вершины, которые одновременно принадлежат G ′ и какому-то сегменту, назовем контактными. Для нашего примера сегменты и вершины изображены на рис. 27. Контактные вершины обведены в квадрат.
 |
 |
 |
| Рис. 25 | Рис. 26 | Рис. 27 |
Если бы в каком-нибудь сегменте не было ни одной контактной вершины, то граф до разрезания был бы несвязный; если бы была только одна, то граф имел бы мостик. Эти возможности заранее исключены, так что каждый сегмент имеет не менее двух контактных вершин. Поэтому в каждом сегменте имеется цепь между любой парой таких вершин.
Если все контактные вершины сегмента S имеют номера вершин какой-то грани Γ, то мы будем говорить, что грань Γ вмещает этот сегмент. Может быть, имеется не одна такая грань, вмещающая сегмент S, множество таких граней обозначим Γ(S), а их число – |Γ(S)|.
Общий шаг алгоритма следующий: обозреваются все сегменты Si и определяются числа |Γ(Si)|. Если хоть одно из них равно 0, то граф не планарен, конец. Иначе выбираем сегмент, для которого число |Γ(S)| минимально, или один из множества, если таких сегментов несколько. В этом сегменте найдем цепь между двумя контактными вершинами и уложим ее в любую из граней множества Γ(S), совместив контактные вершины сегмента с соответствующими вершинами грани. При этом данная грань разобьется на две.
В результате повторения общего шага либо будет получена плоская укладка, когда множество сегментов станет пустым, либо будет получено, что граф G не является планарным. Вернемся к нашему примеру. Пока для любого i: S i Î< Γ 1, Γ 2>, |Γ(Si)| = 2. Поэтому возьмем первый по номеру сегмент Si и цепь <4, 8>вставим в грань Γ 2. Получим увеличенную часть G ′ и уменьшенную систему сегментов (рис. 28 a, b).
Определим, какие грани вмещают новые сегменты. Теперь сегменты S 1 и S 2 вмещаются только в одну грань Γ 1, в то время как сегмент S 3 вмещается в две грани Γ 1 и Γ 3. Поэтому берем S 1. Возьмем в нем цепь между контактными вершинами, например <2, 7>, и уложим ее в Γ 1. Получим увеличенную часть G ′ и уменьшенную систему сегментов (рис. 29 a, b). Продолжая таким образом, в итоге получим плоскую укладку G (рис. 30).
 |
 |
| Рис. 29 | Рис. 30 |
Задания
Для аудиторных занятий
1. Построить попарно неизоморфные непланарные графы без петель и кратных ребер, содержащие 6 вершин и 11 ребер.
2. Построить однородный 9-вершинный граф без петель и кратных ребер, который не планарен вместе со своим дополнением.
3. Используя формулу Эйлера, доказать непланарность следующих графов:
а) К 5 (рис. 31 а); б) К 3.3 (рис. 31 б); в) граф Петерсена (рис. 32 а); г) граф на рис. 32 б.
4. Существует ли планарный граф без петель и кратных ребер, у которого:
а) 7 вершин и 16 ребер; б) 8 вершин и 17 ребер.
5. Какое наибольшее число граней может быть у плоского 5-вершинного графа, не имеющего петель и кратных ребер? Изобразить такой граф.
6. Какое наименьшее число вершин нужно удалить из графа G, чтобы получить планарный граф, если:
а) G – граф Петерсена (рис. 32 а); б) G – граф, изображенный на рис. 33.
7. Какое наименьшее число ребер нужно удалить из графа G, чтобы получить планарный граф, если:
а) G – граф Петерсена (рис. 32 а); б) G = К 6.
8. Существует ли плоский 6-вершинный граф без петель и кратных ребер, у которого 9 граней?
9. Построить все попарно неизоморфные плоские 6-вершинные графы без петель и кратных ребер, имеющие 8 граней.
10. Доказать, что в каждом планарном графе без петель и кратных ребер есть вершина степени не больше, чем 5.
Для самостоятельной работы
1. Доказать, что в любом планарном графе без петель и кратных ребер, имеющем не менее 4 вершин, найдутся хотя бы 4 вершины, степени которых не больше, чем 5.
2. Какое наименьшее число вершин необходимо удалить, чтобы граф стал планарным (рис. 32 б).
3. Какой из графов G может быть планарным:
а) граф, состоящий из 7 вершин и 16 ребер;
б) граф, состоящий из 8 вершин и 17 ребер;
в) граф, состоящий из 5 вершин и 10 ребер.
4. Используя формулу Эйлера, определить, планарен ли следующий граф:
5.Дать определение плоского графа:
а) плоский граф – это граф, нарисованный на плоскости таким образом, что его ребра пересекаются;
б) плоский граф – это граф, нарисованный на плоскости таким образом, что его ребра не пересекаются;
в) плоский граф – это граф, уложенный на плоскости.
6. Сколько граней имеет заданный плоский граф?
7. Какие вершины плоского графа называются контактными:
а) вершины, которые одновременно принадлежат плоскому графу G′ и какому-то сегменту;
б) вершины, которые одновременно принадлежат графу G и одному из сегментов;
в) вершины, которые одновременно не принадлежат плоскому графу G′ и какому-то сегменту.
8. Дать определение планарного графа:
а) планарный граф – это граф, нарисованный на плоскости таким образом, что его ребра пересекаются;
б) планарный граф – это граф, уложенный на плоскости;
в) планарный граф – это граф, нарисованный на плоскости таким образом, что его ребра не пересекаются.
9. Какой граф представлен записью K 3,3:
10. С помощью гамма-алгоритма укладки графа на плоскости определить планарнрсть графа (рис. 32 б).
Литература
- Новиков, Ф. А. Дискретная математика для программистов: учебник для вузов / Ф. А. Новиков. – СПб.: Питер, 2001. – 304 с.
- Горбатов, В. А. Фундаментальные основы дискретной математики / В. А. Горбатов. – М.: Наука, 2000. – 544 с.
Практическое занятие № 9
Тема: «Деревья»
Цель занятия:
усвоение таких понятий, как связные деревья, бинарные деревья, ориентированные деревья, высота, глубина дерева, упорядоченные и изоморфные деревья.
Пояснение к работе
Время выполнения практического задания – 2 часа.
Последовательность выполнения
1. Руководствуясь приведенным теоретическим материалом, ответить на следующие вопросы:
Какое дерево называется остовным? Привести пример.
Как определяется цикломатическое число графа?
Какой граф является ориентированным деревом?
Как определяются высота ордерева и высота вершины ордерева?
Какое дерево называется упорядоченным?
Как определяется глубина вершины?
Что такое уровень вершины ордерева?
Какие деревья являются изоморфными?
2. Дать определение следующих понятий:
3. Выполнить задания для аудиторных занятий.
4. Выполнить задания для самостоятельной работы.
9.1. Основные определения
Неориентированным деревом (или просто деревом) называется связный граф без циклов. Этому определению эквивалентны, как легко показать, следующие определения:
а) дерево есть связный граф, содержащий р вершин и р – 1 ребер;
б) дерево есть граф, любые две вершины которого можно соединить простой цепью.
Пример. Графы, изображенные на рис. 34, являются деревьями.
Если граф несвязный и не имеет циклов, то каждая его связная компонента будет деревом. Такой граф называется лесом.
Остовным деревом связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом.
Пример. Для графа, изображенного на рис. 35 а, графы на рис. 35 б и 35 в) являются остовными деревьями.
Пусть граф G имеет р вершин и q ребер. Так как всякое дерево с р вершинами по определению имеет р – 1 ребер, то любое остовное дерево графа G получается из этого графа в результате удаления q – (р – 1) = q – р + 1 ребер. Число g = q – р + 1 называется цикломатическим числом графа.
Ориентированные деревья
Ориентированным деревом называется орграф со следующими свойствами:
1. Существует единственный узел, для которого полустепень захода равна 0.
2. Полустепень захода для остальных узлов равна 1.
3. Каждый узел достижим из корня.
4. Если в ордереве отменить ориентацию ребер, то получится свободное дерево.
5. В ордереве нет контуров.
6. Для каждого узла существует единственный путь, ведущий в этот узел из корня.
7. Если в свободном дереве любую вершину назначить корнем, то получится ордерево. Каждое свободное дерево определяет не более р ориентированных деревьев.
Вершину v ордерева называют потомком вершины j, если существует путь из j в v. Вершина, не имеющая потомков, – лист.
Рассмотрим некоторые числовые параметры, которые характеризуют ордерево. Высота ордерева – это наибольшая длина пути из корня в лист. Глубина d(v) вершины v ордерева – это длина пути из корня в эту вершину. Высота h(v) вершины v ордерева – наибольшая длина пути из данной вершины в лист. Уровеньвершины ордерева – это разность между высотой ордерева и глубиной данной вершины.
Пример. Приведем пример ориентированных деревьев (рис. 36).
Упорядоченные деревья – это деревья, в которых относительный порядок поддеревьев фиксирован.
Пример. Рассмотрим три дерева, которые выглядят различными (рис. 37).
Как упорядоченные деревья все они различны, как ориентированные деревья первое и второе одинаковы, а второе и третье различны, как свободные деревья все они изоморфны.
Задания
Для аудиторных занятий
1. Доказать, что граф является деревом тогда и только тогда, когда он связен, но после удаления любого ребра становится несвязным.
2. Доказать, что количество рёбер дерева на единицу меньше количества вершин.
3. Доказать, что связными компонентами леса являются деревья.
4. Доказать, что если в связном неориентированном графе число вершин равно числу ребер, то можно выбросить одно из ребер так, что после этого граф станет деревом.
5. Изобразить все возможные диаграммы деревьев из семи вершин.
6. Изобразить все попарно неизоморфные 4-вершинные ордеревья.
7. Для заданного дерева построить деревья, которые различны с исходным как упорядоченные деревья, одинаковые как ориентированные деревья, как свободные деревья изоморфны.
8. Для заданных деревьев (рис. 37) определить высоту ордерева, уровеньвершин.
9. Для заданных деревьев (рис. 36) определить высоту h(v) вершин, глубину d(v) вершин.
10. Для заданных деревьев (рис. 35 а, 35 б) построить все возможные ордеревья.
Для самостоятельной работы
1. Изобразить все попарно неизоморфные 5-вершинные деревья.
2. Доказать, что количество рёбер дерева на единицу меньше количества вершин.
3. Для заданных деревьев (рис. 26) определить высоту ордерева, уровеньвершин.
4. Для заданных деревьев (рис. 37) определить высоту h(v) вершин, глубину d(v) вершин.
5. Изобразить все возможные диаграммы деревьев из шести вершин.
6. Для заданного дерева построить деревья, которые различны с исходным как упорядоченные деревья, одинаковые как ориентированные деревья, как свободные деревья изоморфны.
7. Для заданных деревьев (рис. 37) построить все возможные ордеревья.
8. Для заданного дерева (рис. 35 б) построить изоморфные ему деревья.
9. Для заданного дерева (рис. 35 в) построить не изоморфные ему деревья.
10. Для заданного дерева (рис. 35 б) построить деревья, которые различны с исходным как упорядоченные деревья.
Литература
1. Новиков, Ф. А. Дискретная математика для программистов: учебник для вузов / Ф. А. Новиков. – СПб.: Питер, 2001. – 304 с.
2. Горбатов, В. А. Фундаментальные основы дискретной математики / В. А. Горбатов. – М.: Наука, 2000. – 544 с.
3. Акимов, О. Е. Дискретная математика. Логика, группы, графы – 2-е изд., доп. / О. Е. Акимов. – М.: Лаборатория базовых знаний, 2001. – 367 с.
Подсчет количества компонент связности у неориентированных графов
связным, если для любых двух различных вершин У( и у2 существует простая незамкнутая цепь из V] в у2. Любой граф можно разбить на непересекающиеся связные графы, называемые компонентами или компонентами связности графа (7. Внутри каждой компоненты будет выполняться определение связности графа. Таким образом, несвязный граф имеет более одной (две или больше) компоненты. Связный граф всегда, по определению, состоит из одной компоненты.
где (/] — К9, у которого удалили восемь ребер, имеющих одну общую вершину; (72 — К7, у которого удалили три ребра, образующих цикл; (73 — Рь, к которому добавили три попарно несмежных ребра. Черта наверху обозначает дополнение указанного графа.
Решение такого рода задач удобнее всего демонстрировать в виде таблиц, так как заполнение каждой отдельной клетки, по сути, является очевидным. Для заданий а), б), в), г) решения и ответы даны в табл. 2.5—2.8.
Задача 2.23. Чему равно число компонент связности у графа, полученного в результате сложения полного графа на шести вершинах и простого цикла на восьми вершинах (общих вершин нет)?
Задача 2.24. Чему равно число компонент связности у графа, полученного в результате сложения регулярного графа на шести вершинах и простого цикла на десяти вершинах (общих вершин нет)?
Задача 2.25. Чему равно число компонент связности у графа, полученного в результате сложения пустого графа на пяти вершинах и пустого графа на десяти вершинах (общих вершин нет)?