Спирина, М.С. Дискретная математика

Теорема 2.4. Ребро графа является мостом тогда и только тогда , когда не принадлежит ни одному циклу. ? Какие графы можно считать различными, а какие не различаются? Графы G' и G" называются изоморфными, если существует вза ­ имно-однозначное соответствие между их ребрами и вершинами, причем соответствующие ребра соединяют соответствующие вер­ шины. Поскольку в данном издании исследуются конечные множе­ ства, такая биекция должна быть подстановкой. Между названием вершины и ее номером различия нет. Смежность двух вершин есть бинарное отношение, поэтому изоморфизм графов можно рас­ сматривать как изоморфизм множеств их вершин (см. подразд. 1.4 и 1.6), на котором введено отношение смежности. Итак, графы G\(VUX ,) и G2( У2, Х2) называются изоморфными, если I У\\ =\Vji =п и существует подстановка о € Sn, такая, что V2 = 0(1^), а Х2= {(а( Г)); а(Уф) 1(К;, Уф е Л',}. Иными словами, можно так переобозначить вершины первого графа, что в новых обозначениях вершины и ребра будут совпадать со вторым графом, причем кратным ребрам первого G\ должны соответствовать кратные ребра второго Gg та ­ кой же кратности (рис. 2.5). Аналогично устанавливается изоморфизм между ориентирован­ ными графами. При этом следует помнить, что ребро является упорядоченным множеством, и надо быть особенно вниматель­ ным, соблюдая порядок. Важно, что изоморфизм графов является отношением эквива­ лентности. Это удобнее всего заметить исходя из свойств подста­ новок. На практике такие различные по внешним признакам и зо ­ морфные графы не различают, рассматривая их с точностью до изоморфизма. Граф (/называется планарным (плоским), если существует и зо ­ морфный ему граф G', в изображении которого на плоскости ребра пересекаются только в вершинах. Иными словами, у пла ­ нарного графа никакие два ребра не имеют общих точек, кроме общих вершин. На рис. 2.1 графы (?, и (73являются планарными, а G2 — нет. Областью назовем подмножество плоскости, пересека­ ющееся с планарным графом только по некоторому простому в 3 D 4 С Рис. 2.5. Изоморфные графы 75