Предположим, что в некотором графе можно по рёбрам «пройти» из вершины А в вершину В, то есть существует последовательность рёбер, соединяющих вершины А и В.
Такую последовательность называют путём из вершины А в вершину В.
Путь между двумя вершинами - это последовательность рёбер, которая их соединяет.
В графе, показанном на рисунке, есть несколько путей из вершины А в вершину В. Например, есть путь, состоящий из рёбер АС и СВ. Этот путь можно обозначить тремя буквами — АСВ. Есть более длинный путь АDFЕВ. Можно придумать более сложный путь, который заставит нас немного «покружить», — АDСАDСВ.
В путях АСВ и АDFЕВ вершины не повторяются. Такие пути называют простыми путями или цепями.
Цепь (простой путь) — это путь в графе из одной вершины в другую, в котором вершины и рёбра не повторяются.
Если граф состоит из одной-единственной цепи, то такой граф также называют цепью. Граф без рёбер, состоящий из единственной вершины, также считают цепью.
Иногда возникает необходимость выйти из вершины и вернуться в неё же. Такие возвращающиеся в начальную точку пути называют циклами.
Цикл в графе — это замкнутый путь, у которого начало и конец в одной вершине, а рёбра и промежуточные вершины не повторяются.
Простейший цикл — петля, которая состоит из одной вершины и одного ребра.
Начальной вершиной цикла можно считать любую вершину. Граф на рисунке имеет цикл АDСА. Этот же цикл можно обозначить DСАD, или САDС, или просто АDС, как мы обычно обозначаем треугольники в геометрии. Если граф состоит из одного-единственного цикла, то такой граф также называют циклом.
Граф называется связным, если две любые вершины в этом графе соединены путём.
На рисунке выше показаны два графа — слева связный, а справа — несвязный, который можно представить как два отдельных связных графа.
Упражнения здесь