3.1.2. Изоморфизм, гомеоморфизм

Определение. Два графа G1 и G2 называются изоморфными, если существует взаимно однозначное соответствие между множествами их вершин, обладающее тем свойством, что число ребер, соединяющих любые две вершины в G1, равно число ребер, соединяющих соответствующие вершины в G2.

Из определения следует, что изоморфные графы можно одинаково изображать графически и отличаться они будут только метками вершин.

Изоморфизм графов есть отношение эквивалентности.

Пример 70.

На рисунке 21 изображены три изоморфных графа. На рисунке 22 изображены два неизоморфных графа.

Графы рассматриваются с точностью до изоморфизма, то есть рассматриваются классы эквивалентности по отношению изоморфизма.

Пример 71.

С точностью до изоморфизма существует ровно четыре простых графа с тремя вершинами и одиннадцать с четырьмя вершинами. Постройте эти графы.

Решение.

1. Построим четыре простых графа с тремя вершинами с точностью до изоморфизма (рис. 23):


2. Построим одиннадцать простых графов с четырьмя вершинами с точностью до изоморфизма (рис. 24):


Определение. Операция подразбиения (измельчения) дуги (u, v) в орграфе D = (V, E) состоит в удалении из Е дуги (u, v), добавлении к V новой вершины w и добавлении к Е | {(u, v)} двух дуг (u, v), (w, v). Аналогично определяется операция подразбиения ребра в графах.

Определение. Орграф D1 называется подразбиением орграфа D2, если орграф D1 можно получить из D2 путем последовательного применения операции подразбиения дуг. Аналогично определяется подразбиение графа.

Определение. Орграфы D1, D2 называются гомеоморфными, если существуют их подразбиения, являющиеся изоморфными.

<< | >>
Источник: Лекции - Дискретная математика. 2016

Еще по теме 3.1.2. Изоморфизм, гомеоморфизм:

  1. I. Генезис кризиса
  2. 5.3. Аналогия
  3. 2.1. Разностные множества и последовательности с двухуровневой ПАКФ
  4. 3.2. Метод изоморфных коэффициентов
  5. 3.3. Модель формирования конфликтологической культуры специалиста
  6. ВВЕДЕНИЕ
  7. Анализ и синтез.
  8. Гештальтпсихология
  9. Психологические теории мотивации
  10. 1.2. Регулирование внешней и внутренней среды предпринимательских структур как основа их устойчивого развития
  11. Изоморфизм и переходность явлений языка как системообразующие факторы.
  12. Содержание дисциплины
  13. 4.2. СОДЕРЖАНИЕ РАЗДЕЛОВ ДИСЦИПЛИНЫ
  14. ИЗОМОРФИЗМ И ГОМОМОРФИЗМ
  15. 4.2. СОДЕРЖАНИЕ РАЗДЕЛОВ ДИСЦИПЛИНЫ
  16. Изоморфизм графов