28. Подграфы и части графа. Операции над графами. N-Мерные кубы.

Граф G’=<M’,R’> называется подграфом графа G=<M,R>, если и . Граф G’ называется частью графа g, если и .

Операции над графом G=<M,R>:

1. Добавление вершины:

2. Добавление дуги:

3. Удаление вершины:

4. Удаление дуги:

5. Отождествление вершин:

6. Дополнением графа без петель G=<M,r> называется граф .

Двухместные операции над графами G₁=<M₁,R₁>, G₂=<M₂,R₂>:

1. Объединение: .

2. Пересечение: , если .

3. Кольцевая сумма: .

4. Соединение:

5. Произведение: , где

6. Композиция: , где . Т.е. каждая вершина a графа G₁ заменяется на изоморфную копию G_a графа G₂, а затем, если , то между любыми вершинами b₁ из G_a1 и b₂ из G_a2 проводится дуга (b₁,b₂).

Неорграф без петель называется полным, если его любые две различные вершины смежны. Полный граф, имеющий n вершин обозначается K_n.

Определим по индукции важный класс графов, называемых n-мерными кубами. Рассмотрим граф K₂, вершины которого обозначим 0 и 1. n-куб Q_n определяется по следующим правилам: Q₁=K₂, , n>1. Вершинами n-куба являются всевозможные n-ки, состоящие из наборов нулей и единиц (всего таких наборов 2ⁿ), а ребра задаются по следующему правилу: вершины смежны тогда и только тогда, когда соответствующие кортежи различаются ровно одной координатой.

29. Маршруты, циклы, цепи. Достижимость и связность (матрицы достижимости, контрдостижимости, связности).

Пусть G=<M,R> - граф. Последовательность a₁,u₁,a₂,u₂,…,u_n,a_n+1, где , называется маршрутом, соединяющим вершины a₁ и a_n+1, если u_i=(a_i,a_i+1). Число n дуг в маршруте называется его длиной.

Пусть G – неорграф. Маршрут (a₁,a_n+1) называется цепью, если все ребра [a₁,a₂],…,[a_n,a_n+1] различны, и простой цепью, если все его вершины, кроме, возможно, первой и последней, различны. Маршрут называется циклическим, если a₁=a_n+1. Циклическая цепь называется циклом, а циклическая простая цепь – простым циклом.

Пусть G – орграф. Маршрут называется путем, если все его дуги различны. Путь называется контуром, если a₁=a_n+1. Граф, не имеющий контура, называется бесконтурным. Вершина b называется достижимой из вершины a, если существует (a,b) – путь.

Неорграф называется связным, если любые две его несовпадающие вершины соединены маршрутом. Граф G называется связным, если соответствующий ему неорграф F(G) тоже является связным. Граф G называется сильно связным, если для каждой пары различных вершин a и b существуют (a,b)-маршрут и (b,a)-маршрут. Аналогично определяются понятия связности и сильной связности для мультиграфов.

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

Теорема: Любой граф представляется в виде объединения непересекающихся связных (сильных) компонент. Разложение графа на связные (сильные) компоненты определяется однозначно.

Теорема: Если A_G – матрица смежности графа G, то (i,j)-й элемент матрицы есть число (a_i,a_j)-маршрутов длины k.

Следствие: 1) В графе G мощности n тогда и только тогда существует (a_i,a_j)-маршрут (a_i≠a_j), когда (i,j)-й элемент матрицы не равен нулю.

2) В графе G мощности n тогда и только тогда существует цикл, содержащей вершину a_i, когда (i,i)-й элемент матрицы не равен нулю.

Образуем из матрицы (b_ij)=E+A_G+A_G²+…+A_G^n-1 матрицу C=(c_ij) порядка n по следующему правилу: . Матрица С называется матрицей связности, если G – неорграф, и матрицей достижимости, если G-орграф.

Определим матрицу контрдостижимости Q=(q_ij): . Причем Q=C^T.

Рассмотрим матрицу сильных компонент S=C*Q, где операция * означает поэлементное произведение матриц С и Q: s_ij=c_ij•q_ij. Таким образом, матрица S является матрицей отношения эквивалентности E: выполнимо a_iEa_j тогда и только тогда, когда a_i и a_j находятся в одной сильной компоненте.