Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 30
Текст из файла (страница 30)
Взвгшгннмц граф и гго мошричног задание 161 Гл. 3. Творим графов и мографов 160 Для взвешенного графа р;, если дуга (о,, о ) Е Гт' имеет вес р;,, О, если (о;, оу) й К 0 ш У ч Матрицы 5, Ит, Р полностью описывают взвешенный граф, Например, граф С (рис. 3.1,6) задается матрицами этого класса как 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 О 0 1 1 0 0 0 0 О 0 О 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 О 0 0 0 0 О хт хт трш 'рш 'рш Уш У 5(С) = И'(С) = При задании графа С (рис.
3.1, 6) отсутствует матрица Р(С), так как дуги этого графа не взвешены. Два графа, С = (У, 1т') и С' = (У', ст"), называются изоморфными, если существует такое взаимно однозначное соответствие между вершинами множеств У = (о,) и У' = (ит), что вершины и„ов соединены дугой (и„из) в одном из графов в том и только том случае, когда соответствующие им вершины и,', и' соединены дугой (и,', оз~) в другом графе.
Матрицы рассмотренных классов задают графы с точностью до изоморфизма. Обозначим через (А+) транспонированную матрицу ннцнденций А+. Матрица смежности, начальная А+ и конечная А матрицы ннциденций и диагональная матрица весов дуг связаны следующим равенством: 5=(А+) .Р (А ). (3.1) Стлепенью г(и) вершины о называется число дуг (ребер), инцидентных этой вершине, Используя понятие мог рафа, можно задавать более эффективно в смысле затраченного объема информации большие графы С,, матрицы смежности которых слабо зацолнены единицами. Графы этого класса имеют большое практическое значение.
Будем задавать связанный неорнентированный граф С = (У, Ц без петель моделью те = (М, 5м 5т, ..., 5„), в которой М = У; слово, определяемое 5;, представляет собой окрестность 0(и,) единичного радиуса вершины и, Е У, содержашую з — 1 вершину о,. Для иллюстрации этого задания рассмотрим тот же граф С (рис. 3.1,6), не учитывая ориентацию его ребер. Матрица инцидентности Я(тР) в этом случае представляет собой матрицу смеж- ности 5(тр) графа С, в которой диагональные элементы равны 1: ит ттз из зч из ив вт 1 0 1 1 0 0 0 0 1 1 0 1 0 0 1 1 1 1 1 0 О 1 0 1 1 0 1 0 0 1 1 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 ит из гз ив ит 1 0 1 0 0,1 0 1 1 0 1 0 0 1 0 1 из ив, вт гз которая имеет покрытие (ом иэ) или 1ов, оэу. Для определенности выберем первое покрытие.
Окончательно рассматриваемый граф С задается моделью тр, матрица инцидентности которой имеет вид ш из ш ш ит 1 1 1 1 0 0 0 1 1 1 0 0 1 0 0 0 0 0 1 0 ив Ют Для задания этой матрицы необходимо 20 бит вместо 49 бит црн задании этого графа матрицей смежности. Мограф С~ ф(Ф)) вз.л.г т„ Минимизацию затрачиваемого количества информации црн задании графа сведем к покрытию столбцов строками матрицы фтР). Для уменьшения трудоемкости поиска минимального покрытия вычеркнем поглощаемые строки и столбцы.
Строка а поглои4аепз сторону ~3, если множество столбцов М, покрываемых строкой а, содержит множество столбцов Мд, покрываемых строкой Д, Мв т Мд. Стполбгц о поглощагтп спзвлвбец 6, если множество строк Мв, покрывающих столбец 6, содержит множество строк М„покрывающих столбец а, М, с Мм Найдем покрытие столбцов строками матрицы Я(тр), затем удалим недиагональные единичные элементы, вошедшие в покрытие, и снова произведем покрытие столбцов и т. д. до тех пор, пока все недиагональные элементы не будут равны нулю.
В результате получим минимизированное задание графа С в виде соответствующего мографа, в котором сигнатура представляет собой сечения элементов полученных покрытий. В рассматриваемом случае минимальное покрытие имеет вид 1оз, ое), Этому покрытию соответствуют две окрестности единичного радиуса: 0(оз) = (им иэ, ов, ог) и 0(ие) = (ов, оэ, ит). После удаления соответствующих единиц нз матрицы я(тр) получаем матрицу ит из ив вв 163 Гл.3. г'горов графов и мавра ов 162 $3.2.
Связность и сильнал сгягностпь графа изображен на рис. 3.2. Уплотнение задания ориентированных графов с петлями аналогично первому способу. Отдельна задаются наги гг(тть) чала дуг графа в виде мографа (0ы)+ и концы дуг в виде мографа (0м) Для представления графов в виде композиции более простых графов введем следующие три операции: 1Ь(гх гг вг) объединение, сумму и произведение. 'Объединением графов О, = (У„ (т',) и 0ь = (Уь, 7УЬ) называется граф 0 = (У, (т'), носитель и сигнатура которого являются соответственно теоретико-множественным объединением носителей У„ Уь и сигнатур с(г, (ть графов 0„0ь (рис. 3.3, а). (г.
() (г, т) (г, 3) в (6, 1) (6, 3) (6, 3) Рис. з.з Суммой графов О, = (У„(т',) и 0ь = (Уь, Уь) называется граф 0 = (У, (У), представляющий собой объединение графов 0„0Ь и двудопьного полного графа К~к,црь(, построенного на носителях У, 1У, ГФь и Уь | У,ГЛ4Ь. Другими словами, при построении суммы графов О, и 0ь определяется их объединение и каждая вершина о; б У„не вошедшая в пересечение У, () Уь, соединяется со всеми вершинами Уь'1 У, () Уь, и наоборот. Будем говорить, что вершина о конусируст граф О, если она смежна со всеми вершинами графа О. Вершины, не вошедшие в пересечение слагаемых щ ~ У, Г) Уь прн суммировании графов О, и 0ь, конусируют соответственно Уь ~ У, Г) Уь и У, ~ У, П Уь (рис.
3.3, б). Декартовым произведением графов 0 = (У„ Г„) и 0Ь = = (Уь, Гь) называется граф (1 ) Г)~ 1 = 1а х 1Ь = т((оа;т вы)тт оа; Е Уг~ оь, Е Уь)1 Г(о... оь,.) = Гоги х Гоьт (рнс. 3.3, в). $3.2. Связность и сильная связность графа Распределение цепей, циклов в неориентированном графе и путей и контуров в ориентированном графе определяет многие свойства графа, в том числе его связность н сильную связность. 1(гпью называется последовательность ребер (ры рт,, рг) видар; = (о;, о;+) ), 1 = 1, 2,..., п.
Вершины цепи могут иметь степень, равную 1. Вершина о( со степенью, равной 1, называется концевой. Число ребер цепи, соединяющей вершины щ и о., называется ее длиной Цо;, о ). г(иклом назйвается цепь, концевые вершины которой совпадают. Все вершины цикла имеют степень г(и;) > 2. Цепь называется: еоешавной, если в ней повторяется хотя бы одно ребро; сложной, если повторяется хотя бы одна вершина; проешой, если не повторяется ни одна вершина.
Граф 0 = (У, ЬУ) называется связным, если любая пара его вершин соединена цепью. Максимальный по включению вершин связный подграф графа называется его компонентной связноеши. Граф называется несвязным, если число его компонент больше одной. Например, граф, состоящий из двух несмежных вершин, является несвязным и имеет две компоненты связности.
Рассмотрим алгоритм определения связности графа и числа его компонент. Теорема 3.1; Элгментп матрицы з", гдг з = [г( ] — матрица емгжноетпи, г; сеть множгетпво последовательных идентпификатпоров ребер, образующих цепь между о( и оу, представляет собой множгетпво цепей длины и, соединяющих вершины ьцт оу. При возведении в и-ю степень матрицы смежности Я = (г( ] Умножение рассматриваем каи конкатенацию (приписывание спра- 165 Гл.З. Теория графов и могрофое 164 1О А« 0 0 ... 0 0 А2 О ...
0 0 0 Аз 0 О 0 0 ... Аь «О ва к идентификатору, соответствующему «-й строке, идентификатора, соответствующего 7-му столбцу), а суммирование — как объединение полученных в результате умножения слов. Пример 2.1. Рассметрюервсвределение вевейв неориентировавиом графе Петерсена (рис. ЗЛ), матрива сменности воторото имеет следующий ввю 1 2 3 4 Ь О «7 З 9 10 1 Матрнва сменности Я овределяет расвределевие ребер (левей единичной длины).
Пля овределення левей длины 2 воаведемматриву сменности в ввадрат: 2 3 4 Ь г 7 о 9 10 23.2. Соязностль и сильнол селзностпь грофа Сума«ируя матривы я + оэ, волучаем, что в 2 результирующей матриве отсутствуют нулевые эле. менты, что означает существование деви длины 1 ь нли длины 2 меиду любой верой верщвн графа Петерсена. Следовательно, граф Петерсена связный и з дредставляет собой вомвонеиту свввности.
г у Понятие цепи является основным при изучении метрических свойств графа. Минимальная длина цепи, соединяющей вершины о; и о,называется раеетол- " р ноем г(о;, о ) между вершинами о;, озч г(о;, о;) = ппп 1ь(и;, о ). ь Максимальное расстояние между вершинами графа О называется диаметпром графа Ы(0): а(С) = п«ахппп1ь(о<, о ).
О ь Введенная на множестве всех вершин (о;, и.) графа «, ' функция «'(»;, и ) определяет его метрику. Действительно, эта функция з (ии о ) удовлетворяет следующим трем аксиомам: («Уо;, и,) (г(о;, оу) = 0) 4+ и; = о;; (чо;, о )(г(о;, о ) = г(о., о;)); («уиг, иу, иь) (г(оп о ) + г(и, оа) > г(о;, иь)); оурследнюю аксиому обычно называют неравенеп«вом трерголь.,йика.
Матрица А называется )с-клеточной, если в результате перестановки строк и столбцов она приводится к виду е матрица А;, « = 1, ..., 1с, не содержит ни одного нулевого элеЕнта (кроме, быть может, диагональных). ' Теорема 3.2. Граф сз еоетоитп из 19 компонентп связности Фогда и только тогда, когда его матрица доетижимоетпи в(й .о(а) = ~;[я(а))', (3.2) «м1 Фде Я(0) — матприца емежноетпи, Н(с ) — диаметпр графа С, авллетея И-клеточной.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
