Методы решения графов. Графы и терминология

При выводе уравнений скоростей ферментативных реакций используется ряд упрощающих допущений. В частности, как правило, принимают, что ферментативная реакция протекает в условиях идеального перемешивания, термо- и рН-статирования и что в реакции очень быстро устанавливается квазистационарное состояние (см. раздел 2.1), в котором все промежуточные формы фермента находятся в равновесии друг с другом. Приставка «квази» означает, что лишь часть переменных достигает стационарных значений, тогда как остальные продолжают медленно меняться. Использование допущения о достижении частью концентраций (биохимической системы квазистационарных значений известно в литературе как метод Боденштейна - Семенова . Этот метод позволяет резко упростить анализ (био)химических систем. Вместо решения систем нелинейных дифференциальных уравнений, описывающих изменение промежуточных веществ в ходе реакции, в соответствии с этим методом удается решать лишь системы алгебраических уравнений, связывающих друг с другом

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

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

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

Например, ферментативная реакция

протекающая через промежуточное образование двух фермент-субстратных комплексов

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

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

(см. скан)

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

Совокупности (на стр. 24) не являются деревьями узла так как а представляет собой замкнутую последовательность ветвей (цикл), имеет две параллельные последовательности ветвей соединяющих узлы и в имеет цикл ветвь направлена от узла в узел не связан с узлом

Базовым определителем узла называется сумма величин всех деревьев, направленных в узел - базу. Определителем графа называется сумма всех базовых определителей графа. Например, определителями узлов и в графе (1.11) являются следующие суммы величин деревьев (1.12):

(см. скан)

а определитель этого графа равен сумме трех базовых определителей:

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

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

Например, для графа (1.11) по формуле (1.14) следует записать

Первый член в числителе положителен, так как распад освобождает а второй член отрицателен, так как связывается с

Квазистационарные концентрации промежуточных комплексов находятся по формуле

Так, в графе (1.11) концентрации свободного фермента и комплексов определяются выражениями

Что такое метод графов?

Слово «граф» в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями. Прежде всего, стоит сказать о том, что графы, о которых пойдет речь, к аристократам былых времен никакого отношения не имеют. Наши «графы» имеют корнем греческое слово «графо», что значит «пишу». Тот же корень в словах «график», «биография».

В математике определение графа дается так: графом называется конечное множество точек, некоторые из которых соединены линиями. Точки называются вершинами графа, а соединяющие линии – рёбрами.

Схема графа, состоящая из «изолированных» вершин, называется нулевым графом. (рис.2)

Графы, в которых не построены все возможные ребра, называются неполными графами. (рис.3)

Графы, в которых построены все возможные ребра, называются полными графами. (рис.4)

Граф, каждая вершина которого соединена с ребром любой другой вершины, называется полным .

Заметим, что если полный граф имеет n вершин, то количество ребер будет равно

n(n-1)/2

Действительно, количество ребер в полном графе с n вершинами определяется как число неупорядоченных пар, составленных из всех n точек-ребер графа, т. е. как число сочетаний из n элементов по 2:

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

Степени вершин и подсчет числа ребер.

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

Если степени всех вершин графа равны, то граф называется однородным . Таким образом, любой полный граф - однородный.

рис.5

На рисунке 5 изображен граф с пятью вершинами. Степень вершины А обозначим Ст.А.

На рисунке: Ст.А = 1, Ст.Б = 2, Ст.В = 3, Ст.Г= 2, Ст.Д= 0.

Сформулируем некоторые закономерности, присущие определенным графам.

Закономерность 1.

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

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

Эта закономерность очевидна уже после рассмотрения любого полного графа. Каждая вершина соединена ребром с каждой вершиной, кроме самой себя, т. е. из каждой вершины графа, имеющего n вершин, исходит n-1 ребро, что и требовалось доказать.

Закономерность 2.

Сумма степеней вершин графа число четное, равное удвоенному числу ребер графа.

Эта закономерность справедлива не только для полного, но и для любого графа. Доказательство:

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

Число нечетных вершин любого графа четно. Доказательство:

Рассмотрим произвольный граф Г. Пусть в этом графе число вершин, степень которых 1, равна К1; число вершин, степень которых 2, равно K2; ...; число вершин, степень которых n, равно Кn. Тогда сумму степеней вершин этого графа можно записать как
K1 + 2К2 + ЗК3 + ...+ nКn.
С другой стороны: если число ребер графа R, то из закономерности 2 известно, что сумма степеней всех вершин графа равна 2R. Тогда можно записать равенство
K1 + 2К2 + ЗК3 + ... + nКn = 2R. (1)
Выделим в левой части равенства сумму, равную числу нечетных вершин графа (К1 + К3 + ...):
K1 + 2К2 + ЗК3 + 4К4 + 5К5 + ... + nК = 2R,
(К1 + К3 + К5 +...) + (2K2 + 2Х3 +4K4 + 4К5 + ...)=2R
Вторая скобка- четное число как сумма четных чисел. Полученная сумма (2R) четное число. Отсюда (К1 + К3 + К5 +...)-четное число.

Рассмотрим теперь задачи, решаемые с помощью графов:

Задача. Первенство класса . В первенстве класса по настольному теннису 6 участников: Андрей, Борис, Виктор, Галина, Дмитрий и Елена. Первенство проводится по круговой системе – каждый из участников играет с каждым из остальных один раз. К настоящему моменту некоторые игры уже проведены: Андрей сыграл с Борисом, Галиной и Еленой; Борис, как уже говорилось, с Андреем и еще с Галиной; Виктор – с Галиной, Дмитрием и Еленой; Галина с Андреем и Борисом; Дмитрий – с Виктором и Елена – с Андреем и Виктором. Сколько игр проведено к настоящему моменту и сколько еще осталось?

Обсуждение. Изобразим данные задачи в виде схемы. Участников будем изображать точками: Андрея – точкой А, Бориса – точкой Б и т.д. Если двое участников уже сыграли между собой, то будем соединять изображающие их точки отрезками. Получается схема, показанная на рисунке 1.

Точки А, Б, В, Г, Д, Е - вершины графа, соединяющие их отрезки – ребра графа.

Заметим, что точки пересечение ребер графа не являются его вершинами.

Число игр, проведенных к настоящему моменту, равно числу ребер, т.е. 7.

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

Чтобы найти число игр, которые надо провести, построим еще один граф с теми же вершинами, но ребрами будем соединять тех участников, которые еще не играли друг с другом (рис.2) Ребер у этого графа оказалось 8, значит, осталось провести 8 игр: Андрей – с Виктором и Дмитрием; Борис – С Виктором, Дмитрием и Еленой и т.д.

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

Задача. Кто играет Ляпкина – Тяпкина? В школьном драмкружке решили ставить гоголевского «Ревизора». И тут разгорелся жаркий спор. Все началось с Ляпкина – Тяпкина.

Ляпкиным – Тяпкиным буду я! – решительно заявил Гена.

Нет, я буду Ляпкиным – Тяпкиным, возразил Дима.- С раннего детства мечтал воплотить этот образ на сцене.

Ну, хорошо, уступить эту роль, если мне дадут сыграть Хлестакова, - проявил великодушие Гена.

- …А мне – Осипа, - не уступил ему в великодушии Дима.

Хочу быть Земляникой или Городничим,- сказал Вова.

Нет, Городничим буду я, - хором закричали Алик и Боря. – Или Хлестаковым, -

Удастся ли распределить роли так, чтобы исполнители были довольны?

Обсуждение. Изобразим юных актеров кружками верхнего ряда: А – Алик, Б – Борис, В – Вова, Г – Гена, Д – Дима, а роли, которые они собираются играть, - кружками второго ряда (1 – Ляпкин – Тяпкин, 2 – Хлестаков, 3 – Осип, 4 – Земляника, 5 – Городничий). Затем от каждого участника проведем отрезки, т.е. ребра, к ролям, которые он хотел бы сыграть. У нас получиться граф с десятью вершинами и десятью ребрами (рис.3)

Чтобы решить задачу, нужно из десяти выбрать пять ребер, не имеющих общих вершин. Сделать это легко. Достаточно заметить, что в вершины 3 и 4 ведут по одному ребру, из вершин Д и В соответственно. Это означает, что Осипа (вершина 3) должен играть Дима (кто же еще?), а Земляничку – Вова. Вершина1 – Ляпкин – Тяпкин – соединена ребрами с Г и Д. Ребро 1 – Д отдает, так как Дима уже занят, остается 1 – Г, Ляпкина – Тяпкина должен играть Гена. Остается соединить вершины А и Б с вершинами 2 и 5, соответствующими ролям Хлестакова и Городничего. Это можно сделать двумя способами: либо выбрать ребро А -5 и Б – 2, либо ребро А -2 и Б -5. В первом случае Алик будет играть Городничего, а Боря – Хлестакова, во втором случае наоборот. Как показывает граф, других решений задача не имеет.

Тот же граф получится при решении следующей задачи:

Задача. Сварливые соседи. Жители пяти домов поссорились друг с другом и, чтобы не встречаться у колодцев, решили поделить их (колодцы) так, чтобы хозяин каждого дома ходил к «своему» колодцу по «своей» тропинке. Удастся ли им это сделать?

Возникает вопрос: так ли нужны были графы в разобранных задачах? Разве нельзя прийти к решению чисто логическим путем? Да, можно. Но графы придали условиям наглядность, упростили решение и выявили сходство задач, превратив две задачи в одну, а это уже не так уж мало. А теперь представьте себе задачи, графы которых имеют 100 или более вершин. А ведь именно такие задачи приходиться решать современным инженерам и экономистам. Тут без графов не обойтись.

III. Графы Эйлера.

Теория графов – наука сравнительно молодая: во времена Ньютона такой науки еще не существовало, хотя и были в ходу «генеалогические деревья», представ-ляющие собой разновидности графов. Первая работа по теории графов принадлежит Леонарду Эйлеру, и появилась она в 1736 году в публикациях петербургской Академии наук. Начиналась эта работа с рассмотрения следующей задачи:

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

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

Фигура эта, такая простая на вид, оказывается, имеет интересную особенность. Если мы начнем движение из вершины В, то у нас это обязательно получится. А что будет, если мы начнем движение из вершины А? Легко убедиться, что обвести линию в этом случае нам не удается: у нас всегда будет оставаться не пройденные ребра, добраться до которых уже невозможно.

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

Графы, начерченные на рис.6 также можно начертить одним росчерком пера.

Теперь попробуйте вычертить одним росчерком граф, изображенный на рис.7

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

Проведем рассуждения, которые убедят нас в этом. Рассмотрим узел А. Из него выходят три вершины. Начнем вычерчивать граф с этой вершины. Чтобы пройти по каждому из этих ребер, мы должны выйти из вершины А по одному из них, в какой – то момент обязательно вернуться в него по второму и выйти по третьему. А вот снова войти уже не сможем! Значит, если мы начнем вычерчивание с вершины А, то закончить в нем не сможем.

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

Итак, вершина А должен быть или началом, или конечным узлом вычерчивания.

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

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

Такими графы названы в честь учёного Леонарда Эйлера.

Закономерность1. (вытекает из рассмотренной нами теоремы).

Невозможно начертить граф с нечетным числом нечетных вершин.
Закономерность 2.

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

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

Граф, имеющий более двух нечетных вершин, невозможно начертить «одним росчерком».
Фигура (граф), которую можно начертить, не отрывая карандаш от бумаги, называется уникурсальной.

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

Граф называется несвязным , если это условие не выполняется.

рис.7рис.8

На рисунке 7, очевидно, изображен несвязный граф. Если, например, на рисунке между вершинами Д и Е провести ребро, то граф станет связным. (рис.8)

Такое ребро в теории графов (после удаления которого граф из связного превращается в несвязный) называется мостом .

Примерами мостов на рисунке 7 могли бы служить ребра ДЕ, A3, ВЖ и др., каждое из которых соединяло бы вершины «изолированных» частей графа.(рис.8)

Несвязный граф состоит из нескольких «кусков». Эти «куски» называются компонентами связности графа. Каждая компонента связности является, конечно, связным графом. Отметим, что связный граф имеет одну компоненту связности.
ТЕОРЕМА.

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

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

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

Вернемся теперь к задаче о кенигсбергских мостах.

Обсуждение задачи . Обозначим различные части города буквами А, В, С, Д, а мосты – буквами а, b, c, d, e, f, g – мосты, соединяющие соответствующие части города. В этой задаче существуют лишь переходы через мосты: переходя через любой мост, мы всегда из одной части города попадаем в другую, И, наоборот, переходя из одной части города в другую, мы непременно пройдем по мосту. Поэтому, изобразим план города в виде графа, вершины которого А, В, С, Д (рис.8) изображают отдельные части города, а ребра a, b, c, d, e, f, g – мосты, соединяющие соответствующие части города. Ребра зачастую оказываются удобнее изображать удобнее не прямолинейными отрезками, а криволинейными – «дугами».

Если бы существовал маршрут, удовлетворяющий условию задачи, то существовал бы замкнутый непрерывный обход этого графа, проходящий один раз по каждому ребру. Иными словами этот граф должен вычерчиваться одним росчерком. Но это невозможно – какую бы вершину мы ни выбрали за исходную, нам придется проходить через остальные вершины, и при этом каждому «входящему» ребру (мосту, по которому мы вошли в эту часть города) будет соответствовать «выходящее» ребро мост, которым мы и воспользуемся затем, чтобы покинуть эту часть города): число ребер, входящих в каждую вершину, будет равно числу ребер, выходящих из нее, т. е. общее число ребер, сходящихся в каждой вершине, должен быть четным. Наш граф этому условию не удовлетворяет, и поэтому требуемого маршрута не существует.

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

