Том 11. Карты метро и нейронные сети. Теория графов - Клауди Альсина

· Discrete Mathematics.

· Journal of Graph Theory.

· Electronic Journal of Combinatorics.

* * *

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

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

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

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

Словарь

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

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

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

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

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

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

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

Грань — область, ограниченная ребрами плоского графа.

Граф — совокупность множества точек (вершин) и линий (ребер), соединяющих некоторые точки.

Дерево — связный граф, не содержащий циклов.

Дуга — ориентированное ребро графа. Изображается стрелкой.

Изоморфные графы — графы, между вершинами и ребрами которых существует взаимно однозначное соответствие, которое сохраняет смежность и инцидентность.

Критический путь — путь максимальной длины в ориентированном графе.

Лес — множество графов, которые являются деревьями.

Матрица инцидентности графа — матрица n x n чисел, элементы которой равны 1, если между соответствующими вершинами имеется ребро, и 0 в противном случае.

Метка — информация, присвоенная вершинам и ребрам графа; например, числа, слова, наименования.

Оптимальное решение — наилучшее решение (согласно некоему количественному показателю) из множества возможных решений.

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

Орграф (ориентированный граф) — граф, все ребра которого являются ориентированными, то есть дугами.

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

Петля — дуга или ребро, начало и конец которого находятся в одной и той же вершине.

Плоский граф — граф, ребра которого не имеют никаких общих точек, кроме вершин, в которых они сходятся.

Подграф — граф, содержащий некое подмножество вершин и ребер данного графа.

Полный граф — граф, в котором любая пара вершин соединена ребром.

Поток — некая величина, сопоставленная ребру, дуге или графу.

Путь — последовательность смежных ребер или дуг.

Раскраска графа — присвоение цветов вершинам, ребрам или граням графа при выполнении определенных условий.

Ребро — связь между двумя вершинами графа.

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

Сеть — граф, используемый для решения транспортных задач и задач распределения.

Смежные дуги — две дуги, имеющие общую вершину.

Смежные ребра — два ребра, имеющие общую вершину.

Степень вершины — количество ребер графа, сходящихся в данной вершине.

Траектория — то же, что и путь.

Узел — то же, что и вершина.

Цикл — путь, начало и конец которого находятся в одной и той же вершине.

Эйлеров граф — граф, в котором существует эйлеров цикл.

Эйлеров цикл — цикл, проходящий через каждое ребро графа ровно один раз.

Библиография

ALEXANDER, Ch., Ensayo sobre la síntesis de la forma, Buenos Aires, Infinito, 1976.

—: Tres aspectos de matemática у diseño, Barcelona, Tusquets, 1969.

AUSINA, C., Vitaminas matemáticas, Barcelona, Ariel, 2008.

—: у NELSEN, R.B., Math Made Visual. Creating Images for Understanding Mathematics, Washington, MAA, 2006.

BELTRAND, E.J., Models for Public Systems Analysis, Nueva York, Academic Press, 1977.

BERGE, C., Craphes, París, Gauthier-Villars, 1987.

—: Graphs and Hypergraphs, Amsterdam, North-Holland, 1973.

BURR, S., The mathematics of Networks, American Mathematical Society, Providence, R.I., 1982.

BUSACKER, R.G. у SAATY, T.L., Finite Graphs and Networks: An Introduction with Applications, Nueva York, McGraw-Hill, 1963.

CORIAT, M. et al., Nudos у nexos. Redes en la escuela, Madrid, Síntesis, 1989.

DE GUZMÁN, M., Cuentos con cuentas, Barcelona, Labor, 1983.

FERNÁNDEZ, J. у RODRFGUEZ, M.I., Juegos у pasatiempos para la enseñanza de la matemática elemental, Madrid, Síntesis, 1989.

FOULDS, L.R., Graph Theory Applications, Nueva York, Springer Verlag, 1992.

HARARY, F., Graph Theory у Reading, Addison-Wesley, 1994.

KAUFMANN, A., Puntos у flechas (teoría de los grafos). Barcelona, Marcombo, 1976.

ORE, O., Teoría у aplicación de los gráficos, Bogotá, Norma, 1966.

—: The Four Color Problem, Nueva York, Academic Press, 1967.

STEEN, L. (ed.), For all Practical Purposes: Introduction to Contemporary MathematicSy Nueva York, W.H. Freeman and Company, 1994.

WILSON, R., Four Colours Suffice: How the Map Problem Was Solved, Londres, Penguin Books Ltd., 2003.

WIRTH, N., Algoritmos у estructuras de datoSy México, Prentice-Hall Hispanoamericana, 1987.

* * *

Научно-популярное издание

Выходит в свет отдельными томами с 2014 года

Мир математики

Том 11

Клауди Альсина

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

РОССИЯ

Издатель, учредитель, редакция:

ООО «Де Агостини», Россия

Юридический адрес: Россия, 105066, г. Москва, ул. Александра Лукьянова, д. 3, стр. 1

Письма читателей по данному адресу не принимаются.

Генеральный директор: Николаос Скилакис

Главный редактор: Анастасия Жаркова

Старший редактор: Дарья Клинг

Финансовый директор: Наталия Василенко

Коммерческий директор: Александр Якутов

Менеджер по маркетингу: Михаил Ткачук

Менеджер по продукту: Яна Чухиль

Для заказа пропущенных книг и по всем вопросам, касающимся информации о коллекции, заходите на сайт www.deagostini.ru, по остальным вопросам обращайтесь по телефону бесплатной горячей линии в России:

8-800-200-02-01

Телефон горячей линии для читателей Москвы:

8-495-660-02-02

Адрес для писем читателей:

Россия, 170100, г. Тверь, Почтамт, а/я 245, «Де Агостини», «Мир математики»

Пожалуйста, указывайте в письмах свои контактные данные для обратной связи (телефон или e-mail).

Распространение:

ООО «Бурда Дистрибьюшен Сервисиз» УКРАИНА

УКРАИНА

Издатель и учредитель:

ООО «Де Агостини Паблишинг» Украина

Юридический адрес: 01032, Украина, г. Киев, ул. Саксаганского, 119

Генеральный директор: Екатерина Клименко

Для заказа пропущенных книг и по всем вопросам, касающимся информации о коллекции, заходите на сайт www.deagostini.ua, по остальным вопросам обращайтесь по телефону бесплатной горячей линии в Украине: