Здравствуйте! Меня зовут Владимир Подольский, и на этой неделе мы с вами обсудим графы. Что же такое граф? У нас часто возникает такая ситуация, когда есть некоторые объекты, и между ними задано какое-то отношение. Как раз такие ситуации удобно описывать с помощью графов. Такое встречается повсюду, так что графы оказываются очень полезными. Давайте рассмотрим такой пример: например, это могут быть люди, объекты — это люди. Допустим, у нас есть пять человек, и между ними есть какое-то отношение, например, в социальной сети. Некоторые из них друзья. Например, вот A и B — это друзья, A и C — это друзья, A и E, B и C, C и D, и D и E. Тогда этих людей мы можем изобразить точками и отношения, связь между ними, изобразить отрезками. И на этой картинке можно обсуждать какие-то вопросы про этих людей. Например, можно спросить, есть ли общие друзья у C и E. Да, они есть, например, A — это общий друг, и, например, еще D — их тоже общий друг. Итак, в графах объекты будут изображаться точками. Мы будем называть их вершинами. При этом те объекты, которые связаны отношением, мы будем соединять линиями. Будем их называть ребрами. А несвязанные отношением объекты мы соединять не будем. При изображении ребра могут пересекаться, но ничего страшного. Мы знаем, где у нас вершины, ребра тоже нарисованы на картинке. Тогда графом называется множество вершин, некоторые из которых соединены ребрами. При этом важно только, какие вершины соединены, а какие нет. Конкретные изображения при этом могут быть разными. Например, на этих картинках нарисован один и тот же граф, просто мы вершину D немножко подвинули, а так соединение ребрами объектов одно и то же. Множество вершин графа обычно обозначается буквой V большое. Отдельные вершины часто обозначаются буквами v маленькая, u маленькая, и так далее. Множество ребер в графе обычно обозначается буквой E большое, а отдельные ребра обозначаются маленькой буквой e. Где же у нас могут возникать графы? Например, это могут быть транспортные задачи, где объекты — это населенные пункты, и мы соединяем ребрами те, которые соединены дорогой. Также это могут быть социальные сети, и там у нас объекты — это люди, и мы соединяем тех, которые находятся в отношении "быть друзьями". Также графы могут возникать в структурах данных, если на объектах в структуре данных есть какая-то связь. И в принципе, если у нас есть какая-то обучающая выборка, и в пространстве признаков у нас есть объекты, мы можем заводить на них какие-то отношения: например, мы можем как-то измерять расстояние между объектами пространств и признаков и соединять ребрами те, которые находятся на близком расстоянии. Хорошо, что же разрешается в графах? Например, допускаются ли петли? Допускаются ли ребра, которые соединяют вершину саму с собой? Или допускаются ли кратные ребра? Можем ли мы две вершины, два объекта соединить двумя ребрами? Можно допускать, можно нет. В принципе, здесь можно выбрать. По умолчанию мы не будем разрешать такое, мы не будем рассматривать петли, и мы не будем рассматривать графы с кратными ребрами. На самом деле можно это разрешить, и большинство рассуждений, которые у нас будут, переносятся также и на эти случаи. Бывают немножко другие ситуации, бывают ситуации, когда связи между объектами односторонние. Например, это могут быть ссылки между сайтами. У нас есть два сайта, с одного есть ссылка на другой, но это не значит, что с другого есть ссылка на первый. Также это могут быть пользователи, следящие за постами друг друга в соцсетях. Бывают односторонние отношения в соцсетях. Также это могут быть односторонние дороги в транспортных задачах. Эти ситуации тоже описываются графами, но немножко другими. Мы обсудим такие графы чуть позже.