Эйлеровы и гамильтоновы графы реферат

Обновлено: 02.07.2024

14§4. Методы построения гамильтоновых циклов в графе.

15§5. Алгебраический метод построения гамильтоновых циклов

16§6. Метод перебора Робертса и Флореса

18§8. Улучшение метода Робертса и Флореса

19§9. Мультицепной метод

21§10. Сравнение методов поиска гамильтоновых циклов

23Глава 3. Задача коммивояжера

23§1. Общее описание

25§2. “Жадный” алгоритм решения ЗК

26§3. “Деревянный” алгоритм решения ЗК

28§4. Метод лексикографического перебора

29§5. Метод ветвей и границ решения ЗК

34§6. Применение алгоритма Дейкстры к решению ЗК

34§7. Метод выпуклого многоугольника для решения ЗК

36§8. Генетические алгоритмы

39§9. Применение генетических алгоритмов

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

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

Маршрутом в графе G(V,E) называется чередующаяся последова​тельность вершин и ребер: v0,e1, … en,vn, в которой любые два со​седних элемента инцидентны. Если v0 = vn, то маршрут замкнут, иначе открыт.

Если все ребра различны, то маршрут называется цепью. Если все вершины (а значит, ребра) различны, то маршрут называется про​стой цепью.

Замкнутая цепь называется циклом; замкнутая простая цепь на​зывается простым циклом. Граф без циклов называется ациклическим. Для орграфов цепь называется путем, а цикл — контуром.

Глава 1. Эйлеровы циклы

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

Задача возникла из предложенной Эйлеру головоломки, получившей название "проблема кенигсбергских мостов". Река Прегель, протекающая через Калининград (прежде город назывался Кенигсбергом), омывает два острова. Берега реки связаны с островами так,

как это показано на рисунке.

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

§1. Основные понятия и определения

Да​дим теперь строгое определение эйлерову циклу и эйлерову графу. Если граф имеет цикл (не обязательно простой), содержащий все ребра графа по одному разу, то такой цикл называется эйлеровым циклом, а граф называется эйлеровым графом. Если граф имеет цепь (не обязательно простую), содержащую все вершины по одному разу, то такая цепь называется эйлеровой цепью, а граф называется полуэйлеровым графом.

Ясно, что эйлеров цикл содержит не только все ребра по одному разу, но и все вершины графа (возможно, по несколько раз). Оче​видно также, что эйлеровым может быть только связный граф.

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

1. Каково наименьшее число цепей или циклов необходимое для того, чтобы каждое ребро графа G содержалось точно в одной цепи или в одном цикле? Очевидно, что если G имеет эйлеров цикл или эйлерову цепь, то ответом будет число один.

2. Р
ебрам графа G приписаны положительные веса. Требуется найти цикл, проходящий через каждое ребро графа G по крайней мере один раз и такой, что для него общий вес (а именно сумма величин n_j c(a_j ), где число n_j показывает, сколько раз проходилось ребро a_j , а c(a_j ) — вес ребра) минимален. Очевидно, что если G содержит эйлеров цикл, то любой такой цикл будет оптимальным, так как каждое ребро проходится по один раз и вес этого цикла равен тогда

Сформулированная выше задача 2) называется задачей китайского почтальона , и ее решение имеет много потенциальных приложений, как например:

1. Сбор мусора. Рассмотрим проблему сбора домашнего мусора. Допустим, что определенный район города обслуживается единственной машиной. Ребра графа G представляют дороги, а вершины — пересечения дорог. Величина c(a_j ) — вес ребра — будет соответствовать длине дороги. Тогда проблема сбора мусора в данном районе сводится к нахождению цикла в графе G, проходящего по каждому ребру G по крайней мере один раз. Требуется найти цикл с наименьшим километражем.

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

§5. Задача китайского почтальона

Р
ассмотрим неориентированный граф G(X,A). Среди вершин из X некоторые вершины (скажем из множества X + ) будут иметь четные степени, а остальные (из множества X - =X\X + ) — нечетные степени. Сумма степеней d_i всех вершин x_i X равна удвоенному числу ребер в A (т.к. каждое ребро добавляет по единице к степеням двух его концевых вершин) и поэтому равна четному числу 2m. Следовательно, и так как первая сумма четна, то вторая сумма также четна. Но все d_i в последней сумме нечетны, значит число |X - | вершин нечетной степени четно.

