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

Граф, заданный аналитически, изображается Разными диаграммами, имеющими Одинаковое число вершин и Одинаковое число ребер.

Определение. Графы и называются Изоморфными, если существует биективное отображение , сохраняющее отношение смежности вершин графа.

Для обозначения изоморфности графов используется символ «».

Теорема 2. .

Теорема 3. Изоморфизм графов является отношением эквивалентности на множестве V.

Доказательство.

1) , так как тождественное отображение является биективным;

2) , так как для биективного отображения существует единственное обратное отображение;

3) , так как композиция биективных отображений является биективным отображением.

Изоморфизм графов обладает свойствами рефлексивности, симметричности и транзитивности. Значит, является отношением эквивалентности на множестве графов. ■

Следовательно, отношение изоморфизма является разбиением множества всех графов на классы эквивалентности.

Поэтому в дискретной математике изоморфные графы не различаются.

Например, на рис. 3 приведены диаграммы графов, изоморфных графу рис. 1: , ; , ; , .

Рис. 3. Изоморфные графы

Общего правила, устанавливающего изоморфизм графов, в дискретной математике нет.

3адачи и упражнения

5. Постройте диаграммы графов, изоморфных графам задачи 4.1.

6. Найдите пару изоморфных графов по заданным диаграммам трёх графов:

< Предыдущая		Следующая >