Задать вопрос юристу

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. 9. Непрерывное отображение. Гомеоморфизм
  2. Изоморфизм графов
  3. ИЗОМОРФИЗМ И ГОМОМОРФИЗМ
  4. Изоморфизм и переходность явлений языка как системообразующие факторы.
  5. 5. Изоморфизм и изометрия сепарабельных гильбертовых пространств. Общий вид линейного функционала в гильбертовом пространстве. Теорема Рисса-Фишера.
  6. ЭКВИВАЛЕНТНОСТЬ
  7. Изоморфные и изометричные линейные нормированные пространства
  8. 2. Конечномерные пространства. Конечномерность и компактность. Теорема Рисса о локальной компактности.
  9. ГОМОМОРФИЗМ
  10. Непрерывные отображения.
  11. 2. Теорема о пополнении метрического пространства
  12. АНАЛОГИЯ
  13. МОДЕЛЬ
  14. ЛОГИКА КЛАССОВ
  15. Примечания.
  16. 3.2. Метод изоморфных коэффициентов