Матрица инцидентности.

Задание графа

Связность

Если для двух вершин существует цепь, то они называются связанными. Граф называется связным, если у него все вершины связны. Таким образом, если граф не связан. то из него можно выделить связные подграфы, называемые компонентами связности..

Рис. 35. Связный граф

Рис.36. Граф с двумя компонентами связности

1. Матрица смежности.

Матрица инцидентности устанавливает связь вершин и инцидентных с ней ребер.

b_ij =

Пример V l ₂ V

l ₁

l ₃

V1 V4

Матрица инцидентности

V V V V4

Рис.38. Задание графа матрицей инцидентности

4. Список смежности.

В списке смежности нужно указывать вершину и смежные с ней вершины.

V (V, V);

V (V, V);

V(V, V, V);

V(V, V);

V(V, V);

V(V, V, V);

V(V);

V(V);

Рис. 39. Задание графа списком смежности

Задание графа в виде списка смежности полезно при решении задачи обхода всех вершин графа: обследовать все вершины графа, побывав в каждой 1 раз.

Различают два метода решения этой задачи:

1) Поиск в глубину.

2) Поиск в ширину.

При поиске в глубину некоторая вершина выбирается в качестве начальной и помечается. Затем рассматривается список смежности этой вершины и из него выбирается первая вершина и помечается (какая-то вершина U). Рассматривается список смежности для вершины U. Выбирается первая вершина (W) и помечается. Рассматриваем список смежности для W, и так далее пока не столкнемся со случаем, что вершины списка помечены. Возвращаемся в вершину U и выбираем не помеченную вершину, если такая есть. Продвигаемся в этом направлении до тех пор, пока список вершины не оказывается помеченным. Опять возвращаемся назад и так далее. В итоге все вершины будут помечены.

Пример: См. рис. 39

Пусть начальная вершина ─ V(метка 1). В списке смежности вершины Vчислится V(метка 2). В списке смежности V─ вершина V(метка 3). В списке смежности вершины Vимеются вершины V,V,V.

Vуже помечена. Из Vследуем в V(метка 5). VV ( метка 6). Аналогично, VV(метка 7). Теперь возвращаемся в V. Все вершины помечены. Аналогично и в V,V, V. В списке смежности Vимеется непомеченная вершина ─ V(метка 8). В списке Vвсе вершины помечены. Возвращаемся в V. Здесь тоже все помечены. Следовательно, обход графа завершен. См. рис. 40

Рис. 40. Граф с помеченными вершинами при обходе в глубину

Приведенный нами алгоритм убеждает в справедливости теоремы:

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

Замечание:

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

Поиск в ширину. Смысл поиска в ширину заключается в том, что некоторую вершину V мы объявляем начальной ─ V. Перебираем весь список смежности этой вершины. Когда список исчерпан, т.е. все вершины, достижимые из V, помечены, мы переходим к первой вершине из помеченных. Затем, исчерпав список этой вершины, переходим ко второй вершине из первых помеченных и так далее до тех пор, пока не останется непомеченных вершин.

Пример: См. рис. 41.

Пусть V₇ (метка 1) ─ начальная вершина. В списке смежности у вершины Vвершина V₆ (метка 2). Больше нет вершин в списке смежности V. Переходим в V. V(V, V, V). Назначаем метку вершине V(метка 3). V─ помечена, V( метка 4). Список вершины Vисчерпан. Переходим в вершину V(V, V, V). Вершины V(метка 5), V(метка 6). Возвращаемся в список вершины V. Вершины Vи V─ помечены. Возвращаемся в V, и переходим затем в вершину V: V(V, V). V(метка 7). Возвращаемся в Vи переходим в V. V(V, V). Переходим в V. Все вершины из списка Vпомечены. Переходим в V. Список V─ помечен. Непомеченных вершин не осталось. Поиск в ширину закончен.

Рис 41. Метки вершин графа при поиске в ширину

Ясно, что последовательность поиска в глубину и в ширину зависит от выбора V.