Вариантов немного, поэтому, после небольшого числа попыток («2-3-4-2-1-5-4-1-ой?!», «4-2-1-5-4-3-5-ой?!») любой ребёнок находил верное решение. А нужно всего лишь начинать рисование либо с точки 1, либо с точки 5. После этого движение в любом направлении в итоге приводило к решению задачи.

Что же особенного в этих двух точках, первой и пятой? Что позволяет им становиться гарантом успешного решения? Всего лишь «нужное» для решения задачи число сходящихся в каждой из этих особенных точек числе сторон, а именно - нечётное количество! Действительно, в точках 1 и 5 сходится по 3 стороны, в 2 и 4 - по 4, а во второй - 2. В терминах теории графов (именно эта дисциплина с лёгкость решает задачу) это требование к «открытому конверту» звучит так:

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

Зная это, становится понятным, что нарисовать «закрытый конверт» при тех же требованиях задачи не представляется возможным-все вершины имеют нечётную степень.

И любое подтрунивание над одноклассником - что, мол, слабо? - рассчитано на неосведомлённость последнего в теории графов!

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

Но вернёмся к графам. Итак, - множество вершин (узлов), соединённых рёбрами. В строгом определении графом называется упорядоченная пара G=(V,E), где V - это непустое множество вершин или узлов, а E - это множество пар вершин, называемых рёбрами.

