Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 20
Текст из файла (страница 20)
Таким образом, последовательности (еь еь ез, е,), (еь е,, е„е,), (е,, е„еь е,), (е„, еь е„е,) представляют один и тот же цикл. Часто считается,что можно менять по- Рис. 4.7 Рис. 4Д рядок ребер цикла на противоположный, т,е. например, последовательность (е4, ем еь е,) представляет тот же цикл (рис. 4.7). Участок цепи или цикла является цепью, а участок простой цепи или простого цикла — простой цепью, Связные компоненты графа.
Вершины о', п"~б называются связанными, если существует маршрут М с началом и' и концом о". Легко видеть, что в этом случае существует также маршрут с началом о" и концом о', Для этого ребра маршрута М должны идти в противоположном порядке. Пусть вершина о~6 инцидентна более чем двум ребрам маршрута М, связывающего вершины и' и в", е; — первое из этих РебеР, ес — последнее (1' 1+1). Тогда из маРшрута М можно выбросить участок от (1+1)-го ребра до (1 — 1)-го. Получится маршрут М'(еь ..., еь еь ..., е„). Если М' — не простая цепь, то можно продолжать этот процесс выбрасывания его внутреннего участка.
В конце концов получится простая цепь М*, связывающая о' и о", Таким образом, связанные маршрутом вершины связаны также и простой цепью. Если вершина о~6 связана с какой-либо другой вершиной о', она связана и сама с собой. Пусть о н и' связывает мар|прут М (еь еь ..., е.), тогда о и о связывает маршрут М' (е„ е,, „,, е„, е „ „,, е,, е,), в котором сначала идут ребра 1оо маршрута М, а затем они же, но в обратном порядке. Однако обычно счи~ают, что изолированная вершина также связана сама с собой и отношение связанности двух вершин, заданное на множестве вершин графа 6, рефлексивно. Как было указано ранее, оно симметрично.
Наконец, оно транзитивно. Если вершина о' связана с вершиной о" маршрутом М' (е'„..., с„'), а о" с о"' — маршрутом М" (е1, ..., е ), то о) связана с о"' маршрутом М (е,',а, ..., е„', е",, ..., е,"), в котором сначала идут ребра маршрута М', а затем ребра маршрута М". Последователыюсть ребер М вЂ” это маршрут. Действительно, кроме пары ребер е„', е",, остальные пары соседних ребер являются соседними в одном из маршрутов М' или М" и имеют общую инцндентную вершину.
Ребра >ке е„' и е, инцидентны вершине о". Итак, отношение связанности вершин обладает свойствами отношения эквивалентности и определяет разбиение множества вершин графа на непересекающиеся подмножества гь Вершины одного и того же множества г'; связаны друг с другом, а вершины различных множеств Г; и Р~ не связаны между собой. Поэтому в графе 6 нет ребер с концами в разных множествах г'; и г'ь и он может быть разложен в прямую сумму подграфов; 6 ()6(Р~). Граф 6 называется связным, если все его вершины связаны между собой.
Поэтому все подграфы 6(Г;) связны и называются связными компонентами рассматриваемого графа. Расстояния. Пусть 6 — связный неориентированный граф, о' и о" — любые две его вершины. Тогда существует связываюшая их простая цепь М (еь е„,.., сч). Если количество д ребер этой цепи — ие минимальное из возможных, то существует цепь М' (е,', е,,', ..., е,',), связывающая о' и о" и имеющая меиынее число ребер.
Если и М' не минимально, можно найти связывающую о' и о" цепь с еще меньшим количеством ребер и т. д. Однако этот процесс уменьшения числа ребер можно повторить не более д раз, так как это число каждый раз уменьшается не меньше чем на единицу. Поэтому существует связывающая о' и о" цепь М (е„е, ..., е„) с минимальным количеством ребер р, Минимальная длина простой цепи с началом о' и концом о' называется расстоянием д (о', о") между этими вершинами (в 5 4.4 будут рассмотрены более общие понятия длины цепи и расстояния между вершинами). 101 Считая каждую вершину о неориентированного графа связанной с самой собой, мы по существу ввели нулевые маршруты, не содержащие ребер, с началом и концом в любой вершине о~6, В соответствии с этим расстояние д (о, о) между вершиной о и ею самой равно О.
Для любой пары о', онен6 различных вершин й (о', о") )О, так как связывающая эти вершины цепь состоит хотя бы из одного ребра. Расстояние й (о', о") удовлетворяет аксиомам метрики: 1) й (о', о") )О, причем а' (о',о") =О тогда и только тогда, когда о'=о"; 2) И (о', о") =д (о", о'); 3) справедливо неравенство треугольника; д (о', о")+ '+й (о", о"') = й (о', о"'), В особом доказательстве нуждается только последнее свойство. Пусть М' (о', о"') и М" (о", о"') — минимальные простые цепи, связывающие о' с о" и о" с о"'.
Тогда последовательность ребер М (е'„е,', ..., е'„е",, е,", ..., е .), в которой сначала идут ребра цепи М', а затем ребра цепи М",— это маршрут, связывающий о' и о"' и имеющий длину д (о', о")+д (о", о"'). Как показано ранее, если этот маршрут не является простой цепью, то можно найти более короткую цепь Л, связывающую о' и о". Поэтому во всяком случае минимальная связывающая эти вершины цепь имеет длину, не превосходящую суммы й (о', о")+с( (о", о"'), Диаметр, радиус и центр графа. Пусть 6 — конечный неориентированный связный граф. Тогда можно определить его дииметр д(6) =гпахд(о', о").
Кратчайшие простые ь',в"~Бе цепи, связывающие вершины о', он~6 с максимальным расстоянием между ними, называются диаметральными простыми ценя.ии. Пусть о — произвольная вершина рассматриваемого графа 6 Максимальным удалением в графе 6 от вершины о называется величина г(о)= шах й(о, о').
Вершке'яе на о называется центром графа 6, если максимальное удаление от нее принимает минимальное значение г(6)= = ппп г(о'). Максимальное удаление г(6) от центра ~ее называется радиусом графа, а любая кратчайшая цепь от центра о до максимально удаленной от него вершины о'— радиальной цепью. Центр не обязательно должен быть единственным, Например, в полном неориентироеанном графе К()г), в кото- ром любые две различные вершины о', он~)г соединены ребром, радиус равен единице н любая вершина оен(1 является центром.
Протяжеггиости. Пусть 6 — конечный, связный иеориеитироваииый граф, т — число его ребер. Количество последовательностей ребер этого графа без повторений равно тй т.е, конечно. Следовательно, коиечво и число простых цепей, в которых ребра пе повторяются. Протяженностью д(о', о") между вершинами о', о"ш6 называется максимальная из длин связывающих эти вершины простых испей. Если исключить из этих простых цепей циклы, то для любой вершины огм(г 8(о, о) =О. В этом случае протяженность также удовлетворяет аксиомам метрики. Как и для расстояния, в доказательстве иуждается лишь иеравеиство треугольника. Пусть Е(о', о"') — самая длиикая простая цепь, соелиияющая вершины о' и о"', Е*[о", о')— какая-то простая цепь с началом о" и концом о', Е(о", огч) — участок последней цепи до первого пересечения с цепью Е (рис.
4.8). Тогда Рис. 4.9 Рис. 4.8 огц делит цепь ва два участка Е' и Е" (одии из этих участков или же участок Е может быть пустым). Участки Е' в Е составляют простую цепь с началом о' и концом о", а Е" и Š— простую цепь, соедипяющую он и о"', причем сумма их длин ие меньше ллииы цепи Е. Значит, и сумма максимальных длин путей с теми же началами и концами, равиая 8(о', о")+8(о", о"'), ие меньше длины цепи Е, которая равиа В графе 6 существуют диомегральные ло протяженности или длиннейгние простые нели, Их длина 1, иазывается диаметром протяженности.
Для каждой вершины о существуют самые длинные простые цепи с коицом в этой вершине. Их ллипа 8(о) = гпах 8(о, о') иаэы- о'Е- :к вается числом протяженности лля вершипы о. Центрами протяжевиости называются вершивы зс с минимальным числом протяжеииости лэ 8(зр)= ш(п 8(о). Самые длиииые простые цепи с началом в центре сг=. к !03 протяженности называются радиальными по протяткенности, а их длина Ка — радиусом протяженности, Любые днаметральные по протягкепности испи (л н Ез пересекаются. Если бы зто было не так, нашлась бы простая связывающая цепь М(о', о"), такая, что о' лежит на ьь о" — па Ем а остальные вершины М не принадлежат ь1 и ьз (рис. 4.9). Пусть Ь~ и Ез — более длинные из участков, на которые разбиваются Е, и ьз вершинами о' и о".
Тогда длина простой цепи 1.'()М(о', о") о/." больше 1ь г Матрица и цепи. Произведение графов. Пусть 6 и Н— два графа, оба ориентированные или неориентированные, без кратных ребер с одним и тем же множеством вершин У. В произведении этих графов г'=ОН ребро (о', о") существует в том и только том случае, когда для некоторой вершины оен)г существуют ребра (о', о)ен6, (о, о")енН, т.
е. существует маршрут из двух ребер с началом о' и концом о", причем первый элемент маршрута принадлежит графу 6, а второй — графу Н. Матрица смежности произведения графов равна произведению матриц смежности сомножителей, только вместо обычных произведений и сумм нужно рассматривать логические: боп (б<а> ~ б<н>) а=1 Для графов с кратными ребрами в произведении 6Н кратностью ребра (о', о") считается число маршрутов длины 2 в графе 6()Н таких, что первое ребро содержит о' и принадлежит 6, а второе ребро содержит о" и принадлежит Н, При таком определении б(ю жз б(о) б[нз П = г п~ а1 Таким образом, произведение графов без кратных ребер может оказаться имеющим кратные ребра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
