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

124 XI Х2 XL Х4 Xs Хб а) б) Рис. 5.7 Каждому гиперграфу Hd'.X) можно поставить в соответствие двудольный граф G, см. рис. 5, 7, б). Два графа Gi=(Vj,Xi) и называются изоморфными, если между их мнолсествами вершин существует взаимно однозначное соответствие, сохраняющее смежность. Иными словами, Gi=(Vi,Xi) и G 2=( V j, X ^ изоморфны тогда и только тогда, когда существует взаимна однозначное соответствие между их вершинами У/ и обладающее тем свойством, что две вершины соедине^ш ребром в одном графе тогда и только тогда, когда соответствующие им вершины соединены ребром в другом графе. На рис. 5.8 приведен пример изоморфных графов, т. к. существует взаимно однозначное соответствие v; ^ и, сохраняющее смежность вершин. § 2. Изоморфизм графов ИЗ V4 Vj Vfi Рис. 5.8 Отношение изоморфизма, очевидно, обладает свойствами рефлексивности, симметричности и транзитивности, следовательно, это отношение является