Прикладные задачи теории графов кратко

Обновлено: 30.06.2024

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

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

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

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

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

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

… Это решение по своему характеру; по-видимому, имеет мало отношения к математике, и мне непонятно, почему следует скорее от математика ожидать этого решения, нежели от какого-нибудь другого человека, ибо это решение подкрепляется одним только рассуждением и нет необходимости привлекать для нахождения этого решения какие-либо законы, свойственные математике.

Из письма Леонарда Эйлера к своему другу Карлу Готлибу Элеру, 03 [14] апреля 1736 г. [1]

Рис. 1. Кёнигсберг на гравюре 17 века.

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

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

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

Из письма Леонарда Эйлера к Джиованни Джакобо Маринони, 13 [24] марта 1736 г. [2]

(Судя по письмам Леонарда Эйлера, великий ученый не без удовольствия решал и другие головоломные задачи..)

Задача о семи мостах

Наконец, ты, славнейший муж, выражаешь желание ознакомиться с моим способом построения мостов; охотно представляю этот способ на твой суд. Ибо, когда ты попросил у меня решения этой проблемы, приспособленной к частному случаю Кёнигсберга, ты, вероятно, считал, что я предложил такого рода построение мостов, но я не сделал это, а только доказал, что такое построение вообще не может иметь места, и это следует принять вместо решения. Способ же мой является универсальным , так как с его помощью в любом предложенном мне случае этого рода я тотчас могу решить, следует ли строить переход с помощью отдельных мостов или нет, и в первом случае [могу установить], каким образом этот переход следует осуществить. Далее я изложу мой способ, а также опишу путь, которым я к нему пришел.

Карлу Готлибу Элеру, 03 [14] апреля 1736

Я рассмотрел произвольно взятую фигуру разветвления реки, а также мосты а, b, с, d, e, f, как это указано на рисунке, и установил, что возможен переход, который я представляю следующим образом. Области, отделенные друг от друга водой, я называю буквами А, В, С, и когда предполагается переход через мосты из одной области в другую, [а именно] переход из А в В через мост или а или b, — наиболее удобно назвать [буквами] АВ, из которых первая буква А будет обозначать область, из которой переходят. Итак, АВСАСАВ будет определять переход, совершаемый через все мосты по одному разу; число этих букв должно быть на единицу больше, чем число мостов; это должно иметь место при любом возможном переходе описанным способом, в чем каждому легче убедиться самому, чем доказывать. Теперь я рассматриваю, сколько раз в ряде букв А, В, С, А, С, А, В должны встретиться буквы ABC, о чем нужно судить по числу мостов, ведущих в каждую из областей. Так, к области А ведут пять мостов: а, b, с, d, e, и сколько раз буква А встречается в середине того ряда, столько раз встречаются два из этих мостов, ибо с одной стороны нужно перейти в область А, с другой стороны — выйти оттуда. Если А встречается или в начале, или в конце того ряда, тогда единственный переход моста соответствует А. Отсюда следует, что, если число мостов, ведущих в область А, будет нечетным, тогда переход через все мосты не может совершиться иначе, чем таким образом, чтобы он или начинался в области А, или заканчивался в области А. А если число мостов, ведущих к А, будет четным, тогда переход может быть совершен и без этого условия, чтобы начинаться или заканчиваться в А, но если он начинается в А, то должен будет там же и закончиться. Отсюда вытекает, что в ряде АВСАСАВ любая буква, за исключением первой и последней, обозначает переход, ведущий через два моста в область, обозначенную этой буквой.

Следовательно, надо держаться следующего правила: если на каком-либо рисунке число мостов, ведущих в некоторую область, будет нечетным, тогда желаемый переход через все мосты одновременно не может быть осуществлен иначе, как если переход или начинается, или заканчивается в этой области. А если число мостов четное, отсюда не может возникнуть никакого затруднения, так как ни начало, ни конец перехода при этом не фиксируются. Отсюда следует такое общее правило: если будет больше чем две области, к которым ведет нечетное количество мостов, тогда желательный переход вообще не может быть совершен. Ибо представляется совершенно невозможным, чтобы переход и начинался, и заканчивался в какой-нибудь одной из этих областей. А если будут только две области такого рода (так как не могут быть даны одна область этого рода или нечетное число областей), тогда может быть совершен переход через все мосты, но с таким условием, чтобы начало перехода было в одной, а конец в другой из этих областей. Когда в предложенной фигуре А и В есть области, к которым ведет нечетное число мостов, а число мостов, ведущих к С, является четным, то я считаю, что переход или построение мостов может иметь место, если переход начинается или из А, или из В, а если же кто-нибудь пожелает начать переход из С, то он никогда не сможет достигнуть цели. В расположении кенигсбергских мостов я имею четыре области А, В, С, D, взаимно отделенные друг от друга водой, к каждой из которых ведет нечетное число мостов.

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

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

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

