Основные понятия теории графов. Представления о планарном графе. Теорема Куратовского и другие характеризации планарности. Эйлеровы и гамильтоновы графы. Расчет количества израсходованного топлива за неделю каждым водителем по справочным данным задачи.
Аннотация к работе
Первая работа по теории графов, принадлежащая известному швейцарскому математику л. Вначале теория графов казалась довольно незначительным разделом математики, так как она имела дело в основном с математическими развлечениями и головоломками. В настоящее время можно узнать и главы чистой математики, например теория математических отношений, в которых теория графов служит естественным аппаратом; с другой стороны, эта теория находит многочисленные применения в разнообразных практических вопросах: при установлении разного рода соответствий, при решении транспортных задач, задач о потоках в сети нефтепроводов и вообще в так называемом «программировании». Математические развлечения и головоломки тоже остаются частью теории графов, особенно если отнести к ним знаменитую проблему четырех красок, интригующую математиков и по сей день. В математике теория графов рассматривается как одна из ветвей топологии; непосредственное отношение она имеет также к алгебре и к теории чисел.Графом G называется пара (V (G), E (G)), где V (G) - непустое конечное множество элементов, называемых вершинами, а E(G) - конечное семейство неупорядоченных пар элементов из V (G) (необязательно различных), называемых ребрами. Дополнением графа называется граф G с теми же вершинами, что и граф G, и с теми ребрами, которые необходимо добавить к графу G, чтобы получился полный граф. Допустим, что множество вершин графа можно разбить на два непересекающихся подмножества V1 и V2, так, что каждое ребро в G соединяет какую-нибудь вершину из V1 с какой-нибудь вершиной из V2, тогда G называется двудольным графом. Следует подчеркнуть, что в двудольном графе совсем не обязательно каждая вершина из V1 соединена с каждой вершиной из V2; если же это так и если при этом граф G простой, то он называется полным двудольным графом и обычно обозначается Km,n, где m, n - число вершин соответственно в V1 и V2 . Если в графе с вершинами n>2 в точности две вершины имеют одинаковую степень, то в этом графе всегда найдется либо в точности одна вершина степени 0, либо в точности одна вершина степени n-1.Начало теории графов относится к 1736 г., когда Л. Эйлер не только решил популярную в то время задачу о кенигсбергских мостах, но и нашел критерий существования в графе специального маршрута (эйлерова цикла). Однако этот результат более ста лет оставался единственным результатом теории графов. Родившись при решении головоломок и занимательных игр (задачи о шахматном коне, о ферзях, «кругосветное путешествие», задачи о свадьбах и гаремах и т.п.), теория графов стала в настоящее время простым, доступным и мощным средством решения вопросов, относящихся к широкому кругу проблем. В виде графов можно, например, интерпретировать схемы дорог и электрические цепи, географические карты и молекулы химических соединений, связи между людьми и группами людей.