Граф можно обойти, если вы можете нарисовать путь между всеми вершинами, не возвращаясь к одному и тому же пути. Основываясь на этом пути, есть некоторые категории, такие как путь Эйлера и схема Эйлера, которые описаны в этой главе.
Путь Эйлера
Путь Эйлера содержит каждое ребро «G» ровно один раз, а каждую вершину «G» хотя бы один раз. Связный граф G называется проходимым, если он содержит путь Эйлера.
пример
Путь Эйлера = dcabde.
Схема Эйлера
На пути Эйлера, если начальная вершина совпадает с его конечной вершиной, то она называется схемой Эйлера.
пример
Путь Эйлера = abcdagfeca.
Схема Эйлера
Связный граф ‘G’ проходим в том и только в том случае, если число вершин с нечетной степенью в G ровно 2 или 0. Связный граф G может содержать путь Эйлера, но не схему Эйлера, если он имеет ровно две вершины с странная степень.
Примечание. Этот путь Эйлера начинается с вершины нечетной степени и заканчивается другой вершиной нечетной степени.
пример
Путь Эйлера — beabdca — это не схема Эйлера, а путь Эйлера. Очевидно, что оно имеет ровно 2 вершины нечетной степени.
Примечание. Если в связном графе G число вершин с нечетной степенью = 0, то существует схема Эйлера.
Гамильтонов график
Связный граф G называется гамильтоновым графом, если существует цикл, содержащий все вершины G.
Каждый цикл является схемой, но схема может содержать несколько циклов. Такой цикл называется гамильтоновым циклом группы G.
Гамильтонов путь
Связный граф называется гамильтоновым, если он содержит каждую вершину группы G ровно один раз. Такой путь называется гамильтоновым путем .
пример
Гамильтонов путь — Эдбак.
Примечание —
- Схема Эйлера содержит каждое ребро графа ровно один раз.
- В гамильтоновом цикле некоторые ребра графа могут быть пропущены.
пример
Посмотрите на следующий график —
Для приведенного выше графика —
- Путь Эйлера существует — ложь
- Схема Эйлера существует — ложь
- Гамильтонов цикл существует — верно
- Гамильтонов путь существует — верно
У G есть четыре вершины с нечетной степенью, следовательно это не проходимо. Пропуская внутренние ребра, граф имеет гамильтонов цикл, проходящий через все вершины.