Вершины и называются концевыми вершинами (или просто концами) ребра Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними.

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

Степенью вершины (помните «открытый конверт»?) называют количество инцидентных ей ребер (т.е. ребер, входящих в вершину). При этом петли считают дважды.

Вершина называется изолированной , если она не является концом ни для одного ребра; висячей (или листом ), если она является концом ровно одного ребра.

Одних только определений в теории графов великое множество. Граф может быть ориентированным (все рёбра имеют ориентацию наподобие вектора), взвешенным (каждому ребру поставлено в соответствие некоторое число, называемое весом ребра), связным (любых вершин , есть путь из в ) и т.д. Как правило, к возникновению новых определений и понятий приводило расширение круга задач, решаемое посредством этой теории. Именно поэтому интерес представляют не столько сами многочисленные определения (с ними можно ознакомиться в любом учебнике), сколько решаемые ими задачи! Среди них такие классические как «Проблема семи мостов Кенигсберга» (одна из первых задач теории графов, опубликован Эйлером в 1736), «Проблема четырёх красок» (была сформулирована в 1852 году, но доказательство получено лишь в 1976 году), «Задача коммивояжёра» , изоморфизм графов, планарность

Остановимся предметно на «задаче коммивояжёра».Рассмотрим типичное лабораторное задание по дискретной математике:

