Теория графов - проходимость

Граф проходим, если вы можете нарисовать путь между всеми вершинами, не возвращаясь к одному и тому же пути. Основываясь на этом пути, есть некоторые категории, такие как путь Эйлера и схема Эйлера, которые описаны в этой главе.

Путь Эйлера

Путь Эйлера содержит каждое ребро «G» ровно один раз, а каждую вершину «G» хотя бы один раз. Связный граф G называется проходимым, если он содержит путь Эйлера.

пример

Путь Эйлера = dcabde.

Схема Эйлера

На пути Эйлера, если начальная вершина совпадает с его конечной вершиной, то она называется схемой Эйлера.

пример

Схема Эйлера

Путь Эйлера = abcdagfeca.

Теорема Эйлера

Связный граф 'G' проходим в том и только в том случае, если число вершин с нечетной степенью в G ровно 2 или 0. Связный граф G может содержать путь Эйлера, но не схему Эйлера, если он имеет ровно две вершины с странная степень

Примечание. Этот путь Эйлера начинается с вершины нечетной степени и заканчивается другой вершиной нечетной степени.

пример

Теорема Эйлера

Путь Эйлера - beabdca - это не схема Эйлера, а путь Эйлера. Очевидно, что оно имеет ровно 2 вершины нечетной степени.

Примечание. Если в связном графе G число вершин с нечетной степенью = 0, то существует схема Эйлера.

Гамильтонов график

Связный граф G называется гамильтоновым графом, если существует цикл, содержащий все вершины G.

Каждый цикл - это цепь, но схема может содержать несколько циклов. Такой цикл называется гамильтоновым циклом группы G.

Гамильтонов путь

Связный граф называется гамильтоновым, если он содержит каждую вершину группы G ровно один раз. Такой путь называется гамильтоновым путем .

пример

Гамильтонов путь

Гамильтонов путь - Эдбак.

Примечание -

  • Схема Эйлера содержит каждое ребро графа ровно один раз.
  • В гамильтоновом цикле некоторые ребра графа могут быть пропущены.

пример

Посмотрите на следующий график -

Пример гамильтонова пути

Для приведенного выше графика -

  • Путь Эйлера существует - ложь
  • Схема Эйлера существует - ложь
  • Гамильтонов цикл существует - верно
  • Гамильтонов путь существует - верно

У G есть четыре вершины с нечетной степенью, следовательно это не проходимо. Пропуская внутренние ребра, граф имеет гамильтонов цикл, проходящий через все вершины.