Отношение эквивалентности.

Отношение эквивалентности (~) на множестве X — это бинарное отношение, для которого выполнены следующие условия:

1. Рефлексия: a ~ a для любого a в X,

2. Симметричность: если a ~ b, то b ~ a,

3. Транзитивность: если a ~ b и b ~ c, то a ~ c.

Запись вида «a ~ b» читается как «a эквивалентно b».

Отображения множеств.

Если каждому элементу x множества X поставлен в соответствие ровно один элемент ƒ(x) множества Y, то говорят, что задано отображение ƒ из множества X в множество Y.

При этом, если ƒ(x)=y, то элемент y называется образом элемента x при отображении ƒ, а элемент x называется прообразом элемента y при отображении ƒ.

Обозначение: ƒ: X→Y.

Функция – взаимно-однозначное отображение одного множества на другое.

Основные понятия и определения теории графов.

Граф - система, которая интуитивно может быть рассмотрена как множество кружков и множество соединяющих их линий.

Кружки называются вершинами графа, линии со стрелками - дугами, без стрелок - ребрами.

Граф, в котором направление линий не выделя­ется (все линии являются ребрами), называется неориентирован­ным;

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

Смешанный граф — это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые — неориентированными

Для любого графа есть матрица смежности.

Петля – дуга, которая соединяет вершину саму с собой. Петля при подсчете степени вершины берется дважды!!!!!

Планарный граф – все точки лежат в одной плоскости.

Раскрашенные графы – вершины при соединении красятся в разные цвета.

ПОЛНЫЙ ГРАФ – такой граф, все вершины которого соединены друг с другом ребрами.

Начало теории графов датируют 1736 г, когда Л. Эйлер решил популярную в то время «задачу о кенигсбергских мостах». Термин «граф» впервые был введен спустя 200 лет (в 1936) Д. Кенигом.

Не нашли, что искали? Воспользуйтесь поиском: