22. Маршруты, цепи(пути) и циклы в графах.

По аналогии с картой дорог мы можем рассматривать различные маршруты для графов, при этом актуальными мог оказаться вопросы типа: имеется ли маршрут начинающийся и заканчивающийся в одной и той же точке, который проходит ч/з заданное множество точек без прохождения 2-жды по 1-му и тому же пути (эта задача наз задачей Коробейника).

Опр: Последовательностью ребер длины n графа Г наз последовательность е1,е2,…,еn (необязательно все ребра различны) таких, что еi и еi+1 смежные ребра. Последовательность ребер определяется последовательностью вершин V1,V2,…,Vn. Где V1 начальная вершина, Vn – конечная.

Опр: Путь – это последовательность ребер, в которой все ребра различны. Если, к тому же, все вершины различны (за исключением может быть V1=Vn), то путь наз простым.

Опр: Последовательность ребер наз замкнутой, если V1=Vn.

Опр: Замкнутый простой путь, содержащий по крайней мере 1 ребро наз циклом.

Последовательность ребер графа – это такая последовательность, которую можно прочертить карандашом без его отрыва от бумаги, при этом допускается повторное прохождение ребер, многократное прохождение по петлям. Когда говор о пути, то наши возможности резко сужаются – не разрешается проходить по 1-му и тому же пути > 1-го раза (также исключается возможность прохождения по петле, т.к. вершину посещаем 2 раза).

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

23. Связные графы. Изоморфизм графов. Подграфы.

(связанные графы)

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

Опр: Граф называется связанным, если для любой пары различных вершин существует связывающий их путь.

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

2-е обстоятельство представляет собой суть максимального терма.

Максимальный терм: Если Ɛ – связанный подграф такой, что Г1<=Ɛ, то Ɛ=Г1, т.е. нет связанного подграфа Г, который > чем Г1.

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

См. вопрс №20).

Подграфы. Граф Н называется подграфом графа G, если множество вершин графа Н есть подмножество вершин графа G, и множество ребер графа Н есть подмножество ребер графа G: VH VG EH EG . Подграф Н называется оставным, если множество вершин VH=VG. Говорят, что подграф Н порожден вершинами VH VG, где VH не пустое, если он содержит те и только те дуги(ребра), оба конца которых принадлежат множеству VH. Очевидно, что если мы имеем матрицу смежности, то чтобы получить матрицу смежности подграфа, порожденного какими-то вершинами, нужно вычеркнуть соответствующие строки и столбцы матрицы исходного графа, тогда на пересечении этих строк и столбцов будет находиться матрица смежности графа, порожденного соответствующими вершинами.