Г енерация перестановок.

VII. Графы

1. Определение графа. Виды задания графов. Смежность и инцидентность. Вектор степеней графа.

О пределение графа.

Если (u,v) ребро, то u и v наз. концами ребра. Пары одинаковых элементов (u,u) наз. петлями, а одинаковые пары наз. кратными ребрами. Пары в наборе V могут быть упорядоченными и неупорядоченными. Упорядоченная пара (u,v) наз. дугой, u начало дуги, v начало дуги

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

Способы задания графов. Смежность и инцидентность.

Вектор степеней графа.

Число ребер, сходящихся в вершине графа, называется степенью (порядком) s (G, x) вершины х в графе G = (X, U), или число ребер инцидентных этой вершине. При изоморфизме двух графов соответствующие друг другу вершины должны иметь одинаковую степень вершин. Упорядоченную систему степени его вершин называют вектором степеней графа G и кратко обозначают s (G).

VII. Графы

7. Операции над графами. Дополнение, сумма, произведение, модульное произведение графов. Теорема о модульном произведении графов (без доказательства).

Операции над графами.

Дополнение.

Сумма.

Произведение.

Модульное произведение графов. Теорема о модульном произведении графов (без доказательства).

Ещё несколько операций на всякий.