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

В разделе 5.1 мы определили ребро Е графа G (см. формулы (5.2), (5.1)) как элемент или точку (a,b) в произведении V×V. Пусть V={a₁,…,a_n}.

Совокупности элементов произведения V×V можно сопоставить квадратную матрицу М=(t_ij)_n×n, где каждой паре (a_i,a_j) соответствует пересечение i-ой строки с j-ым столбцом. Положим t_ij = 1, если в G вершины a_i и a_j соединены ребром и t_ij = 0 в противном случае. Таким образом, в случае графа с конечным числом вершин мы получим конечную матрицу смежности вершин M(G), которая полностью описывает G, если граф имеет однократные ребра.

Поскольку в неориентированном графе G (a,b)=(b,a), то можно положить t_ij= t_ji. Таким образом, неориентированным графам соответствуют симметрические матрицы смежности.

5.4. Cвязность

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

S = (E₁,…,E_q+1), (5.6)

что каждые два соседних ребра E_j, E_j+1.имеют общую концевую точку. Таким образом, можно написать

E₁=(b₁,b₂), …, E_j=(b_j,b_j+1),…,E_q= (b_q,b_q+1). (5.7)

Отметим, что одно и то же ребро Е может встречаться в маршруте несколько раз.

В дальнейшем рассматриваются только конечные маршруты, поэтому упоминание о конечности маршрута будем опускать; b₁ называется начальной вершиной S, b_q+1 – конечной.

Маршрут назовем нетривиальным, если он содержит хотя бы одно ребро; для систематичности рассуждений в теории графов вводится еще нуль-маршрут, не содержащий ребер. Если a₀, a_n – начальная и конечная вершины маршрута S, то можно написать

S = S(a₀,a_n) (5.8)

и назвать a₀ и а_n концевыми точками, или концами маршрута S. Будем говорить также, что S есть маршрут длины n, соединяющий а₀ и а_n. Если a₀ = а_n, то маршрут называется циклическим. Для двух вершин маршрута a_j,a_k, где j<k, подмаршрут S = S(a_j,a_k) называется участком S.

Маршрут называется цепью, а циклический маршрут – циклом, если каждое его ребро встречается в нем не более одного раза; вершины в цепи могут повторяться и несколько раз. Любой участок цепи есть цепь. Нециклическая цепь называется простой цепью, если в ней никакая вершина не повторяется.

Пусть граф G неориентированный. Две вершины a и b называются связанными, если существует маршрут вида (5.6) с концами a и b. Если S проходит через какую-нибудь вершину c более одного раза, то можно, очевидно, удалить его циклический участок, и при этом остающиеся ребра будут составлять маршрут S', связывающий a и b. Отсюда следует, что связанные маршрутом вершины связаны также простой цепью. Граф называется связным, если любая пара вершин связана.

5.5. Связные компоненты и максимальные клики

Если в произвольном графе G вершина a связана с b, а вершина b связана с вершиной c, то, очевидно, что a связана с вершиной c. Отношение связанности для вершин является отношением эквивалентности.

Подмножество W вершин графа G называется связным в графе G, если для любой пары вершин a_i, a_j из W существует маршрут S(a_i,a_j), состоящий из вершин множества W.

Связное множество является связной компонентой, если оно не является собственным подмножеством никакого другого связного множества.

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