XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 55
Текст из файла (страница 55)
Сначала выделим в С(1) вторую строку и второй столбец: С(1)— сп — — ш)п 1С11, С12 + С21 1 = шш10, оо1 = О, (2) . ~~ (1) (1) (1) ~~ сз, — — шш 1с21, С22 + с21 1 = шш (оо, оо1 = оо, сз1 = шш 1сз1 сзз + с21 ) = Ш1п1оо, оо1 = оо (2) ° ° (1) (1) Р) ~ с41 1пш1с41 с42 +с21 1 шш(3, 001 = 3. (г) . (1) (1) Р) Затем, чтобы вычислить первый столбец матрицы С(2), берем второй (выделенный) столбец матрицы С(1) и умножаем (в полукольце )с+) его элементы по очереди на первый элемент второй (выделенной) строки той же матрицы СО). Каждое такое произведение складываем в полукольце с одноименным элементом первого столбца матрицы С(1). Поскольку умножение в полукольце )с+ — это арифметическое сложение, а сложение — взятие наименьшего иэ двух чисел, мы получим следующие элементы первого столбца матрицы С(2): 341 5.7.Изоморфвззтграфов Как видим, первый столбец матрицы С(2) не изменился по сравнению с первым столбцом матрицы С(~).
Это означает, что нельзя уменьшить стоимость прохождения в первую вершину из других вершин графа, идя через вторую вершину (см. рис. 5.27). Точно так же для вычисления второго столбца матрицы С(2) умножаем второй столбец С(~) на второй элемент второй строки той же матрицы, для вычисления третьего столбца — на третий элемент второй строки и т.д.
Не выписывая подробно всех вычислений, отметим характерный момент — изменение элемента стз — — 8 по сравнению с стз — — 10, связанное с тем, что (2) (т) стоимость прохождения из е1 в ез по пути ранга 2 оказалась меньше, чем стоимость прохождения по пути ранга 1. Минимальная же стоимость прохождения с з — — 5 получена по пути (4) ранга 4. 5.7. Изоморфиэм графов Для ориентированного графа (К Е) множество Е дуг можно рассматривать как график бинарного отношения непосредстпвеннот) достижимости, заданного на множестве вершин. В неориентированном гра(ре (К Е) множество Е ребер является множеством неупорядоченных пар.
Для каждой неупорядоченной пары 1и, е) е Е можно считать, что вершины и и е связаны симметпричнмм бинарным отношением р, т.е. (и, е) е р и (е, и) Е р. Таким образом, с каждым неориентированым и ориентированным графом связано бинарное отношение р. Это отношение будем называть отпношением смезтсностпи. С алгебраической точки зрения как ориентированный, так и неориентированный граф можно рассматривать как модель, сигнатпура которой состоит из одного бинарного отношения: й = ()т, р). В классической теории графов изучаются преимущественно конечные модели такого рода.
342 5. ТЕОРИЯ ГРАФОВ При указанном подходе различия между ориентированным и неориентированным графами проявляется только в свойствах отношения смежности р. Если это отношение симмегвричио, то граф называют неориентированным, и с этой точки зрения неориентированный граф можно считать частным случаем ориентированного'. Применяя к данному частному случаю моделей общие понятия гомоморфиэма и изоморфизма (см. 4.4), мы можем сформулировать следующие определения. Определение 5.14.
Отображение Ь: У1 -+ Уо множества вершин графа 01 = (Уы р~) в множество вершин графа Сэ = = (Уэ, р2) называют гомоморфизмом граФов (графа С~ в граф Сэ), если для любых двух вершин, смежных в первом графе, их образы при отображении Ь смежны во втором графе, т.е. если (Чи, е е У1)(и р1 е =э Ци) рз Це)). Биекгвиекыб гомоморфизм Ь, такой, что любые две вершины смежны в первом графе тогда и только тогда, когда их образы смежны во втором графе, т.е.
(Чи, е е У1)(и р1 и е» Ци) рэ Це)), называют изоморфизмом графов 6~ и Сз (графа 01 на граф Сз), а графы 01 и Сз — изоморфными, что записывают в виде С~ ~ Сг. Гомоморфизм графов, который является эпиморфиэмом, называется также гомоморфизмом одного графа на другой. Возвращаясь к нашему определению графа посредством двух множеств: множества вершин У и множества ребер (дуг) Е, получим следующие варианты определений гомоморфизма и изоморфизма. 'При таком подходе в неориентированном графе могут быть ветле, если отношение р содержит некоторые элементы дпееокалк, в частности лвллетсл реЕелексиекьыь 343 5.7.
Ивоморфюм графов Гомоморфизм неориентированного графа Сд = (Уд, Ед) в не- ориентированный граф Сз = (Уз, Ез) есть такое отображение Ь: Уд -+ Уз, что для любых двух вершин первого графа, соединенных ребром, их образы при отображении Ь также соединены ребром, т.е. (Чдд, е Е Уд)((дд, е) е Ед =д (Ь(н), Ь(о)) е Ез). Гомоморфизм ориентированного графа Сд = (Уд, Ед) в ориентированный граф Сз = (Уо, Ез) есть такое отображение Ь: Уд -+ Уз, что для любых двух вершин дд, е первого графа, таких, что есть дуга, ведущая из дд в е, из вершины Ь(дд) тоже ведет дуга в Це), т.е.
(д7дд,е Е Уд)((и, е) Е Ед =в (Ь(дд), Ь(е)) Е Ез). Изоморфизм неориентированного графа Сд на неориентированный граф Сз есть такая оиекддиа Ь: Уд ~ Уз, при которой две вершины дд и е графа Сд соединены ребром тогда и только тогда, когда соединены ребром их образы Ь(дд) и Ь(е), т.е. (дддд, е Е Уд) (дд м е 4Ф Цдд) м Це)). Аналогично изоморфдсдм ориентированного графа Сд на ориентированный граф Со есть такая биекция Ь: Уд -д Уз, при которой в ориентированном графе Сд из вершины дд ведет дуга в вершину е тогда и только тогда, когда в ориентированном графе Сз из образа Цдд) вершины дд ведет дуга в образ Ь(о) вершины е, т.е.
(дддд, е Е Уд) (дд -+ е 44 Ь(и) ~ Ь(е) ). Пример 5.12. а. На рис. 5.29 отображение Ь, где Ь(ед) = ндд, Ь(ез) = ндз Ь(ез) = Ь(е4) = едз, есть гомоморфизм ориентированного графа Сд в ориентированный граф Сз. 344 5. ТЕОРИЯ ГРАФОВ ов о4 с Рис. 6.29 Обратим внимание на петлю (шз, шз): эта петля является образом дуги (о4, оз), так как Ь(04) = шз и Ь(оз) = шз Н противоположность этому петля (ш1, ш1) не имеет прообраза в 61. На этом же рисунке более толстыми стрелками выделен подгреб С~э графа Сз, порожденный подмножеством вершин (ш1, шз, шз). Этот подграф будет гомоморфным образом графа 01.
Удаляя петлю в вершине ш1, получим (для того же подмножества вершин) порожденный подграф, являющийся строгим гомоморфным образом графа 01. Отметим, что каждая дуга в строгом гомоморфном образе ориентированного графа 01 имеет прообраз в 01. б. На рис. 5.30 неориентированный граф Сз есть строгий гомоморфный образ графа 61 (если рассматривать неориентированные графы беэ петель). ша Ь~о21 4вз ЬЩ = Ь1од Рне. 5.30 в. На рис. 5.31 отображение Ь не является гомоморфиэмом 01 на 62> поскольку о1 + 52~ но Ь(ю1) ~~ Ь(оз) (пегли (ю1) ш1) 6.7. Иэоморфвзм графов нет); Цег) о )з(ез), хотя ез -+ ез и т.д.
Легко сообразить, что любой двухвершинный гомоморфный образ графа ззз на рис. 5.31 должен иметь петлю, и следовательно, Сз не является гомоморфным образом Сз ни при каком отображении. зоз = оа'оз) зоз = )з(сз) = М~а) зоа а'з Оз зоа ~г )з(оз) = )з1са) = зо„Цоз) = аоа Рис. 6.31 Рис. 6.33 На рис. 5.32 изображен один граф из множества двух- вершинных гомоморфных образов 01.
д. Графы, изображенные на рис. 5.33, изоморфны, и изоморфизмом является, например, отображение )з, такое, что )З(ЕЗ) = авз, )З(ЕЗ) = ЗО4 )З(ЕЗ) = аОЗз )З(Е4) = Зоб> ЗЗ(об) = ПЗЗ )З(об) = аоб зг Рис. 6.33 Зачастую для того, чтобы распознать изоморфизм графов, Удобно перейти от исходных графов к их дополнениям. 346 В.
ТЕОРИЯ ГРАФОВ Определение 5.15. Неориентированный (ориентированный) граф С = т';Е называют дополнением неориенптированного (ориентпированного) графа Ст = (К Е), где Е— дополнение мнозсества Е до множества всех неупорлдоченныг (упорлдоченныз пар) на У. Можно доказать, что графы иэоморфны тогда и только тогда, когда иэоморфны их дополнения.
Например, перейдем к дополнениям графов, юображенных на рис. 5.33. Анализ указанных дополнений (рис. 5.34) позволяет сразу обнаружить их иэоморфюм, а следовательно, и изоморфиэм исходных графов. Рнс. 5.34 Более сложные случаи распознавания юоморфюма (главным образом, для неориентированных графов) будут рассмотрены в 5.9.
Определение 5.16. Автпоморфизм графа Ст = (К р)— зто любая подстановка множества его вершин, являющаяся изоморфизмом Ст на себя. Можно показать, что композииил двух любых автоморфюмов графа снова есть автоморфизм этого графа, а подстановка, обратпнал к автоморфюму, опять-таки есть автоморфюм.
Таким образом, множество всех автоморфизмов данного графа образует группу по операции композиции, которая является подгруппой симметпрической группы множества вершин графа. Ее называют группой автаоморфизмов данного графа. 347 3.7. Изоиорфизи графов Рассмотрим некоторые примеры групп автоморфизмов. ог ог о о оэ "э "э Рис. 3.33 Пример 5.13. Найдем нетривиальные (т.е.
отличные от тождественной подстановки) автоморфизмы неориентированного графа, изображенного на рис. 5.36. Так как среди вершин графа лишь одна вершина еэ имеет степень 1 и лишь одна вершина е4 имеет степень 2, то при любом изоморфизме эти вершины перейдут в себя. Значит, при изоморфизме возможны лишь перестановки вершин ея 03 и 9$. оэ Рис. 3.36 Для графа, изображенного на рис. 5.35, а, группа автоморфизмов порождается пэрансаоэпэ4ияаэи (1 4) и (2 3), что легко усматривается из анализа дополнения этого графа (рис. 5.35, 6).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