Решить задачу коммивояжёра для () городов «жадным алгоритмом». Города определить случайным образом. Задачу считать симметричной. Критерием выгодности считать расстояние между городами. Написать программу.

Прежде всего, немного теории.

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

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

Совершенно очевидно, что решить задачу методом прямого перебора (или «грубой силы») не поможет даже самый мощный компьютер! Не случайно в условии сделан акцент на приближённый алгоритм.

«Жадный алгоритм», а именно «метод ближайшего соседа» - один из простейших методов решения задачи коммивояжёра. Формулируется следующим образом:

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

Составим словесный алгоритм.

Пользователь задаёт количество городов – константа CITIES_COUNT. Расстояния между городами хранятся в квадратном массиве Distances. А оптимальный путь, представляющий собой оптимальную последовательность индексов городов, хранится в линейном массиве Path.

1. Происходит первоначальная инициализация карты городов. Для этого используем случайный алгоритм (выполняя требование исходной задачи «Города определить случайным образом» ).
2. Ищется путь коммивояжёра – процедура CalcPath.
   1. В ней рассчитывается матрица взаимных расстояний между городами Distances. По диагонали в матрице хранятся -1, верхний треугольник матрицы рассчитывается и копируется в нижний, т.к. матрица симметрична относительно главной диагонали.
   2. Далее «пробегаем» по всем городам (переменная iCurr), начиная с начального (iStart), и для каждого ищем ближайший город (до которого расстояние минимально), запоминаем его в переменной iM и добавляем в путь Path. При поиске ближайшего города игнорируем те города, в которые уже заходили (дистанция до которых =-1). Попутно ищем общую протяжённость пути (Len);
   3. После включения очередного города в путь, вычёркиваем его из рассмотрения (ставим в матрицу расстояний -1 в соответствующие этому городу столбец и строку).

