40. Два графа являются изоморфными (т.Е. В определённом смысле одинаковыми), если между множествами их вершин существует взаимно-однозначное соответствие, которое сохраняет свойство смежности вершин.

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

Для изоморфизма графов необходимо и достаточно, чтобы матрицы смежности этих графов получались одна из другой одинаковыми перестановками строк и столбцов. Требуемая перестановка реализуется по правилу:

B=S*A*S-1 , где

А,В – матрицы смежности изоморфных графов

S – матрица перестановки

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

41. Маршрут в графе — это чередующаяся последовательность вершин и рёбер v0,e1,v1,e2,v2,...,ek,vk, в которой любые два соседних элемента инцидентны. Если v0 = vk, то маршрут замкнут, иначе открыт.

Цепь в графе — маршрут, все рёбра которого различны. Если все вершины (а тем самым и рёбра) различны, то такая цепь называется простой (элементарной). В цепи v0,e1,...,ek,vk вершины v0 и vk называются концами цепи. Цепь с концами u и v соединяет вершины u и v. Цепь, соединяющая вершины u и v обозначается . Для орграфов цепь называется орцепью.

Цикл — замкнутая цепь. Для орграфов цикл называется контуром.

42.

43.

44.

45.

46.