Изоморфные графы

Два графа, которые отличаются лишь нумерацией вершин и ребер называются изоморфными.

Они могут отличаться графическим изображением и матрицами смежности и инцидентности. Чтобы убедиться, что два графа - это один и тот же граф, необходимо и достаточно установить взаимно однозначные соответствия между ними.

Необходимые условия, чтобы два графа были изоморфными:

1. Имеют одинаковое количество вершин и ребер

2. Вершины графов имеют одинаковые степени.

Но выполнение этих свойств не является достаточным условием для изоморфизма графов.

Пример:Построить граф изоморфный графу из предыдущего примера.

1 3 5

 

 

2 4 6

Путь и цикл в графе

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

Циклом называется путь, у которого конечные и начальные вершины совпадают. Цикл называется простым, если он проходит через одну вершину один раз.

Длинной цикла называется количество ребер в нем.

Теорема о длине цикла:

Если у графа все простые циклы четной длины, то граф не имеет ни одного цикла нечетной длины.

 

Теорема:

Связный граф является простым циклом тогда и только тогда, когда все его вершины имеют степень 2.

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

Ребро АВ называется мостом, если при его удалении вершины А и В остаются несвязными.

Пример:

 

Здесь любое ребро является мостом

 

АВ – мост

- Мостов нет

 

Признаки мостов:

1. Ребро АВ является мостом, если АВ единственный путь, соединяющий вершину А с В.

2. АВ является мостом, когда ребро АВ не принадлежит ни одному циклу.

3. АВ. является мостом, если найдется две вершины С1 и С2 такие, что путь их соединяющий проходит через АВ.