Блок-схема поиска пути имеет вид:

Результат работы программы (скачать) для пяти городов (так нагляднее) представлен ниже:

Начальный город (родной город коммивояжёра) помечается красным цветом, остальные - синим.

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

Однако, вспомним требования задачи. Итак, для числа городов 10, 100, 300 решения могут быть следующими:

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

Рассмотренный алгоритм является эвристическим . В большинстве эвристических методов (метод минимального остовного дерева , метод имитации отжига , метод ветвей и границ ) находится не самый эффективный маршрут, а приближённое решение. На практике это единственная возможность найти, хоть и приближённое, решение задачи. Безусловно, оптимальный маршрут может дать лишь полный перебор вариантов , но разве реально это сделать хотя бы для 100 городов, где число этих вариантов выражается 156-значным числом?!

Литература

1. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. - М.: Издательский дом «Вильямс», 2001.
2. Бондарев В.М., Рублинецкий В.И., Качко Е.Г. Основы программирования. - Харьков: Фолио; Ростов н/Д: Феникс, 1997.
3. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. - М.: МЦНМО, 2001.
4. Романовский И.В. Дискретный анализ… - Издание 2-е, исправленное. - СПб.: Невский диалект, 2000.
5. Шень А. Программирование: теоремы и задачи. - М.: МЦНМО, 1995.

