Примеры решения задач

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

Решение. Для того чтобы отношение Г было отношением эквивалентности, необходимо, чтобы оно было рефлексивным, симметричным, транзитивным.

1. Так как каждый человек живет сам с собой на одной улице, то lГl выполняется, а значит отношение Г – рефлексивно.

2. Так как из того, что человек l₁ живет на одной улице с человеком l₂ следует, что и l₂ живет на одной улице с l₁, т.е. из l₁Гl₂  l₂Гl₁, то значит отношение Г – симметрично.

3. Очевидно, что из l₁Гl₂ и l₂Гl₃ следует l₁Гl₃.

Таким образом, отношение Г – отношение эквивалентности.

Задача 2. Пусть А=R – множество действительных чисел. Введем на R отношение Г: хГу, если ху. Проверить, является ли отношение Г отношением порядка.

Решение. 1. Проверим на рефлексивность. Так как хГх выполняется , т.е. хх, то Г – рефлексивно. 2. Проверим на симметричность. Так как из хГууГх только в случае, когда х=у (ху, ух х=у), то отношение Г – асимметрично. 3. Проверим на транзитивность. Так как из хГу, уГzхГz (ху, уzхz), то отношение Г – транзитивно.

Из 1.-3. следует, что Г – отношение нестрогого порядка, а значит, отношение Г является отношением порядка.

Задачи для самостоятельного решения

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

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

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

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

Тема 2. Теория графов

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

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

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

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

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

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

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

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

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

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

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

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

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