Б и н а р н ы х о т н о ш е н и й

Отношения порядка и эквивалентности позволяют создать модель такого важного вида деятельности, как принятие решений (выбор). Выбор приходится осуществлять очень часто и в самых различных ситуациях – от бытовых случаев до проектирования сложных технических систем. Бинарные отношения позволяют сравнивать между собой различные варианты (которые называются альтернативами), являющиеся элементами множества X, и выбирать из двух более предпочтительную альтернативу. Так, в случае конечных множеств X удобно находить наилучшие альтернативы с помощью графа предпочтений, стрелки которого направлены в сторону менее предпочтимой альтернативы (рис. 1.26). Выделенные вершины графа, из которых ребра (стрелки) только выходят (на рисунке это альтернативы 1 и 5), – это так называемые недоминируемые (наилучшие) альтернативы.

Рис. 1.26. Пример графа предпочтений

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

Графы

Поскольку все структурные модели имеют нечто общее, можно, абстрагировавшись от содержания, получить схемы, на которых формально обозначены только имеющиеся в наличии элементы и связи между ними, с учетом различий в элементах и связях, если это необходимо. Такие общие, универсальные с математической точки зрения схемы носят название графов. Графы уже использовались выше в модели структуры при задании бинарных отношений. Напомним, что граф состоит из обозначений элементов произвольной природы, которые называются вершинами(им на изображении графа соответствуют кружки), и обозначений связей между вершинами, которые называются ребрами, или дугами.Им соответствуют линии со стрелками или без них, соединяющие вершины между собой (рис. 1.27).

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

Две вершины могут быть соединены любым количеством ребер.

Рис. 1.27. Пример графа для четырех элементов

Если вершина соединена сама с собой (вершина x на рис. 1.27), то ребро называется петлейи соответствует рефлексивному отношению. Если вершина не соединена с другими, то она называется изолированной(вершина f на рис. 1.27). Иногда бывает нужно отразить в графе различия между элементами или связями, тогда либо разным ребрам или вершинам присваиваются разные значения (веса) – в этом случае граф называется взвешенным, либо вершины и ребра окрашивают в разный цвет (раскрашенные графы) и т.п.

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

Более подробно о графах можно узнать из Приложения 2, помещенного в конце данного учебного пособия.

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

а) линейная; б) древовидная (иерархическая); в)матричная; г)сетевая; д) кольцевая; е) звездообразная.