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

Изоморфизм графов

Легко подсчитать число графов с фиксированным множеством вершин V. Эти графы различаются своими ребрами, и поэтому их число равно количеству подмножеств множества V´V, т.е. , где п = | V |.

Однако эти графы на всегда следует различать. Как в применении теории графов, так и в самой этой теории чаще существенно лишь то, что есть объекты (вершины графа) и связи между объектами (ребра графа). С этих позиций графы, которые получаются один из другого изменением наименований вершин, разумно не различать. Такие графы называются изоморфными.

Пусть G и Н – графы, а – биекция. Если для любых вершин и и v графа G их образы и смежны в Н тогда и только тогда, когда и и v смежны в G, то эта биекция называется изоморфизмом графа G на граф Н. Если такой изоморфизм существует, то мы пишем и говорим, что графы G и Н изоморфны.

Пример 1. Графы, представленные на рис. 2.8 изоморфны, указана соответствующая изоморфизмам нумерация вершин. Графы на рис. 2.9 неизоморфны (например, вследствие того, что в первом графе есть циклы из трех ребер, а во втором их нет).

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

оно симметрично, рефлексивно и транзитивно. Следовательно, все графы разбивается на классы так, что графы из одного класса попарно изоморфны, а графы из разных классов не изоморфны. Изоморфные графы естественно отождествлять, т.е. считать совпадающими (их можно изобразить одним рисунком). Они могли бы различаться конкретной природой своих элементов, но именно это игнорируется при введении понятия графа. Класс изоморфных графов принято называть абстрактным графом.

В некоторых случаях приходится различать изоморфные графы. Граф порядка п называется помеченным, если его вершинам присвоены некоторые метки, например, номера 1, 2, …, п. Отождествив каждую из вершин графа с ее номером (а, следовательно, множество вершин – с множеством чисел {1, 2, …, п}), определим равенство графов G и Н одного и того же порядка: G = Н тогда, когда ЕG = ЕН. На рис. 2.10 изображены три разных помеченных графа.

Число gn помеченных графов порядка п определяется сложно. Известна формула Пойа

,

дающая асимптотику числа gn. Эта формула означает, что две функции g(п)=gn и f(n)= асимптотически равны, т.е. .

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

Еще по теме Изоморфизм графов:

  1. 3.1.2. Изоморфизм, гомеоморфизм
  2. ИЗОМОРФИЗМ И ГОМОМОРФИЗМ
  3. Изоморфизм и переходность явлений языка как системообразующие факторы.
  4. В.Н. Бурков, Д.А. Новиков. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ, 2001
  5. 6.2.2 Применение теории графов
  6. 3. ТЕОРИЯ ГРАФОВ
  7. 3.1. Элементы теории графов
  8. 1. Основные понятия теории графов
  9. 3.1.4. Примеры графов. Операции над графами
  10. Матрицы графов.
  11. 3.3.3. Минимальные остовные деревья нагруженных графов
  12. ряд примеров приложений теории графов.
  13. 3.1.3. Матричное задание графов. Матрицы смежности, инцидентности
  14. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
  15. §2.2. Способы задания графов
  16. §2.4. Раскраски графов. Планарность
  17. 2 Элементы теории графов
  18. 2.4. Графово-матричное представление взаимодействия популяций