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

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

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

Графическое представление отображения 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, присваиваемые парам элементов, сопоставляются ребрам графов. Иными словами, получается взвешенный граф.

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

Словарь

Алгоритм — пошаговая последовательность действий по решению задачи.

Вершина — точка графа, где сходится одно или более ребер; также может быть изолированной.

Вес — значение, поставленное в соответствие ребру графа, означающее стоимость, расстояние, время и пр.

Взвешенный граф — граф, каждому ребру которого поставлено в соответствие некоторое число.

Гамильтонов граф — граф, в котором существует гамильтонов цикл.

Гамильтонов цикл — цикл, содержащий все вершины графа ровно по одному разу.

Гомеоморфные графы — графы, один из которых получается из другого путем добавления или удаления вершин степени 2. Если в таких графах удалить все вершины степени 2, полученные графы будут одинаковыми.