Определение

Прямое произведение множеств.

Определение

Определение 1. Прямым произведением ⁾, или декартовым произведением ⁾ множеств и называется множество всех упорядоченных пар таких, что и . При этом используют следующее обозначение:

Пример 1.

§ Прямое произведение окружности и прямой — это цилиндр: ;

§ Прямое произведение двух прямых — это плоскость: ;

§ Прямое произведение двух окружностей — это тор: .

Определение 1'. Декартовым, или прямым произведением множеств называется множество упорядоченных пар

.

Проекции

Определение 2. Пусть — прямое произведение множеств . Отображение

называется проекцией на -й сомножитель.

Матрица смежности графа и ее свойства.

Определение

Матрица смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n) — это квадратная матрица A размера n, в которой значение элемента a_ij равно числу рёбер из i -й вершины графа в j -ю вершину.

Иногда, особенно в случае неориентированного графа, петля (ребро из i -й вершины в саму себя) считается за два ребра, то есть значение диагонального элемента a_ii в этом случае равно удвоенному числу петель вокруг i -й вершины.

Матрица смежности простого графа (не содержащего петель и кратных ребер) является бинарной матрицей и содержит нули на главной диагонали.

[править]Примеры

· Ниже приведён пример неориентированного графа и соответствующей ему матрицы смежности A. Этот граф содержит петлю вокруг вершины 1, при этом в зависимости от конкретных приложений элемент может считаться равным либо одному (как показано ниже), либо двум.

Граф	Матрица смежности

· a_ij — число рёбер, связывающих вершины и , причем в некоторых приложениях каждая петля (ребро при некотором ) учитывается дважды.

· Матрица смежности пустого графа, не содержащего ни одного ребра, состоит из одних нулей.