Теорема 3. Для любого цикла, проходящего по G, можно выбрать множество M, для которого граф G - (M) имеет эйлеров цикл, соответствующий первоначально взятому циклу в графе G. Это соответствие таково, что если цикл проходит по ребру (x_i , x_j ) из G l раз, то в G - (M) существует l ребер (одно реальное и l-1 искусственных) между x_i и x_j , каждое из которых проходится ровно один раз эйлеровым циклом из G - (M). Справедливо и обратное утверждение.

Доказательство.

Если цикл проходит по графу G, то по крайней мере одно ребро, инцидентное каждой вершине x_i нечетной степени, должно проходиться дважды. (Ребро, проходимое дважды, можно рассматривать как два параллельных ребра — одно реальное и одно искусственное — и каждое из них проходится один раз). Пусть это ребро (x_i , x_k ). В случае нечетности степени d_k вершины x_k графа G добавление искусственного ребра прежде всего сделает d_k четным, и значит только ребро (x_i ,x_k ) нужно будет проходить дважды, если ограничиться рассмотрением лишь вершин x_i и x_k . В случае когда d_k четно, добавление искусственного ребра сделает d_k нечетным, а второе ребро выходящее из x_k должно быть пройдено дважды (т.е. добавляется еще одно искусственное ребро). Такая ситуация сохраняется до тех пор, пока не встретится вершина нечетной степени, о чем говорилось выше. Следовательно, чтобы удовлетворить условию возвращения в вершину x_i , нужно дважды пройти всю цепь из x_i в некоторую другую вершину нечетной степени x_{r X} - _{. Это автоматически приводит к выполнению условия прохождения вершины xr. Аналогично обстоит дело для всех других вершин xi X} - _{. Это значит что все множество M цепей из G, определенное выше, должно проходится дважды, и так как отсюда вытекает, что каждое ребро из G} - _{(M) должно проходиться один раз, то теорема доказана.}

_{Алгоритм решения задачи китайского почтальона немедленно следует из доказанной теоремы, так как все, что для этого необходимо, состоит в нахождении множества цепей M} * _{(цепного паросочетания для множества вершин нечетной степени), дающего наименьший дополнительный вес. Цикл наименьшего веса, проходящий по G, будет иметь вес, равный сумме весов всех ребер из G плюс сумма весов ребер в цепях из M} * _{. Это то же самое, что и сумма весов всех ребер — реальных и искусственных — графа G} - _(M * _).

Описание алгоритма решения задачи китайского почтальона:

1. Пусть [c_ij ] — матрица весов ребер G. Используя алгоритм нахождения кратчайшей цепи, образуем |X - |_* |X - | — матрицу D =[d_ij ], где d_ij — вес цепи наименьшего веса, идущей из некоторой вершины x_{i X} - _{в другую вершину xj X} - _.

2. _{Найдем то цепное паросочетание M} * _{для множества X} - _{, которое дает наименьший вес (в соответствии с матрицей весов D ). Это можно сделать эффективно с помощью алгоритма минимального паросочетания.}

3. _{Если вершина xα сочетается с другой вершиной xβ, то определим цепь μαβ наименьшего веса (из xα в xβ), соответствующую весу dαβ, делая шаг 1. Добавим искусственные ребра в G, соответствующие ребрам из μαβ, и проделаем это для всех других цепей из множества M} * _{, в результате чего получится граф G} - _(M * _).

4. _{Сумма весов всех ребер графа G} - _(M * _{), найденная с использованием матрицы [cij] (вес искусственного ребра берется равным весу параллельного ему реального ребра), равна минимальному весу цикла, проходящего по G. При этом число прохождений цикла по ребру (xi,xj) равно общему числу параллельных ребер между xi и xj в G} - _(M * _).

Покажем, что указанный выше алгоритм строит минимальный цикл. Для этого следует заметить, что поскольку на шаге 2 мы используем минимальное паросочетание, никакие две кратчайшие цепи μ_ij и μ_pq при таком паросочетании (скажем, идущие из x_i в x_j и из x_p в x_q ) не могут иметь общего ребра. Если бы они имели общее ребро (x_a , x_b ), то сочетание вершин x_i и x_q (использующее подцепи от x_i к x_b и от x_b к x_q ) и сочетание пары вершин x_p и x_j (использующее подцепи от x_p к x_a и от x_a к x_j ) давало бы общее паросочетание веса 2c_ab , меньшего чем вес первоначального паросочетания, что противоречит предположению о минимальности исходного паросочетания. Следовательно, граф G - (M * )не должен содержать более двух параллельных ребер между любыми двумя вершинами, т.е. оптимальный цикл не проходит ни по какому ребру графа G более чем два раза.

