Вот. Но это не единственная тонкость,
которая может возникнуть,
и ради которой придется добавить какую-нибудь частичку перед словом "граф".
Помимо ориентации, как я уже успел вскользь сказать,
бывают кратные ребра, и бывают петли.
Ну, давайте в качестве следующего примера рассмотрим классическую задачу,
которую мы обязательно будем еще обсуждать в рамках этого курса.
Эта классическая задача возникла в 18-ом веке.
Это то, что называется задача про кёнигсбергские мосты.
Кёнигсберг — это Калининград нынешний.
И вот в те годы, в 18-ом веке,
мосты там были устроены совершенно конкретным способом.
Я нарисую очень плохо, но будет понятно.
Схематично рисуется так.
Есть два островка суши, находящихся на реках,
протекающих через этот город.
Есть большая суша здесь, и есть большая суша здесь.
Вот это вот суша.
Значит, имеется два моста, которые соединяют вот
этот вот островок с большим куском суши, так сказать, на севере, условно говоря.
Есть два моста, которые, опять же, первый островок соединяют с южной,
с южной частью суши.
Есть один мост, который соединяет два островка.
И здесь тоже по одному мосту.
Так вот задача, которая стояла в 18-ом веке — она не сложная на самом деле.
Мы ее с вами обязательно решим, это классика теории графов.
Задача была такая.
Говорилось так: давайте попробуем стартовать из
какой-нибудь части суши, ну например, из вот этой.
Или с вот этого острова, или с вот этого острова, или из вот этой части суши.
Так, стартовали, дальше пошли по некоторому мосту,
перешли на следующую часть суши, опять же прошли по некоторому мосту и так далее.
Чего мы хотим достичь?
Мы хотим пройти по всем мостам.
Прежде всего мы хотим пройти по всем мостам, то есть все мосты мы хотим обойти.
При этом мы очень хотим ни разу не повторить мост в рамках нашего движения,
то есть,
если мы по этому мосту прошли, то больше мы по этому мосту уже ходить не будем.
Если мы по этому мосту в очередном шаге прошли,
то и по этому мосту мы дальше уже ходить не будем.
Вот мы хотим обойти все мосты, при этом каждый мост ровно один раз,
и вернуться, внимание, в ту же самую часть суши, с которой стартовали.
Вот попробуем так двигаться, двигаться, двигаться...
Ой! Начали здесь,
а закончили здесь — вот не получается, не вернулись в эту часть суши.
Но может быть, плохо двигались?
Может быть, есть какой-то другой маршрут — спрашивала задача.
Ну и вот, легко понять, что на самом деле, конечно,
такого маршрута не существует, я об этом скажу подробнее позже.
А Эйлер по этому случаю развил некую теорию, которая очень хорошо укладывается
тоже в теорию графов и хорошо коррелирует с понятием графа.
Но вот именно здесь возникает та самая тонкость,
которая называется "кратные ребра".
Давайте попробуем эту картинку сделать теоретико-графовой,
то есть представить вот эту вот картину как граф.
А именно, вершины графа — это просто части суши,
которые есть у нас в распоряжении.
Вот видите, эта вершина отвечает южной части суши, эта — островку большому,
эта — островку маленькому, а эта — северной части суши.
Нам же никак не важен размер частей суши,
нам важно только попадание на них по мостам.
Так вот мосты и будут ребрами нашего графа.
Видите, какая тонкость.
Если мы вот эту часть суши соединяем с вот этой,
то мостов-то у нас два, и, стало быть, ребер тоже получается два.
То же самое касается соединения между островком и южной частью суши,
здесь одно ребро, здесь одно ребро, здесь одно ребро.
И возникает вот такой вот интересный граф, у которого — внимание!
— кратные ребра.
То есть ребра, которые встречаются между двумя вершинами сразу несколько раз.
Вы, конечно, можете сказать, а здесь что, не кратные ребра?
Я скажу, нет, не кратные.
Дело в том, что это разные ребра.
Вот это ребро, оно направлено от x к y,
а это — другое ребро, которое направлено от y к x.
Здесь же никакой разницы между этими ребрами нет.
Если хотите, вы пойдете по этому мосту, если хотите, вы направитесь по этому.
И никакой принципиальной разницы между мостами не существует.
Вопрос только в том, по какому из них пойти.
Это совершенно другая ситуация.
Так вот графы, у которых допускаются кратности в ребрах,
называются мультиграфами для того, чтобы их аккуратно отличать от обыкновенных,
простых графов, которые у нас были в первых двух примерах.
Итак, видите, есть простые, они же обыкновенные графы,
есть орграфы — ориентированные графы, и есть мультиграфы.