Бинарные операции

Унарные операции

Добавление к G =(V, E) вершины v: G ₁=(V È{ v }, E)

Добавление к G =(V, E) дуги (v, w): G ₁=(V È{ v, w }, EÈ{(v, w)})

Удаление из G =(V, E) дуги (v, w): G ₁=(V, E \{(v, w)})

Удаление из G =(V, E) вершины v: G ₁=(V \{ v }, E \{(u, w)| u = v или w = v })

Отождествление в G =(V, E) вершин v и w (стягивание дуги (v, w))

Дополнение графа G =(V, E): G ₁=(V, E ')

Пусть заданы графы G ₁=(V ₁, E ₁) и G ₂=(V ₂, E ₂).

Пересечение графов G ₁=(V ₁, E ₁) и G ₂=(V ₂, E ₂):

, где .

Объединение графов G ₁=(V ₁, E ₁) и G ₂=(V ₂, E ₂):

.

Кольцевая сумма графов G ₁=(V ₁, E ₁) и G ₂=(V ₂, E ₂):

.

Соединение графов G ₁=(V ₁, E ₁) и G ₂=(V ₂, E ₂):

.

Произведение графов G ₁=(V ₁, E ₁) и G ₂=(V ₂, E ₂):

,

где .

Композиция графов G ₁=(V ₁, E ₁) и G ₂=(V ₂, E ₂):

,

гдетогда и только тогда, когда выполняется одно из условий:

1. ;

2. .

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

Определение. (n -куба Q_n)

1. Q ₀ – граф без петель, состоящий из одной вершины

2. Q ₁= K ₂

3. Q_n = K ₂´ Q_{n –1}, n >1

Обозначим вершины K ₂ символами 0 и 1. Тогда вершины n -куба кодируются всевозможными двоичными наборами длины n, а ребра соединяют вершины, кортежи которых отличаются ровно одной координатой.

Постройте Q ₂, Q ₃, Q ₄

Дата добавления: 2014-01-04