Следствие Формулы, связывающее пространства иррациональных и мнимых чисел:

Поскольку из Формулы Эйлера следует, что , нетрудно видеть, что

Впрочем, впечатлиться можно простым перечислением заслуг этого великого человека перед наукой…

А мостов могло быть и больше.

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

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

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

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

Пути и деревья

Графические схемы, конечно же, не исчерпываются замкнутыми маршрутами, и наш путь ведет нас к деревьям…

Мне эта головоломка показалась несколько напоминающей задачу Дьюдени, обремененную, однако, несколькими нюансами.

Разработчиком (создателем, творцом, демиургом) этого образца неординарной мысли, шедевра изощренной человеческой изобретательности отмечен Donghoon Pee – творец, видимо, скромный и незаслуженно малоизвестный здесь на Хабре,– последнюю несправедливость мы сейчас исправим, хотя, конечно, загубим интригу… Мне и самому жалко лишать читателей Хабра возможности самостоятельно поразмыслить над головоломкой 2&1 автора Donghoon Pee – могу лишь посоветовать тем, кто страстно желает решить головоломку самостоятельно, закрыть ладошками рисунки и часть относящегося к головоломке текста ниже.

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

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

Задача с четырьмя цветными кубиками

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

граф кубика в этой головоломке – это графическая модель, в 4-х узлах которой расположены 4-е цвета, а каждое ребро указывает/связывает пару противоположных граней : остроумная мысль, пришедшая в голову F. De Carteblanche (Cedric A. B. Smith) заключалась в том, что два набора по четыре цвета в каждом могут быть описаны в виде графа с узлами степени 2 , где сами узлы означают цвета, а ребра графа указывают на то, что пара состоит в различных, а не в одном, наборах – соотнеся пару с родительским кубом (путем нумерации ребер), мы получим однозначные указания для размещения в пирамиде этого комплекта граней.

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

Обратное моделирование

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

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

Изоморфизм

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

Вместо заключения

Очень надеюсь, что чтение не было скучным. Возможно, кому-то оказалось отчасти полезным. И практически уверен, что количество нарисованных конвертиков к завтрашнему дню несколько возрастет, и кто-то наконец найдет в себе силы и мотивацию отвлечь наследника от его гаджета какой-нибудь занимательной и умной задачей. Эйлер вот не пренебрегал…

1.↑ Леонард Эйлер. Письма к ученым, Издательство АН СССР, 1963, стр.339
2.↑ Леонард Эйлер. Письма к ученым, Издательство АН СССР, 1963, стр.153
3.↑ Генри Э. Дьюдени. 520 головоломок. Составитель и редактор американского издания М. Гарднер, Издательство МИР, Москва, 1975

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

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

Глава 6. ПРИКЛАДНЫЕ ЗАДАЧИ ТЕОРИИ ГРАФОВ

6.1. Введение

Изучать теорию графов без учета возможных приложений — значит потерять основную ее сущность. Учитывая важность сказанного, мы разделили книгу на две части. Вторая часть Полностью посвящена краткому из? ложению некоторых интересных прикладных задач. Цель настоящей главы состоит в том, чтобы с помощью

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

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

История возникновения теории графов

Леонард Эйлер и задача о Кёнигсберских мостах

Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов.

Издавна среди жителей Кёнигсберга (теперь Калининграда) была распространена такая загадка: как пройти по всем мостам, не проходя ни по одному из них дважды? Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически, во время прогулок. Но никому это не удавалось, однако не удавалось и доказать, что это даже теоретически невозможно.

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

Для того, чтобы решить эту задачу, Эйлер сделал специальные обозначения. Каждую часть суши (остров или берег реки) он обозначил кружком на бумаге, а затем соединил линиями те кружки, между которыми существуют мосты. Такие обозначения подчеркивают, что в этой задаче фактическое расположение, форма, длина и другие свойства объектов не представляют интереса, важны только связи между ними. Такая картинка на бумаге или на экране компьютера называется графом. Кружки — это его вершины, а линии — рёбра. Размышляя над этой и другими картинками из кружков и линий, Эйлер пришел к следующим выводам о графах:

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

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

Проблема четырёх красок

Проблема четырёх красок — математическая задача, предложенная Гутри в 1852 году.

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

Иначе говоря, показать что хроматическое число плоского графа не превосходит 4.

О доказательстве

