Изоморфизм, плоские графы, реализуемость в r
Похожесть и непохожесть однотипных объектов в математике определяется понятием изоморфизм.
Изоморфныеграфы (орграфы) имеют одинаковое число вершин и дуг и отличаюся лишь их обозначением, т.е. если можно переименовать вершины и дуги графа (орграфа) G так, чтобы получился граф G1, то графы G и G1 будут изоморфными.
На рис.3.5 изображены два изоморфных графа. Это следует из того, что вершины и дуги графа G2 можно переименовать так:
2 ’ 1, 1 ’ 3, 3 ’ 2; x1 ’ x3, x3 ’ x1, x
’ x.
У изоморфных графрв степени соответствующих друг другу вершин должны совпадать.
|
Рис. 3.5
На рис.3.6 изображены три орграфа. Орграф G1 изоморфен орграфу G2. Это следует из того, что вершины и дуги орграфа G2 можно переименовать следующим образом:
1 ’ 4, 2 ’ 3, 3 ’ 1, 4 ’ 2;
x
’ x, x ’ x
, x
’ x
, x ’ x, x ’ x, x
’ x.
В результате этого переименования из орграфа G2 получится следующий орграф
Сравнивая полученный граф с графом G рис.3.6, видим, что они
совпадают. Такое переименование удалось сделать потому, что вершины этих орграфов
“похожи”, т.е. двум вершинам каждого орграфа инцидентны две заходящие дуги и одна
выходящая, а двум остальным вершинам инцидентны одна заходящая и две выходящих дуги.