§1. Основные понятия и определения

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

Гамильтонов цикл не обязательно содержит все ребра графа. Ясно, что гамильтоновым может быть только связный граф и, что всякий гамильтонов граф является полугамильтоновым. Заметим, что гамильтонов цикл существует далеко не в каждом графе.

Любой граф G можно превратить в гамильтонов граф, добавив достаточное количество вершин. Для этого, например, достаточно к вершинам v₁ ,…,v_p графа G добавить вершины u₁ ,…,u_p и множество ребер <(v_i ,u_i )><(u_i ,v_i+1 )>.

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

§2. Условия существования гамильтонова цикла

Теорема Дирака. Если в графе G(V,E) c n вершинами (n ≥ 3) выполняется условие d(v) ≥ n/2 для любого vV, то граф G является гамильтоновым.

Доказательство.

От противного. Пусть G — не гамильтонов. Добавим к G минимальное количество новых вершин u₁ , … ,u_n , соединяя их со всеми вершинами G так, чтобы G’:= G + u₁ + … + u_n был гамильтоновым.

Пусть v, u₁ , w, … ,v — гамильтонов цикл в графе G’, причем vG, u₁ G’, u₁ G. Такая пара вершин v и u₁ в гамильтоновом цикле обязательно найдется, иначе граф G был бы гамильтоновым. Тогда wG, w 1 ,…,u_n >, иначе вершина u₁ была бы не нужна. Более того, вершина v несмежна с вершиной w, иначе вершина u₁ была бы не нужна.

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

Прикрепленные файлы: 1 файл

Лекция 10.doc

п.10. Эйлеровы и гамильтоновы циклы.

10.1. Пути и циклы Эйлера.

Определение 10.1. Пусть G(V, E) – граф. Цикл, который включает все ребра и вершины графа G, называется эйлеровым циклом. Граф, в котором существует эйлеров цикл называется эйлеровым.

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

Теорема 10.1. Связный граф является эйлеровым тогда и только тогда, когда степень каждой его вершины четная.

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

Достаточность. Предположим, что степени всех вершин связного графа G четные. Начнем цепь G₁ из произвольной вершины v₁, и будем продлевать ее, выбирая каждый раз новое ребро. Так как степени вершин четная, то, попав в некоторую вершину, мы всегда будем иметь в распоряжении еще не пройденное ребро. Таким образом, построение цепи P₁ обязательно закончится в вершине v₁, и P₁ будет циклом. Если P₁ содержит все ребра графа G, то построен эйлеров цикл.

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

Объединим циклы P₁ и P₂ следующим образом: пройдем часть P₁ от вершины v₁ до вершины v₂, затем пройдем цикл P₂, затем – оставшуюся часть P₁ от v₂ до v₁.

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

Данная теорема служит критерием существования эйлерова цикла в графе. Это связано с тем, что эйлеровых графов с числом вершин n среди множества графов с тем же числом вершин почти нет.

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

Для построения эйлерова цикла применяется так называемый алгоритм Флери.

Определение 10.2. Пусть G(V, E) – граф. Путь, который включает каждое ребро графа G только один раз называется эйлеровым путем. Эйлеров путь, который не является циклом называется собственным эйлеровым путем.

Сформулируем теорему (без доказательства), в которой описано условие, при котором граф имеет собственный эйлеров путь.

Теорема 10.2. Граф (мультиграф или псевдограф) имеет собственный эйлеров путь тогда и только тогда, когда он связный и ровно две его вершины имеют нечетную степень.

По этой теореме получается, что задача о кенигсбергских мостах так же не имеет и эйлерова пути.

Аналогично можно ввести понятие эйлерова цикла для ориентированного графа и условие существования эйлерова цикла в орграфе.

Определение 10.3. Пусть G(V, E) - ориентированный граф. Ориентированный цикл, который включает все ребра и вершины графа G, называется эйлеровым циклом.

Теорема 10.3. Ориентированный граф имеет эйлеров цикл тогда и только тогда, когда он связный и полустепень захода каждой вершины равна ее полустепени исхода.

Какое еще применение эйлерового цикла для решения практических задач? Рассмотрим следующий пример.

Пример 10.1. Из какого минимального числа кусков проволоки можно спаять каркас куба? Толщина всех ребер каркаса должна быть одинаковой.

Чтобы решить данную задачу, сначала сформулируем следующую теорему, которую примем без доказательства.

