Отношение эквивалентности. Классы эквивалентности. Свойства классов эквивалентности

Институт Мировой Экономики и Информатизации

Негосударственное Образовательное Учреждение Высшего Профессионального Образования

 

 

 

 

 

 

 

 

 

Контрольная работа по дисциплине «Дискретная математика»

 

 

 

 

 

 

 

 

 

 

 

 

 

Студент: Волченкова Виктория Александровна

 

Вариант 2

 

Вопрос 1. Отношение эквивалентности. Классы эквивалентности. Свойства классов эквивалентности.

Ответ:

Отношение эквивалентности представляет собой строгое математическое определение таких обыденных понятий, как обыденных понятий, как “одинаковость” или “неразличимость”. Обозначается  X˜Y. Отношение эквивалентности А в множестве М означает, что упорядочная пара(X,Y) принадлежит множеству АIM’M/

Отношение эквивалентности обладает следующими свойствами:

а.) Рефлексивности X˜Y;

б.)Симметричности:  если X˜Y,то Y˜X.

в.)Транзитивности: если X˜Y и Y˜Z, то X˜Z.

Важнейшее значение эквивалентности состоит в том, что это отношение определяет признак, который допускает разбиение множества M на непересекающиеся подмножества, называемые классами эквивалентности. И наоборот: всякое разбиение подмножества М на пересекающиеся подмножества определяет между элементами этого множества некоторое отношение эквивалентности.

 

Например: Отношение “учиться в одной школе”, заданное во множестве школьных классов этой школы, является эквивалентностью и разбивает это множество на непересекающиеся подмножества учеников, являющихся одноклассниками.

Классы эквивалентности состоят из всех тех элементов, которые неразличимы с точки зрения данного отношения эквивалентности. При этом каждый класс определяется его представителем(эталоном) и отождествляется с некоторым общим свойством или совокупности свойств входящих в него элементов.

 

Предельным случаем эквивалентности является Тождественное равенство. Очевидно, что  единственный элемент, тождественно равный какому-либо данному элементу, есть этот самый элемент. Следовательно, в данном случае имеем самое полное разбиение, при котором классы эквивалентности содержат только по одному элементу исходного множества.

 

Вопрос 2. Структура автоматов.

Ответ:

Структура автомата представляется собой сеть взаимосвязанных элементов , соответствующим i-моделям. Каждому элементу ставится в соответствии один из множества содержательно определенных символов. Связи между элементами характеризуются некоторым весом. Каждый элемент в любой момент времени описывается значением непрерывной величины возбуждения. На сети определенны операции передачи возбуждения между элементами установления новых связей , изменения веса связей(проторения и забывания), восприятия информации извне, выдачи информации(действия), а также операции усиления и торможения элементов, реализуемые специфической системой усиления торможения(СУТ), имитирующей механизм внимания . Сеть, составляющая описываемый автомат, может быть условно разделена на блоки приема приема информации, понятийных обобщений, памяти ситуаций, эмоций, желаний и действий.

Существенным критерием синтеза струтуры автомата является его простота, описываемая, например количеством элементов и связей между ними. Ввиду большой сложности синтеза автоматов при синтезе большее внимание уделяется минимизации комбинационной части последних.

 

Вопрос 3. Независимые множества. Клики в графе.

Ответ:

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

Кликой графа называется множество вершин, порождающее полный подграф, т.е множество вершин, каждые две из которых смежны. Число вершин в клике наибольшего размера называется кликовым числом графа и обозначается через w(G)

Очевидно , задача о независимом множестве преобразуется в задачу о клике и наоборот простым переходом от данного графа G к дополнительному графу G̅, так что а(G)=w(G̅).

 

Вопрос 4. Связность и компоненты графа.

Ответ:

 Вершина w орграфа D (графа G) достижима из вершины v, если либо v=w, либо существует путь из v в w(маршрут, соединяющий v и w)

Граф называется связным,  если для любых двух его вершин v,w существует простая цепь из v в w

Граф(орграф) называется связным(сильно связным), если для любых двух его вершин v,w существует маршрут(путь), соединяющий v,w(из   v и w)

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

Рассмотрим парочку примеров, где К – количество компонент связности.

 

                                                                                                                                                                                                                                             

 

 

 

 

 

 

Данный граф не является связным:  k=3

 

                                                                                                                             

 

 

 

 

 

 

 

Данный граф является связным K=0

Представим теорему: Пусть G- простой граф с n вершинами и k компонентами. Тогда число m его ребер удовлетворяет неравенствам

n-k≤m≤((n-k)(n-k+1))/2  

Cследовательно, что любой простой граф с n вершинами и более, чем (T-1)(T-2)/2 ребрами связен.