К. Аппель и В. Хакен доказали в 1976 г., что так можно раскрасить любую карту. Это была первая крупная математическая теорема, для доказательства которой был применён компьютер. Несмотря на последующие упрощения, доказательство практически невозможно проверить, не используя компьютер. Поэтому некоторые математики отнеслись к этому доказательству с недоверием, что объяснялось не только использованием компьютера, но и громоздкостью описания алгоритма первых доказательств (741 страница), впоследствии были предложены более компактные алгоритмы и скорректирован ряд ошибок. Проблема четырех красок является одним из известнейших прецедентов неклассического доказательства в современной математике.

Определения теории графов

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

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

Пример ориентированного графа

Иногда бывает полезно связать с ребрами графа какие-то числа. Это могут быть длины дорог или плата за проезд, если граф моделирует карту какой-то местности. В таком случае граф называется взвешенным, а сами числа — весами.

Пример: граф с шестью вершинами и семью рёбрами

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

Ниже приведены полные графы с числом вершин от 1 до 8 и количества их рёбер.

K₁ : 0	K₂ : 1	K₃ : 3	K₄ : 6

K₅ : 10	K₆ : 15	K₇ : 21	K₈ : 28

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

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

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

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

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

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

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

Две вершины A и B в графе называются связными (несвязными), если в нем существует (не существует) путь, ведущий из A в B.

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

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

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

Представление графов в памяти

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

Матрица смежности

Самый простой способ сохранить граф в памяти — матрица смежности. Нарисуем таблицу, которая чем-то напоминает таблицу умножения: в первой строчке и в первом столбце будут стоять номера (или любые названия) вершин, а на пересечении столбца и строки будем ставить, например, 1 если между этими вершинами есть ребро и 0 если нет. Кроме 1 и 0 можно ставить, например, вес ребра, а для обозначения отсутствия ребра — просто очень большое число. Какой именно вариант использовать, зависит от каждой конкретной задачи. Также задача определяет, что ставить на диагонали получившейся матрицы.

$\begin</p> <p> 1 & 1 & 0 & 0 & 1 & 0\\ 1 & 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0\\ \end$

Граф и его матрица смежности.

В первой строке входного файла заданы числа $N$ и $M$ через пробел — количество вершин и рёбер в графе, соответственно ($1 \le N \le 100$, $0 \le M \le 10 000$). Следующие $M$ строк содержат по два числа $u_i$ и $v_i$ через пробел ($1 \le u_i, v_i \le N$); каждая строка означает, что в графе существует ребро между вершинами $u_i$ и $v_i$. Рёбра нумеруются в том порядке, в котором они даны во входном файле, начиная с единицы.

Напишем функцию, считывающую граф как матрицу смежности:

Список смежности

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

Посмотрим, как это пишется на Python с тем же форматом входных данных:

Другие способы

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

Основные задачи теории графов

Обходы графа

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

Обход в глубину (DFS)

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

Обычно алгоритм DFS реализуется с помощью списков смежности и рекурсии. Требуется лишь создать функцию dfs(v) , которая будет просматривать всех соседей вершины v и запускать себя для каждого из них. Единственное, что требуется, кроме этого — список уже посещённых вершин, иначе функция может войти в бесконечный цикл.

Напишем функцию dfs на языке Python с использованием списков смежности:

Теперь достаточно запустить обход из стартовой вершины. Например, так: dfs(0) .

Обход в ширину (BFS)

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

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

Поиск кратчайших путей

Очень часто требуется найти кратчайший путь между двумя вершинами во взвешенном графе. Очевидный пример — прокладка маршрута по карте. Для решения этой задачи существует большое количество алгоритмов, в числе которых алгоритм Флойда и алгоритм Дейкстры. Алгоритм Флойда является самым простым, но очень неоптимальным — его сложность $O(n^3)$. Алгоритм Дейкстры быстрее ($O(n^2)$ или $O(n \log n)$, в зависимости от реализации), но имеет некоторые ограничения.

Алгоритм устроен так: для каждой вершины графа, пусть её номер будет $k$, просматриваются все пары вершин, пусть это $i$ и $j$. Если сумма текущей известной длины пути из $i$ в $k$ и из $k$ в $j$ меньше, чем из $i$ в $j$, то в клетке, соответствующей пути из $i$ в $j$, запоминаем длину пути через $k$, иначе ничего делать не требуется. Таким образом, алгоритм содержит три вложенных цикла, поэтому его сложность — $O(n^3)$.

Посмотрим, как реализовать этот алгоритм на Python:

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

Алгоритм Дейкстры будет рассматриваться на зимней очной сессии.

Другие задачи

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

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