Спирина, М.С. Дискретная математика

Г л а в а 2 ГРАФЫ В этой главе описывается еще один универсальный и нагляд­ ный язык, графический, который применяется во многих облас­ тях науки и техники. Знакомство с элементами теории графов о г ­ раничится определениями и иллюстрациями к основным положе­ ниям этого раздела математики. Теория графов дает исключительно удобный аппарат для моделирования структурных свойств различ­ ных систем и отношений между объектами разной природы, в том числе программных моделей. 2.1. Основные понятия и определения графа и его элементов Так о великих вещах помогают со­ ставить понятье Малые вещи, пути намечая для их постижения. Лукреций Впервые понятие «граф» ввел в 1936 г. венгерский математик Денни Кёниг. Но первая работа по теории графов принадлежала перу великого Леонарда Эйлера и была написана еще в 1736 г. С помощью графов изображаются схемы различных дорог, линии воздушных сообщений, газопроводов, теплотрасс, электросетей, а также микросхемы, дискретные многошаговые процессы, с и ­ стемы различных бинарных отношений, химические структурные формулы и другие диаграммы и схемы. Применяются графы для решения задач химии, экономики, электротехники и автоматики. Также они широко используются в информатике и строительстве. Без графов сложно анализировать классификации в различных науках. Графом G = (V, X) называется пара двух конечных множеств: множество точек и множество линий, соединяющих некоторые пары точек. В терминах декартова произведения (подразд. 1.5) множество 69