Задачи для самостоятельного решения. Задача 1. На множестве l людей задано отношение г «быть одной группы крови» Проверить, является ли оно отношением эквивалентности

Задача 1. На множестве L людей задано отношение Г «быть одной группы крови» Проверить, является ли оно отношением эквивалентности. Что служит классом эквивалентности?

Задача 2. На плоскости хОу рассмотрим отношение Г: (х₁, у₁) Г (х₂, у₂), если выполнено х₁+ у₁= х₂+ у₂. Является ли оно отношением эквивалентности? Что служит классом эквивалентности?

Задача 3. На плоскости хОу рассмотрим отношение Г: (х₁, у₁) Г (х₂, у₂), если выполнено х₁>x₁, y₂> у₂. Является ли оно отношением порядка?

Задача 4. На множестве людей рассмотрим отношение «быть одной национальности». Является ли оно отношением эквивалентности?

ТЕМА 2. ТЕОРИЯ ГРАФОВ

Основные понятия теории графов: графы, ориентированные и неориентированные графы, пути, маршруты, циклы

Представим на плоскости конечное множество точек V и некоторое множество линий Х, соединяющих попарно какие-то точки из V. Например, схема автодорог, соединяющих населенные пункты Брянской области.

Множество точек (населенных пунктов) назовем множеством вершин, а соединяющие линии (автодороги) – множеством ребер. Совокупность двух множеств (вершин и ребер) называют графом.

На некоторых участках допускается только одностороннее движение. Тогда соответствующее ребро называется дугой и изображается стрелкой, направленной от начальной вершины к конечной.

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

Один и тот же граф можно изобразить по разному. Вершины можно располагать по своему усмотрению и произвольно выбирать форму соединяющих линий.

Ребро, концевые вершины которого совпадают, называется петлей. Ребро с одинаковыми концевыми вершинами называются кратными. Изолированная вершина не соединена с другими вершинами.

Часто на графе требуется выделить различные маршруты, обладающие определенными свойствами.

Маршрут длины m – это последовательность х ₁,…, х_m m ребер графа (не обязательно различных) таких, что любые два соседних ребра x_i, x_{i+ 1} имеют общую концевую вершину.

Замкнутый маршрут приводит в ту же вершину, из которой он начался.

Цепь – это маршрут, все ребра которого различны.

Простая цепь – это цепь без повторяющихся вершин. Замкнутая цепь называется циклом. Простой цикл – это простая замкнутая цепь.

В случае «орграфа» слово «цепь» заменяется на «путь», а «цикл» на «контур».