В данном параграфе мы разберём основные понятия и определения теории графов — раздела математики, который изучает графы, их природу, структуры и алгоритмы. Также посмотрим, где можно встретить графы в реальной жизни.
Граф состоит из множества вершин, соединённых ребрами. По сути, рёбра и вершины — базовые понятия. Обычно граф обозначают , где — множество вершин, — множество рёбер/дуг. Проведём аналогию с картой метро, которую можно рассматривать как граф, где станции — вершины, а перегоны — рёбра. Другим примером может служить обычная карта, где населенные пункты — вершины графа, а рёбра — соединяющие их дороги. Генеалогические деревья, блок-схемы, схемы авиалиний и железных дорог — всё это примеры графов.
Рёбра и вершины графа могут иметь свои имена. Посмотрим на пример графа на рисунке ниже.
Граф может быть ориентированным или неориентированным. В неориентированном графе рёбра не имеют направления, то есть движение по ним возможно в двух направлениях. В ориентированном графе рёбра обычно называют дугами. Пройти по дуге можно только в заданном направлении. Пример ориентированного графа приведён на рисунке ниже. В дальнейшем под понятием граф мы будем понимать именно неориентированный граф.
В графе могут быть рёбра и дуги особого типа, которые входят и выходят из одной вершины. Такие рёбра и дуги называются петлями.
Между рёбрами и вершинами в графах существуют отношения смежности и инцидентности. Термин смежность применяется к объектам одного вида — смежными между собой могут быть вершины и рёбра. Одна вершина смежна другой, если они соединены дугой или ребром. Одно ребро смежно другому ребру, если у них есть общая вершина, из которой они выходят.
Понятие инцидентности применяется к рёбрам и вершинам. Ребро инцидентно вершине, если это ребро выходит из вершины.
Помимо обычных графов, существуют ещё графы особого вида. Например, мультиграф — граф, у которого может быть несколько кратных рёбер или дуг. Пример ориентированного и неориентированного мультиграфа приведён на рисунке ниже.
Рёбрам графа, при необходимости, можно задать веса. В таком случае граф становится взвешенным или нагруженным. В качестве веса может выступать, например, расстояние между городами. На рисунке ниже показан пример взвешенного графа.
В рамках данного параграфа нам также понадобится знать определение двудольного графа. Как следует из названия, граф состоит из двух долей, в каждой из которых никакие две вершины не смежны. На рисунке ниже можно увидеть, что вершины 1, 2 и 3 принадлежат одной доле, а вершины 4 и 5 другой.
Как вы думаете, а может ли граф вообще не содержать ребер? Да, такое бывает. В этом случае говорят о нуль-графе.
А может быть и обратная ситуация, когда граф содержит все возможные ребра или дуги. Такие графы называются полными. Посмотрите на пример полного графа ниже.
💡 Остановитесь и подумайте:
Сколько рёбер может быть в полном неориентированном графе? А в ориентированном?
Двудольный граф также может быть полным. Полный двудольный граф — граф, содержащий все возможные рёбра или дуги. Пример полного двудольного графа изображён ниже.
В графе можно построить путь — последовательность связанных рёбер, которые соединяют вершины графа. Цикл — путь, который начинается и заканчивается в одной и той же вершине.
А может ли в графе отсутствовать цикл? Да, может, и в этом случае речь о таком графе как дерево. Дерево — граф без циклов.
Графы могут быть связными и не связными. Связный граф тот, в котором от всех вершин до каждой существует путь. Пример несвязного графа приведён на рисунке ниже.
При этом в ориентированном графе говорят о сильной и слабой связности. Ориентированный граф называется:
- слабо связным - если его неориентированный аналог является связным;
- сильно связным - если всякая вершина v достижима из любой вершины u.
Очевидно, что любой сильно связный граф, также является и слабо связным.
Важно отметить, что графы имеют свои характеристики. Например, для вершин графа существует понятие степени. Степень вершины — число инцидентных этой вершине рёбер. Обычно степень вершины обозначают функцией . На рисунке ниже, , , , .
В ориентированном графе говорят про полустепени исхода и захода. Под полустепенью исхода понимается количество дуг, выходящих из вершины. Под полустепенью захода понимают число дуг, заходящих в вершину. Обычно, полустепень исхода обозначают , а полустепень захода — .
Если речь про петли, то в случае неориентированного графа она учитывается как два ребра, а в случае ориентированного для вершины эта дуга учитывается и в полустепени исхода, и в полустепени захода.
✒️ Упражнение:
Для ориентированного графа, изображенного на рисунке 2 посчитайте полустепени исхода и захода.