Теорема 10.4. Если связный граф содержит ровно 2n вершин нечетной степени, то минимальное число реберно-непересекающихся цепей, на которые можно разбить его ребра, равно n.

10.2. Пути и циклы Гамильтона.

В 1857 году математик Уильям Роуэн Гамильтон придумал игру. Существует несколько версий того, как это произошло. По одной из версий он описал игру в письме к другу. Согласно другой, он действительно изобрел игру и продал ее производителю игрушек. В любом случае она включала додекаэдр, т.е. правильный многогранник, 12 граней которых представляли собой равные правильные пятиугольники. В каждом из 20 углов, или вершин тела, просверливалась дырочка, в которую вставлялся колышек, изображавший город. Используя веревку, требовалось найти путь через города, посетив каждый город один раз, и вернуться в исходный город.

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

Определение 10.4. Пусть G(V, E) – граф. Гамильтонов путь – это простой путь, который проходит через каждую вершину графа G. Гамильтонов цикл – это простой цикл, который проходит через каждую вершину графа G.

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

Мы рассмотрим одну из задач, в которой требуется отыскать гамильтонов цикл в взвешенном графе минимальной длины. Сначала введем формулировку задачи, а потом алгоритм решения этой задачи.

Задача коммивояжера (развозчика продукции или бродячего торговца).

Формулировка задачи: коммивояжер должен посетить один и только один раз каждый из n городов и вернуться в исходный пункт. Его маршрут должен минимизировать суммарную длину пройденного пути.

Пусть C=[c_ij] – матрица расстояний между городами. Для составления математической модели задачи обозначим через x_ij факт переезда коммивояжером из города i в город j. Поскольку переезд из одного города в другой может осуществляться только один раз, то x_ij должны принимать только два значения: 1 или 0, т.е. булевы значения. Таким образом:

Математическая модель задачи примет следующий вид:

Система ограничений (2) обеспечивает построение маршрута, при котором коммивояжер въезжает в каждый город только один раз, а система (3) – маршрута, когда он выезжает из каждого города только один раз. К сожалению, эти ограничения недостаточны, так как среди допустимых ими решений имеются маршруты, не образующие полный цикл, включающий все города. Устранение подциклов достигается при добавлении системы ограничений:

где переменные u могут принимать произвольные действительные значения.

Решение задачи коммивояжера методом ветвей и границ (алгоритм Литтла).

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

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

Сравнивая нижние границы и подмножеств и , можно выделить среди них то, которое с большей вероятностью содержит гамильтонов цикл минимальной длины. Затем одно из подмножеств или по аналогичному правилу разбивается на два новых и . Для них снова отыскиваются нижние границы и и т.д.

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

Пусть известна матрица весов некоторого орграфа, вершины которого занумеруем числами от 1 до :

где – вес дуги, соединяющей вершины и j, где .

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

Алгоритм Литтла разбивается на несколько шагов.

Шаг 1. Приведение исходной матрицы.

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

После этого вычисляем константу приведения – сумму минимальных элементов столбцов и строк, которые вычитались. Получаем приведенную матрицу с константой приведения .

Шаг 2. Определение степеней нулей.

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

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

Темы исследований

Оформление работы

Наш баннер

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

Код баннера:

Исследовательские работы и проекты

Задачи о мостах. Понятие Эйлерова и Гамильтоновых графах

Ключевой темой исследовательской работы по математике на тему "Задачи о мостах. Понятие Эйлерова и Гамильтоновых графах" является изучение Эйлеровых и Гамильтоновых циклов и попытки применить их на практике. В работе приводится история происхождения графов и дается терминология рассматриваемой теории.

Подробнее о работе:

В рамках проведенного проекта по математике "Задачи о мостах. Понятие Эйлерова и Гамильтоновых графах" учащейся 10 класса школы был рассмотрен вклад Леонарда Эйлера в науку и проанализирована задача о Кёнигсбергских мостах, изучены способы ее решения. Также во время проведения своего исследования ученица ознакомилась с теоретическими понятиями об Эйлеровом цикле.

В рамках самостоятельной работы ученица 10 класса создала исследовательский проект на тему "Задачи о мостах. Понятие Эйлерова и Гамильтоновых графах", в котором представлены варианты решения задач по Леонарду Эйлеру, дано развернутое определение понятия графа, изложена теория графов и перечислены разновидности графов. Автором проекта были исследованы гамильтоновый граф, гамильтоновый цикл и описаны некоторые задачи, решаемые по теории Эйлерова и Гамильтоновых циклов.

Оглавление

