Том 11. Карты метро и нейронные сети. Теория графов

Графическое представление отображения f, связывающего множества {a, b, с, d} и {1, 2, 3, 4}.

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

Инъективное отображение.

Сюръективное отображение.

Биективное отображение.

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

Дерево возможных отображений множества A = {a, b} на множество B = {1, 2, 3, 4}.

Если даны два отображения — отображение f множества А на множество В и отображение g множества В на множество С, то имеет смысл говорить о композиции отображений f и g множества А на множество С, то есть о присвоении каждому элементу а множества А элемента g (f(а)) множества С. Композиции отображений g и f обозначается как g о f. Ее можно представить в виде графов следующего вида.

Граф композиции отображений q и f.

Нечеткие множества и графы

В последние десятилетия в целях моделирования сложных ситуаций реальной жизни все шире применяется теория нечетких множеств, созданная инженером Калифорнийского университета в Беркли Лотфи Заде. В классической трактовке элемент а либо принадлежит множеству А, либо нет. Следовательно, множество определяется характеристической функцией: она принимает значение 1 для элементов, принадлежащих A, и 0 для элементов, не принадлежащих A.

Идея Заде состояла в том, чтобы расширить характеристические функции и создать нечеткие множества, то есть определить функции, которые ставят в соответствие элементам x универсального множества X значения f(х) в интервале от 0 до 1. В такой трактовке f(х) определяет степень принадлежности х к А.

Нечеткие множества, соответствующие утверждению «результат примерно равен 1».

* * *

ЖУРНАЛЫ О ДИСКРЕТНОЙ МАТЕМАТИКЕ, КОМБИНАТОРИКЕ И ГРАФАХ

Ниже перечислены ведущие современные журналы по этим темам.

· Ars Combinatorica.

· European Journal of Combinatorics.

· Combinatorica.

· Geombinatorics.

· Combinatorics, Probability and Computing.

· Journal of Algebraic Combinatorics.

· Designs, Codes and Cryptology.

· Journal of Combinatorial Theory. Series A.

· Discrete and Computational Geometry.

· Journal of Combinatorial Theory. Series B.

· Discrete Applied Mathematics.

· Journal of Geometry.

· Discrete Mathematics.

· Journal of Graph Theory.

· Electronic Journal of Combinatorics.

* * *

Одному и тому же расплывчатому понятию можно сопоставить разные нечеткие множества. Именно это и вызывает интерес к теории нечетких множеств — она допускает альтернативные трактовки одной и той же ситуации. Задачи искусственного интеллекта, управления механизмами, обработки цифровых фотографий, распознавания образов и другие задачи (даже стиральные машины с нечеткой логикой) — прекрасные наглядные примеры того, как эта теория используется на практике. Введение степеней — очень важная идея, ведь между черным и белым существует множество оттенков серого.

В рамках теории нечетких множеств также рассматриваются нечеткие классификации и упорядоченность; можно говорить о степенях отношений. Эта теория основана на теории множеств и может быть подтверждена примерами из теории вероятностей (вероятность является оценкой какого-либо события и лежит в интервале от 0 до 1), но особенно интересна в эмпирических моделях и при решении задач, на которые нельзя дать четкого и однозначного ответа в рамках классической математики.

В частности, в теории нечетких множеств тоже используются графы отношений, но в этом случае значения от 0 до 1, присваиваемые парам элементов, сопоставляются ребрам графов. Иными словами, получается взвешенный граф.