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

В теории графов изоморфизмом графов и называется биекция между множествами вершин графов такая, что любые две вершины и графа смежны, тогда и только тогда, когда вершины и смежны в графе . Здесь графы понимаются неориентированными и не имеющими весов вершин и ребер. В случае, если понятие изоморфизма применяется к ориентированным или взвешенным графам, накладываются дополнительные ограничения на сохранение ориентации дуг и значений весов. Если изоморфизм графов установлен, они называются изоморфными и обозначаются как . Иногда биекция записывается в виде подстановки изоморфизма . Некоторые задачи обработки графов требуют не только проверки изоморфизма, но и выяснения его подстановки.Отношение изоморфизма графов представляет собой отношение эквивалентности, определенное для графов, и позволяет произвести разбиение исходного класса всех графов наклассы эквивалентности. Множество графов, изоморфных друг другу, называется классом изоморфизма графов (англ.), их число в зависимости от представляет собой последовательность A000088 в OEIS (1, 1, 2, 4, 11, 34, 156, 1044, 12346,...).

В случае, если биекция отображает граф сам на себя (графы и совпадают), она называется автоморфизмом графа .

38.Матрицы и циклы в неориентированном графе. Для алгебраического задания графов используются матрицы смежности и инцидентности. Матрица смежности A = ( a_ij) определяется одинаково для ориентированного и неориентированного графов. Это квадратная матрица порядка n, где n - число вершин, у которой: a_ij = Для неориентированного графа матрица инцидентности B задается следующим образом: b_i =

Пусть G - неориентированный граф. Маршрутом или цепью в G называется такая последовательность (конечная или бесконечная) ребер a ₁, a ₂,... a_n..., что каждые соседние два ребра a_i и a_{i+ 1} имеют общую инцидентную вершину. Одно и то же ребро может встречаться в маршруте несколько раз Длиной (или мощностью) маршрута называется число ребер, входящих в маршрут, причем каждое ребро считается столько раз, сколько оно входит в данный маршрут. Замкнутый маршрут называется циклом. Маршрут (цикл), в которой все ребра различны, называется простой цепью (циклом). Маршрут (цикл), в которой все вершины, (кроме первой и последней), различны, называется элементарной цепью (циклом).

39.Пути и контуры в ориентированном графе. Путем ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей дуги. Число дуг пути называется длиной пути. Путь называется контуром, если его начальная вершина совпадает с конечной вершиной. Путь (контур), в котором все дуги различны, называется простым. Путь (контур), в котором все вершины, кроме первой и последней, различны, называется элементарным

40.Связость графа. Неориентированный граф называется связным, если каждая пара различных вершин может быть соединена по крайней мере одной цепью.

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

41. Экстремальные пути в нагруженных ориентированных графах. Ориентированный граф называется нагруженным, если дугам этого графа поставлены в соответствие веса, так что дуге (x_i,x_j) сопоставлено некоторое число c (x_i,x_j) = c_ij, называемое длиной ( или весом, или стоимостью дуги ). Длиной (или весом или стоимостью) пути s, состоящего из некоторой последовательности дуг (x_i,x_j), называется число l (s), равное сумме длин дуг, входящих в этот путь, т.е. l (s) = Е c_ij, причем суммирование ведется по всем дугам (x_i, x_j) s. Матрица C = (c_ij) называется матрицей длин дуг или матрицей весов.

Для ненагруженного графа введем понятие кратчайшего пути. Это путь с минимальным общим числом дуг, причем каждая дуга считается столько раз, сколько она содержится в этом пути В общем случае задача решается с помощью алгоритмов Флойда, Форда, Беллмана Алгоритмы нахождения минимального пути могут быть использованы для поиска кратчайших путей в ориентированном графе без контуров. Для этого нужно каждой дуге приписать вес, равный единице.

42.Алгоритм Форда – Беллмана нахождения минимального пути