Решение дискретной математики на заказ

Появились вопросы — задавайте в комментариях. Нужно решить задачи — заказывайте .
Будем рады Вам помочь!

«Ещё один увлекательный способ решения задач» (метод графов) Автор: Пыркова Мария, обучающаяся 7 класса школы-интерната № 9 ОАО РЖД г. Кинель Самарской области Руководитель: Степанова Ольга Алексеевна, учитель математики высшей категории. г. Кинель, 2015

Актуальность решающая роль задач в обучении математике; введение в школьный курс разделов «Комбинаторика», «Логика», «Вероятность»; отыскание способов решения нестандартных задач.

Цель исследования: изучить понятие «графа» и его элементов; применять при решении различных типов задач.

Объект исследования: граф ПРЕДМЕТ ИССЛЕДОВАНИЯ история математики, виды задач, способы решения задач.

Основные методы исследования: исследовательский; использование на практике. компьютерная обработка данных; классификация и анализ собранного материала; математический отбор.

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

Сфера применения графов

Практическая часть

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

«Сколько у тебя в стаде голов скота?» Н а вопрос путника: - пастух ответил: «Если бы к моему стаду добавить одну корову, то третью часть всего стада составляли бы овцы и козы. Если бы к имеющимся овцам и козам добавить одну овцу, то седьмую часть их составляли бы козы, в которых третья часть есть лишь один маленький козленок». Сколько голов скота было в стаде? Решение: Составим граф по условию задачи. Решаем обратно. Ответ: в стаде 59 голов скота.

Задачи на движение. Машина прошла первый участок пути за 3 часа, а второй участок - за 2 часа. Длина обоих участков вместе 267 км. С какой скоростью шла машина на каждом участке, если скорость на втором участке была на 8,5 км/ч больше, чем на первом? Построим сетевой граф. Пусть V 1 = х км/ч, тогда V 2 = х+ 8,5 км/ч, S 1 = 3х км, S 2 = 2(х+8.5)км Составим уравнение: 3х + 2(х+8,5) = 267 Ответ: 50 км/ч

Комбинаторные задачи. Задача «Что выше?» На пришкольном участке растут 8 деревьев: яблоня, тополь, береза, рябина, дуб, клен, лиственница и сосна. Рябина выше лиственницы, яблоня выше клена, дуб ниже березы, но выше сосны, сосна выше рябины, береза ниже тополя, а лиственница выше яблони. Расположите деревья от самого низкого к самому высокому. Ответ: клен самое низкое дерево.

Опрос одноклассников

Заключение «Рано или поздно всякая правильная математическая идея находит применение в том или ином деле.» (А.Н. Крылов) Графы – это замечательные математические объекты, с помощью которых можно решать математические, экономические и логические задачи. Графы позволяют наглядно представить условие задачи, держать в памяти многочисленные факты, а значить, значительно упростить её решение. Вызывает интерес к изучению математики и получению хороших результатов.

Список литературы Энциклопедический словарь юного математика. \Сост. А.П.Савин.- М.: Педагогика, 1989 Квант №6 1994г. М. Гарднер «Математические досуги» М.: Мир, 1972 Берж К. Теория графов и ее применение. ИЛ, 1962. Математика, учебник для 5 кл. / Н.Я.Виленкин, В.И.Жохов и др.-М:Просвещение, 2011 Математика, учебник для 6 кл. / Н.Я.Виленкин, В.И.Жохов и др.-М:Просвещение, 2011 Алгебра: учебник для 7 кл. / Ю.Н.Макарычев и др., под редакцией С.А.Теляковского.-М.:Просвещение,2011 Элективные курсы «Решение задач с помощью графов»/ авт.-сост.Л.Н.Харламова. - Волгоград: Учитель,2007 .

