![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Задача 1. На множестве L людей задано отношение Г «быть одной группы крови» Проверить, является ли оно отношением эквивалентности. Что служит классом эквивалентности?
Задача 2. На плоскости хОу рассмотрим отношение Г: (х1, у1) Г (х2, у2), если выполнено х1+ у1= х2+ у2. Является ли оно отношением эквивалентности? Что служит классом эквивалентности?
Задача 3. На плоскости хОу рассмотрим отношение Г: (х1, у1) Г (х2, у2), если выполнено х1>x1, y2> у2. Является ли оно отношением порядка?
Задача 4. На множестве людей рассмотрим отношение «быть одной национальности». Является ли оно отношением эквивалентности?
ТЕМА 2. ТЕОРИЯ ГРАФОВ
Основные понятия теории графов: графы, ориентированные и неориентированные графы, пути, маршруты, циклы
Представим на плоскости конечное множество точек V и некоторое множество линий Х, соединяющих попарно какие-то точки из V. Например, схема автодорог, соединяющих населенные пункты Брянской области.
Множество точек (населенных пунктов) назовем множеством вершин, а соединяющие линии (автодороги) – множеством ребер. Совокупность двух множеств (вершин и ребер) называют графом.
На некоторых участках допускается только одностороннее движение. Тогда соответствующее ребро называется дугой и изображается стрелкой, направленной от начальной вершины к конечной.
Граф, состоящий из дуг, называют ориентированным (или просто орграфом), а образованный ребрами – неориентированным.
Один и тот же граф можно изобразить по разному. Вершины можно располагать по своему усмотрению и произвольно выбирать форму соединяющих линий.
Ребро, концевые вершины которого совпадают, называется петлей. Ребро с одинаковыми концевыми вершинами называются кратными. Изолированная вершина не соединена с другими вершинами.
Часто на графе требуется выделить различные маршруты, обладающие определенными свойствами.
Маршрут длины m – это последовательность х 1,…, хm m ребер графа (не обязательно различных) таких, что любые два соседних ребра xi, xi+ 1 имеют общую концевую вершину.
Замкнутый маршрут приводит в ту же вершину, из которой он начался.
Цепь – это маршрут, все ребра которого различны.
Простая цепь – это цепь без повторяющихся вершин. Замкнутая цепь называется циклом. Простой цикл – это простая замкнутая цепь.
В случае «орграфа» слово «цепь» заменяется на «путь», а «цикл» на «контур».
Дата публикования: 2015-10-09; Прочитано: 494 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!