Введение
1. Биография Леонардо Эйлера.
1.1. Вклад Леонарда Эйлера в науку.
1.2. Задача о Кёнигсбергских мостах
2. Теоретические понятия об Эйлерове цикле.
2.1. Решение задач по Леонарду Эйлеру.
2.2. Понятие графа. Теория графов. Разновидности графов
3. Гамильтоновый граф.
3.1. Гамильтоновый цикл.
3.2. Некоторые задачи,решаемые по теории Эйлерова и Гамильтоновых Циклов.
Заключение
Список используемой литературы

Введение

Применение теории графов даёт возможность повысить уровень знаний в химии, компьютерной химии, хемоинформатике, программировании, экономике, логистике, схемотехнике, плате (печатной) или микросхеме.

Целью работы является изучение Эйлеровых и Гамильтоновых циклов и научиться применять их на практике.

Для реализации указанной цели были поставлены следующие задачи:

1. Изучить историю возникновения теории графов, терминологию теории
2. графов, изображение графов на плоскости;
3. Проанализировать некоторые задачи теории графов;
4. Применять теорию графов.

Объектом исследования является выявление на практике Эйлеровых и Гамильтоновых циклов.

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

Биография Леонардо Эйлера

Леонард Эйлер родился 4 апреля 1707 года в селении Рихен вблизи города Базеля, Швейцария. Начальное образование получил дома под руководством отца, затем продолжил обучение в гимназии Базеля. В 1723 г. Эйлер получил степень магистра искусств, а в 1727 г. защитил диссертацию о распространении звука. В 1727 г. Эйлер приехал в Петербург, где был назначен адъюнктом математики. В 1730 г. Эйлер получил место профессора кафедры физики, а в 1733 г.- кафедры математики. В 1741 г. Л. Эйлер переехал в Берлин, но поддерживал связь с Петербургской академией наук.

Эйлер высоко ценил русских ученых Семёна Кирилловича Котельникова – автора русского учебника механики, и М. В. Ломоносова. В 1766 г. Эйлер со своей семьёй возвращается в Петербург и приступает к активной деятельности в Академии наук. В этот период он справедливо считался первым математиком в мире и пользовался всеобщим уважением и почетом.

Умер Л. Эйлер 18 сентября 1783 г. в Петербурге.

Вклад Леонарда Эйлера в науку

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

Также Леонард Эйлер является основоположником теории специальных функций. В теории корабля Эйлер внёс вклад в теорию устойчивости. В алгебре Эйлеру принадлежит ряд работ. Он является основоположником теории специальных функций. Эйлер является создателем вариационного исчисления. Леонард Эйлер также проводил исследования по теории непрерывных дробей и других бесконечных процессов. Леонард Эйлер заложил основы нескольких математических дисциплин.

Задача о Кёнигсбергских мостах

Семь мостов Кёнигсберга, или Задача о семи кёнигсбергских мостах — старинная математическая задача, в которой спрашивалось, как можно пройти по всем семи мостам Кёнигсберга , не проходя ни по одному из них дважды. Впервые была решена в 1736 году математиком Леонардом Эйлером доказавшим, что это невозможно, и изобретшим таким образом эйлеровы циклы.

Теоретические понятия об Эйлерове цикле

Эйлеров путь в графе — это путь, проходящий по всем рёбрам графа и притом только по одному разу.

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

Эйлеров граф — граф, содержащий эйлеров цикл.

Решение задач по Леонарду Эйлеру

На упрощённой схеме города мостам соответствуют линии (ребра графа), а частям города — точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам:

Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин.

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

Если ровно две вершины графа нечётные, то можно начертить этот граф без отрыва карандаша от бумаги, при этом нужно начинать с одной из нечётных вершин и завершить его в другой нечётной вершине.

Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.

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

Понятие графа. Теория графов. Разновидности графов

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

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

В зависимости от задачи, одни изображения могут давать более наглядную картину, чем другие.

Разновидность графов

• Изоморфные и плоские(найти замкнутый путь, проходящий по рёбрам и позволяющий побывать в каждой его вершине по одному разу;
• Графы игр(шахматы)
• Направленные графы
• Орграфы (графы, в которых все рёбра имеют направления)
• Гамильтоновый цикл

Читайте также:

  
• Как бороться с мусором реферат
  
• Врожденный иммунитет иммунология реферат
  
• Первые исследования по изучению природы молнии франклин ломоносов рихман реферат
  
• М шолохов поднятая целина реферат
  
• Методика розвитку гнучкості реферат