Можно объяснить алгоритм двумя способами:

9) Метод поиска в ширину

Можно объяснить алгоритм двумя способами:

Первой вершине (родителю всех остальных вершин) приписываем метку 1. Рассматриваем все смежные с ней вершины и приписываем им метку 2. Дальше рассматриваем окружение вершин с меткой 2 и присваиваем метку 3 всем вершинам, кроме самой главной (родителя всех вершин).

Второй способ объяснения (по-моему, более понятнее, ну по крайней мере писать его легче) подразумевает под собой имитирование «горения» графа. Т.е. мы поджигаем самую первую вершину, дальше огонь перекидывается на смежные с ней вершины, с них на смежные с ними и т.д.

10) Матрицы, ассоциируемые с графами

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

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

В случае ориентированного графа каждой дуге <x,y> ставится в соответствие "-1" в строке вершины x и столбце дуги <x,y> и "1" в строке вершины y и столбце дуги <x,y>; если связи между вершиной и ребром нет, то в соответствующую ячейку ставится "0".

11) Деревья, Теорема о дереве. Следствие об этой теоремы

Дерево — это связный ациклический граф.

Лес – объединение деревьев. Лес может быть из одного дерева.

Теорема о дереве:

Для графа G верны следующие утверждения:

· Любые 2 несовпадающие вершины графа соединены единственное простой цепью.

· Лес обладает свойством что если какую-либо пару его несмежных вершин соединить ребром, то полученный граф будет содержать цикл.

12) Остов графа

Остовное дерево — ациклический связный подграф данного связного неориентированного графа, в который входят все его вершины. Неформально говоря, остовное дерево состоит из некоторого подмножества рёбер графа, таких, что из любой вершины графа можно попасть в любую другую вершину, двигаясь по этим рёбрам, и в нём нет циклов, то есть из любой вершины нельзя попасть в саму себя, не пройдя какое-то ребро дважды.

Алгоритм построения остова:

1. Нумеруем любую его вершину 0.

2. Все вершины, связанные с 0 нумеруем 1.

3. Вершины связанные с 1 нумеруем 2.

4. …

5. Разрушаем циклы.

13) Вершинная и реберная связность графа

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

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

14) Теорема о соотношении числами: числа реберной и вершинной связности графа

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

Для любого графа справедливо следующее неравенство:

Проверим второе неравенство. Если в графе нет ребер, то . Если ребра есть, то несвязный граф получаем из данного, удаляя все ребра, инцидентные вершине с наименьшей степенью. В любом случае .

Чтобы проверить первое неравенство нужно рассмотреть несколько случаев.

Если - несвязный или тривиальный граф, то .

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

Наконец, предположим, что граф содержит множество из ребер, удаление которых делает его несвязным. Ясно, что удаляя ребер из этого множества получаем граф, имеющий мост . Для каждого из этих ребер выберем какую-либо инцидентную с ним вершину отличную от и . Удаление выбранных вершин приводит к удалению (а возможно, и большего числа) ребер. Если получаемый после такого удаления граф не связен, то ; если же он связен, то в нем есть мост , и поэтому удаление вершины или приводит либо к несвязному, либо к тривиальному графу. В любом случае .

15) Теорема о двузначности графа. Двузначные графы

Дата добавления: 2015-10-21