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

138 из V6 v j Рис. 5.15 В каждом графе по 6 вершин, следовательно, возможных взаимно однозначных отображений 6.'=720. Перебрать все 720 отображении и выяснить среди них существование изоморфных отображений дбло громоздкое. Построим граф соответствия, см. рис. 5.16. У каждой вершины записываем полустепени исхода и захода в виде (к,1), здесь к - полустепень 1 2 3 4 5 б_ 2 5 3 4 1 6 ' "i 1 2 3 4 5 6_ 1 6 3 4 2 5 ' 1 2 3 4 5 6_ 2 6 3 4 1 5 ' 1 2 3 4 5 6 1 5 3 4 2 6" Очевидно, что вершину нужно отобразить на вершину из (vj-^ Wj), а V4-^ U4. Вершина V; может при изоморфных отобраясениях отображатьсян а Uj л ли Uj, вершина V2 - на us или щ, вершинаv j - на w/ или wj, а va - на us или Мй- Таким образом, из 720 возможных отображений осталось 4 отображения, при которых возможен изоморфизм. Эти отображения представлены справа от Рис. 5.15. Выясним, есть ли среди них изоморфное отображение рассматриваемых графов. При отображении 1) имеем, что ац=1, а a'12-O, следовательно, не выполнено второе условие теоремы 5.8, поэтому отображение 1) не будет изоморфизмом рассматриваемых графов. При исхода, I - полустепень захода вершины. UI ( 1 , 2 ) (1.2)w U2 (1,2) (2Д) V: из (3,0) (3,0) vj ® Ш (0,3) (0,3) V4 • (1,2) V5 гл (2,1) (2,1) VJ Щ (2,1) Рис. 5.16 1) 2) 3) 4)