Дискретная математика

137 тогда и только тогда, когда: I) число вершин ь V ж F'совпадает (н равны, например, «); 2) существует такое взаимно однозначное соответствие у/ множества {1,2,...,«} на себя, что а,у=й' ф ^ф. Доказательство. Необходимость. Пусть <р - изоморфизм G и G'. Докажем, что выполняются условия 1) и 2). Если (р - изоморфизм, то это означает, что ср взаимно однозначное отображение V т V, следовательно, условие 1) выполняется. Отображение (р сохраняет смежность, поэтому если V, было соединено ребром с ту, т.е. йу=1, то cp(vi)=v'k будет соединено ребром с cp(v^= v' „, следовательно, Тогда если ау=0, то аь,=0. Таким образом, ср порождает взаимно однозначное отображение у/ множества {1 ,2,•..,»} на себя {y/(i)=k, у/ф=т), при котором следовательно, условие 2) выполнено. Достаточность. Пусть выполняются условия 1) и 2). Докажем, что графы G я G' изоморфны. Определим отображение tp: (p(v)=v'y,^i). Это отображение (р взаимно однозначное и сохраняет смежность, следовательно, <р - изоморфизм Gи G", что и требовалось доказать. Доказательство теоремы с незначительными усложнения.ми переносится на случай мультиграфов и орграфов. Количество взаимно однозначных отображений множества {1,2,...,и} н а себя равно числу перестановок, т.е. равно п! и это число является большим п р и больших значениях п. Поэтому использовать непосредственно теорему 5 . 8 при практическом распознавании изоморфизма для графов с большим п нецелесообразно. В большинстве случаев можно использовать следующий метод распознавания изоморфизма, который сводит перебор к минимуму. Этот метод основан на построении графа соответствия для данных графов О и GРа с смо т рим построение графа соответствия для орграфов, Очевидно, что если графы G и С изоморфны, то у соответствующих вершин одинаковы локальные степени. Для орграфов одинаковы полустепени исхода и захода соответствующих вершин. В связи с этим строим граф соответствия как граф, множество вершин которого есть VUV\ и вершина из V соединена с вершиной из К'тогда и только тогда, когда у этих вершин совпадают локальные степени (полустепени исхода и захода) в графах G и G ' соответственно. Вершины из V между собой не соединяем, вершины из V'- тоже. Из построенного графа соответствия определяем, какие варианты отображений вершин из '•'ка К'допустимы и какие нет. Эти оставшиеся допустимые варианты придется перебрать и выяснить существование изоморфизма. Поясним на примере. Пусть даны орграфы, изображенные на рис 5,15.