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

* * *

КЛАССИФИКАЦИИ И ИЕРАРХИИ

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

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

— рефлексивностью (каждый элемент эквивалентен сам себе);

— симметричностью (если а

связано с b, то b связано с а);

— транзитивностью (если а связано с b и b

связано с с, то а связано с с).

Граф, включающий подобные отношения, должен наглядно отражать эти свойства.

Еще один тип отношений — это отношения порядка, которые используются для упорядочивания элементов и обладают свойствами рефлексивности, транзитивности и антисимметричности (если а связано с b

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

Глава 5

Живительные способы применения графов

Если люди отказываются верить в простоту математики, то это только потому, что они не понимают всей сложности жизни.

Джон фон Нейман

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

Графы и интернет