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

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

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

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

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

Семь мостов Кёнигсберга

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

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

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

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

Есть четыре разных места: два острова и две части материка. И семь мостов. Интересно узнать, существует ли какая-либо закономерность в отношении количества мостов, связанных с островами или материком (мы будем использовать термин “земля” для обозначения четырех различных мест)?

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

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

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

Изменим условие

Давайте добавим новый мост, чтобы узнать, как изменится количество общих соединённых мостов, и решит ли он проблему:

Теперь, когда у нас есть два четных (4 и 4) и два нечетных (3 и 5) числа мостов, соединяющих четыре части земли, давайте нарисуем новый маршрут с добавлением этого нового моста.

Завтра рассмотрим это на граффах!👍

Искусственный интеллект с примерами на Python
Автор книги: Джоши П.
Год издания: 2019

Переходим к графам

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

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

itertools.combinations

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

#полезностьдня

Давайте посмотрим на метод combinations. Он принимает в качестве аргументов итерируемый объект и целое число. В результате получаем генератор, состоящий из всех возможных комбинаций итерируемого объекта. Максимальная длина последовательности равна указанному целому числу. Сочетания не дублируются:

import itertools

list(itertools.combinations([1, 2, 3, 4], 2))

[(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]