Подграфы и части графа. Операции над графами. 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ⁿ), а ребра задаются по следующему правилу: вершины смежны тогда и только тогда, когда соответствующие кортежи различаются ровно одной координатой.