Спасибо за внимание!

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

Первая и главная цель, которую нужно преследовать при изучении графов, –научить школьников видеть граф в условии задачи и грамотно переводить условие на язык теории графов. Не стоят рассказывать обе всем на нескольких занятиях подряд. Лучше разнести занятия по времени на 2–3 учебных года. (Прилагается разработка занятия “Понятие графа. Применение графов к решению задач” в 6 классе).

2. Теоретический материал к теме “Графы”.

Введение

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

Понятие графа

Рассмотрим две задачи.

Задача 1. Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Вене; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс и Марс – Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса?

Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями.

Теперь сразу видно, что долететь с Земли до Марса нельзя.

Задача 2. Доска имеет форму двойного креста, который получается, если из квадрата 4x4 убрать угловые клетки.

Можно ли обойти ее ходом шахматного коня и вернуться на исходную клетку, побывав на всех клетках ровно по одному разу?

Решение: Занумеруем последовательно клетки доски:

А теперь с помощью рисунка покажем, что такой обход таблицы, как указано в условии, возможен:

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

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

Другое замечание касается вида графа. Попробуйте проверить, что граф для одной и той же задачи можно нарисовать разными способами; и наоборот для разных задач можно нарисовать одинаковые по виду графы. Здесь важно лишь то, какие вершины соединены друг с другом, а какие – нет. Например, граф для задачи 1 можно нарисовать по-другому:

Такие одинаковые, но по-разному нарисованные графы, называются изоморфными .

Степени вершин и подсчет числа ребер графа

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

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

Задача 3. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими?

Решение: Допустим, что такое соединение телефонов возможно. Тогда представим себе граф, в котором вершины обозначают телефоны, а ребра – провода, их соединяющие. Подсчитаем, сколько всего получится проводов. К каждому телефону подключено ровно 5 проводов, т.е. степень каждой вершины нашего графа – 5. Чтобы найти число проводов, надо просуммировать степени всех вершин графа и полученный результат разделить на 2 (т.к. каждый провод имеет два конца, то при суммировании степеней каждый провод будет взят 2 раза). Но тогда количество проводов получится разным . Но это число не целое. Значит наше предположение о том, что можно соединить каждый телефон ровно с пятью другими, оказалось неверным.

Ответ. Соединить телефоны таким образом невозможно.

Теорема : Любой граф содержит четное число нечетных вершин.

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

Связность графа

Есть еще одно важное понятие, относящееся к графам – понятие связности.

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

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

Доказательство : Рассмотрим два произвольных А и В города и допустим, что между ними нет пути. Каждый из них соединен дорогами не менее, чем с семью другими, причем нет такого города, который был бы соединен с обоими рассматриваемыми городами (в противном случае существовал бы путь из A в B). Нарисуем часть графа, соответствующую этим городам:

Теперь явно видно, что мы получили не менее различных 16 городов, что противоречит условию задачи. Значит утверждение доказано от противного.

Если принять во внимание предыдущее определение, то утверждение задачи можно переформулировать и по-другому: “Доказать, что граф дорог страны Семерка связен.”

Теперь вы знаете, как выглядит связный граф. Несвязный граф имеет вид нескольких “кусков”, каждый из которых – либо отдельная вершина без ребер, либо связный граф. Пример несвязного графа вы видите на рисунке:

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

Задача 5 . В Тридевятом царстве только один вид транспорта – ковер-самолет. Из столицы выходит 21 ковролиния, из города Дальний – одна, а из всех остальных городов, – по 20. Докажите, что из столицы можно долететь в город Дальний.

