Основные понятия теории графов. Представления о планарном графе. Теорема Куратовского и другие характеризации планарности. Эйлеровы и гамильтоновы графы. Расчет количества израсходованного топлива за неделю каждым водителем по справочным данным задачи.
Первая работа по теории графов, принадлежащая известному швейцарскому математику л. Вначале теория графов казалась довольно незначительным разделом математики, так как она имела дело в основном с математическими развлечениями и головоломками. В настоящее время можно узнать и главы чистой математики, например теория математических отношений, в которых теория графов служит естественным аппаратом; с другой стороны, эта теория находит многочисленные применения в разнообразных практических вопросах: при установлении разного рода соответствий, при решении транспортных задач, задач о потоках в сети нефтепроводов и вообще в так называемом «программировании». Математические развлечения и головоломки тоже остаются частью теории графов, особенно если отнести к ним знаменитую проблему четырех красок, интригующую математиков и по сей день. В математике теория графов рассматривается как одна из ветвей топологии; непосредственное отношение она имеет также к алгебре и к теории чисел.Графом 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 г., когда Л. Эйлер не только решил популярную в то время задачу о кенигсбергских мостах, но и нашел критерий существования в графе специального маршрута (эйлерова цикла). Однако этот результат более ста лет оставался единственным результатом теории графов. Родившись при решении головоломок и занимательных игр (задачи о шахматном коне, о ферзях, «кругосветное путешествие», задачи о свадьбах и гаремах и т.п.), теория графов стала в настоящее время простым, доступным и мощным средством решения вопросов, относящихся к широкому кругу проблем. В виде графов можно, например, интерпретировать схемы дорог и электрические цепи, географические карты и молекулы химических соединений, связи между людьми и группами людей.
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
