Теория графов - самые основные понятия

Граф (от греческого "пишу") - множество V вершин и набор E неупорядоченных и упорядоченных пар вершин; обычно граф обозначают как G(V, E).

Ребро - неупорядоченная пара вершин.
Дуга - упорядоченная пара вершин.

То-есть дуга имеет определённое направление, а ребро нет.

Граф, содержащий только ребра, называется неориентированным (или неорграфом);
Граф, содержащий только дуги - ориентированным (или орграфом).

Кратные дуги и рёбра - когда две вершины соединены несколькими рёбрами. либо несколькими однонаправленными дугами.

Мультиграф - граф, имеющий кратные дуги или рёбра.

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

Псевдограф — граф, содержащий петли.

Вершины, соединенные ребром или дугой, называются смежными.
Ребра, имеющие общую вершину, тоже называются смежными.

Инцидентность — понятие, используемое только в отношении ребра и вершины: если v1,v2 — вершины, а e = (v1,v2) — соединяющее их ребро, тогда вершина v1  и ребро e инцидентны, вершина v2 и ребро e тоже инцидентны. Две вершины (или два ребра) инцидентными быть не могут.

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

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

Полный граф - граф. в котором каждая вершина соединена с каждой.
Полный граф — простой граф, в котором каждая пара различных вершин смежна.

Полустепень захода (исхода) вершины – количество дуг, заходящих (выходящих) в (из) вершину (ы).

Степень (валентность) вершины - это количество вершин, соединённых с данной вершиной, либо - количество рёбер графа, инцидентных данной  вершине.

Голая вершина графа - изолированная вершина без петель.

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

Вход и выход графа - вершины, имеющие соответствующее смысловое значение в рамках конкретной задачи.

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

Цепь в графе — маршрут, все рёбра которого различны.

Простой граф — граф, в котором нет кратных рёбер и петель.

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

Ориентированный граф G(V, X) называется односторонне связным, если для любой пары вершин v_i, v_j существует путь  либо из vi в vj, либо из v_j в v_i.

Ориентированный граф G(V, X) называется сильно связным, если для любой пары вершин v_i, v_j существует путь и из vi в vj, и из v_j в v_i.



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

Эйлеров цикл — это эйлеров путь, являющийся циклом.
Эйлеров граф — граф, содержащий эйлеров цикл.
Полуэйлеров граф — граф, содержащий эйлеров путь (цепь).

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

Граф является гамильтоновым тогда и только тогда, когда его замыкание — гамильтонов граф.

Контур — замкнутый путь в орграфе.

Критический путь графа — путь максимальной длины в ориентированном ациклическом графе.