Доказательство: Понятно, что если нарисовать граф ковролиний Царства, то он может быть несвязным. Рассмотрим компоненту связности, которая включает в себя столицу Царства. Из столицы выходит 21 ковролиния, а из любых других городов, кроме города Дальний – по 20, поэтому, чтобы выполнялся закон о четном числе нечетных вершин необходимо, чтобы и город Дальний входил в эту же самую компоненту связности. А так как компонента связности – связный граф, то из столицы существует путь по ковролиниям до города Дальний, что и требовалось доказать.

Графы Эйлера

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

Задача 6. Можно ли нарисовать изображенный на рисунке граф не отрывая карандаш от бумаги и проводя каждое ребро ровно один раз?

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

Сейчас мы доказали теорему об Эйлеровых графах:

Теорема : Эйлеров граф должен иметь не более двух нечетных вершин.

И в заключение – задача о Кенигсбергских мостах.

Задача 7. На рисунке изображена схема мостов города Кенигсберга.

Можно ли совершить прогулку так, чтобы пройти по каждому мосту ровно 1 раз?

3. Задачи к теме “Графы”

Понятие графа.

1. На квадратной доске 3x3 расставлены 4 коня так, как показано на рис.1. Можно ли сделав несколько ходов конями, переставить их в положение, показанное на рис.2?

Рис. 1

Рис. 2

Решение. Занумеруем клетки доски, как показано на рисунке:

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

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

2. В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены авиалинией в том и только в том случае, если двузначное число, образованное названиями городов, делится на 3. Можно ли долететь по воздуху из города 1 в город 9 ?

Решение. Поставив в соответствие каждому городу точку и соединив точки линией, если сумма цифр делится на 3, получим граф, в котором цифры 3, 5, 9 связаны между собой, но не связаны с остальными. Значит долететь из города 1 в город 9 нельзя.

Степени вершин и подсчет числа ребер.

3. В государстве 100 городов к из каждого города выходит 4 дороги. Сколько всего дорог в государстве.

Решение. Подсчитаем общее количество выходящих городов дорог – 100 . 4 = 400. Однако при таком подсчете каждая дорога посчитана 2 раза – она выходит из одного города и входит в другой. Значит всего дорог в два раза меньше, т.е. 200.

4. В классе 30 человек. Может ли быть так, что 9 человек имеют по 3 друга, 11 – по 4 друга, а 10 – по 5 друзей?

Ответ. Нет (теорема о четности числа нечетных вершин).

5. У короля 19 вассалов. Может ли оказаться так, что у каждого вассала 1, 5 или 9 соседей?

Ответ. Нет, не может.

6. Может ли в государстве, в котором из каждого города выходит ровно 3 дороги, быть ровно 100 дорог?

Решение . Подсчитаем число городов. Число дорог равно числу городов х, умноженному на 3 (число выходящих из каждого города дорог) и разделенному на 2 (см. задачу 3). Тогда 100 = Зх/2 => Зх=200, чего не может быть при натуральном х. Значит 100 дорог в таком государстве быть не может.

7. Докажите, что число людей, живших когда-либо на Земле и сделавших нечетное число рукопожатий, четно.

Доказательство непосредственно следует из теоремы о четности числа нечетных вершин графа.

Связность.

8. В стране из каждого города выходит 100 дорог и из каждого города можно добраться до любого другого. Одну дорогу закрыли на ремонт. Докажите, что и теперь из любого города можно добраться до любого другого.

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

Графы Эйлера.

9. Имеется группа островов, соединенных мостами так, что от каждого острова можно добраться до любого другого. Турист обошел все острова, пройдя по каждому мосту розно 1 раз. На острове Троекратном он побывал трижды. Сколько мостов ведет с Троекратного, если турист

а) не с него начал и не на нем закончил?
б) с него начал, но не на нем закончил?
в) с него начал и на нем закончил?

10. На рисунке изображен парк, разделенный на несколько частей заборами. Можно ли прогуляться по парку и его окрестностям так, чтобы перелезть через каждый забор розно 1 раз?