Рубрики

Эйлерова траектория и схема для неориентированного графа

Путь Эйлера — это путь в графе, который посещает каждый край ровно один раз. Эйлерова цепь — это эйлерова тропа, которая начинается и заканчивается в одной и той же вершине.

Как узнать, является ли данный граф эйлеровым или нет?
Проблема такая же, как следующий вопрос. «Можно ли нарисовать данный график, не снимая карандаш с бумаги и не обводя ни одного края больше одного раза».

Граф называется эйлеровым, если он имеет эйлеров цикл, и называется полу-эйлеровым, если он имеет эйлеров путь. Задача кажется похожей на гамильтонову траекторию, которая является полной задачей NP для общего графа. К счастью, мы можем найти, имеет ли данный граф эйлерову траекторию или нет за полиномиальное время. Фактически, мы можем найти это за O (V + E) время.

Ниже приведены некоторые интересные свойства неориентированных графов с эйлеровым путем и циклом. Мы можем использовать эти свойства, чтобы определить, является ли граф эйлеровым или нет.

Эйлеров цикл
Ненаправленный граф имеет цикл Эйлера, если выполняются следующие два условия.
… .A) Все вершины с ненулевой степенью связны. Мы не заботимся о вершинах с нулевой степенью, потому что они не принадлежат циклу Эйлера или Path (мы рассматриваем только все ребра).
… .B) Все вершины имеют четную степень.

Эйлерова дорожка
Ненаправленный граф имеет путь Эйлера, если выполняются следующие два условия.
… .A) То же, что и условие (а) для эйлерова цикла
… .B) Если две вершины имеют нечетную степень, а все остальные вершины имеют четную степень. Обратите внимание, что только одна вершина с нечетной степенью невозможна в неориентированном графе (сумма всех степеней всегда четна в неориентированном графе)

Обратите внимание, что граф без ребер считается эйлеровым, потому что нет ребер для прохождения.

Как это работает?
В эйлеровом пути каждый раз, когда мы посещаем вершину v, мы проходим два невидимых ребра с одной конечной точкой как v. Следовательно, все средние вершины в эйлеровом пути должны иметь четную степень. Для цикла Эйлера любая вершина может быть средней, поэтому все вершины должны иметь четную степень.

C ++

// Программа на C ++ для проверки, является ли данный граф эйлеровым или нет
#include<iostream>
#include <list>

using namespace std;

  
// Класс, представляющий неориентированный граф

class Graph

{

    int V;    // Количество вершин

    list<int> *adj;    // Динамический массив списков смежности

public:

    // Конструктор и деструктор

    Graph(int V)   {this->V = V; adj = new list<int>[V]; }

    ~Graph() { delete [] adj; } // Чтобы избежать утечки памяти

  

     // функция для добавления ребра на график

    void addEdge(int v, int w);

  

    // Метод проверки, является ли этот граф эйлеровым или нет

    int isEulerian();

  

    // Метод проверки, все ли вершины ненулевой степени связаны

    bool isConnected();

  

    // Функция для создания DFS, начиная с v. Используется в isConnected ();

    void DFSUtil(int v, bool visited[]);

};

  

void Graph::addEdge(int v, int w)

{

    adj[v].push_back(w);

    adj[w].push_back(v);  // Примечание: график не ориентирован

}

  

void Graph::DFSUtil(int v, bool visited[])

{

    // Пометить текущий узел как посещенный и распечатать его

    visited[v] = true;

  

    // Повторение для всех вершин, смежных с этой вершиной

    list<int>::iterator i;

    for (i = adj[v].begin(); i != adj[v].end(); ++i)

        if (!visited[*i])

            DFSUtil(*i, visited);

}

  
// Метод проверки, все ли вершины ненулевой степени связаны.
// В основном это обход DFS, начиная с

bool Graph::isConnected()

{

    // Пометить все вершины как не посещенные

    bool visited[V];

    int i;

    for (i = 0; i < V; i++)

        visited[i] = false;

  

    // Найти вершину с ненулевой степенью

    for (i = 0; i < V; i++)

        if (adj[i].size() != 0)

            break;

  

    // Если в графе нет ребер, вернуть true

    if (i == V)

        return true;

  

    // Запускаем обход DFS из вершины с ненулевой степенью

    DFSUtil(i, visited);

  

    // Проверяем, все ли вершины отличны от нуля

    for (i = 0; i < V; i++)

       if (visited[i] == false && adj[i].size() > 0)

            return false;

  

    return true;

}

  
/ * Функция возвращает одно из следующих значений

   0 -> Если грпа не эйлеров

   1 -> Если граф имеет эйлерову траекторию (полуэйлерово)

   2 -> Если в графе есть схема Эйлера (эйлерова) * /

int Graph::isEulerian()

{

    // Проверяем, все ли вершины ненулевой степени связаны

    if (isConnected() == false)

        return 0;

  

    // Считаем вершины с нечетной степенью

    int odd = 0;

    for (int i = 0; i < V; i++)

        if (adj[i].size() & 1)

            odd++;

  

    // Если число больше 2, то график не является эйлеровым

    if (odd > 2)

        return 0;

  

    // Если нечетное число равно 2, то полуевлерово.

    // Если нечетное число равно 0, то эйлерово

    // Обратите внимание, что нечетное число никогда не может быть 1 для неориентированного графа

    return (odd)? 1 : 2;

}

  
// Функция для запуска тестовых случаев

void test(Graph &g)

{

    int res = g.isEulerian();

    if (res == 0)

        cout << "graph is not Eulerian\n";

    else if (res == 1)

        cout << "graph has a Euler path\n";

    else

        cout << "graph has a Euler cycle\n";

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    // Давайте создадим и протестируем графики, показанные на рисунках выше

    Graph g1(5);

    g1.addEdge(1, 0);

    g1.addEdge(0, 2);

    g1.addEdge(2, 1);

    g1.addEdge(0, 3);

    g1.addEdge(3, 4);

    test(g1);

  

    Graph g2(5);

    g2.addEdge(1, 0);

    g2.addEdge(0, 2);

    g2.addEdge(2, 1);

    g2.addEdge(0, 3);

    g2.addEdge(3, 4);

    g2.addEdge(4, 0);

    test(g2);

  

    Graph g3(5);

    g3.addEdge(1, 0);

    g3.addEdge(0, 2);

    g3.addEdge(2, 1);

    g3.addEdge(0, 3);

    g3.addEdge(3, 4);

    g3.addEdge(1, 3);

    test(g3);

  

    // Давайте создадим граф с 3 вершинами

    // связаны в виде цикла

    Graph g4(3);

    g4.addEdge(0, 1);

    g4.addEdge(1, 2);

    g4.addEdge(2, 0);

    test(g4);

  

    // Давайте создадим граф со всеми вершинами

    // с нулевой степенью

    Graph g5(3);

    test(g5);

  

    return 0;

}

Джава

// Java-программа для проверки, является ли данный граф эйлеровым или нет

import java.io.*;

import java.util.*;

import java.util.LinkedList;

  
// Этот класс представляет неориентированный граф, используя список смежности
// представление

class Graph

{

    private int V;   // Количество вершин

  

    // Массив списков для представления списка смежности

    private LinkedList<Integer> adj[];

  

    // Конструктор

    Graph(int v)

    {

        V = v;

        adj = new LinkedList[v];

        for (int i=0; i<v; ++i)

            adj[i] = new LinkedList();

    }

  

    // Функция для добавления ребра в график

    void addEdge(int v, int w)

    {

        adj[v].add(w);// Добавить w в список v.

        adj[w].add(v); // График не ориентирован

    }

  

    // Функция, используемая DFS

    void DFSUtil(int v,boolean visited[])

    {

        // Пометить текущий узел как посещенный

        visited[v] = true;

  

        // Повторение для всех вершин, смежных с этой вершиной

        Iterator<Integer> i = adj[v].listIterator();

        while (i.hasNext())

        {

            int n = i.next();

            if (!visited[n])

                DFSUtil(n, visited);

        }

    }

  

    // Метод проверки, если все вершины ненулевой степени

    // связано. В основном это обход DFS, начиная с

    boolean isConnected()

    {

        // Пометить все вершины как не посещенные

        boolean visited[] = new boolean[V];

        int i;

        for (i = 0; i < V; i++)

            visited[i] = false;

  

        // Найти вершину с ненулевой степенью

        for (i = 0; i < V; i++)

            if (adj[i].size() != 0)

                break;

  

        // Если в графе нет ребер, вернуть true

        if (i == V)

            return true;

  

        // Запускаем обход DFS из вершины с ненулевой степенью

        DFSUtil(i, visited);

  

        // Проверяем, все ли вершины отличны от нуля

        for (i = 0; i < V; i++)

           if (visited[i] == false && adj[i].size() > 0)

                return false;

  

        return true;

    }

  

    / * Функция возвращает одно из следующих значений

       0 -> Если грпа не эйлеров

       1 -> Если граф имеет эйлерову траекторию (полуэйлерово)

       2 -> Если в графе есть схема Эйлера (эйлерова) * /

    int isEulerian()

    {

        // Проверяем, все ли вершины ненулевой степени связаны

        if (isConnected() == false)

            return 0;

  

        // Считаем вершины с нечетной степенью

        int odd = 0;

        for (int i = 0; i < V; i++)

            if (adj[i].size()%2!=0)

                odd++;

  

        // Если число больше 2, то график не является эйлеровым

        if (odd > 2)

            return 0;

  

        // Если нечетное число равно 2, то полуевлерово.

        // Если нечетное число равно 0, то эйлерово

        // Обратите внимание, что нечетное число никогда не может быть 1 для неориентированного графа

        return (odd==2)? 1 : 2;

    }

  

    // Функция для запуска тестовых случаев

    void test()

    {

        int res = isEulerian();

        if (res == 0)

            System.out.println("graph is not Eulerian");

        else if (res == 1)

            System.out.println("graph has a Euler path");

        else

           System.out.println("graph has a Euler cycle");

    }

  

    // Метод драйвера

    public static void main(String args[])

    {

        // Давайте создадим и протестируем графики, показанные на рисунках выше

        Graph g1 = new Graph(5);

        g1.addEdge(1, 0);

        g1.addEdge(0, 2);

        g1.addEdge(2, 1);

        g1.addEdge(0, 3);

        g1.addEdge(3, 4);

        g1.test();

  

        Graph g2 = new Graph(5);

        g2.addEdge(1, 0);

        g2.addEdge(0, 2);

        g2.addEdge(2, 1);

        g2.addEdge(0, 3);

        g2.addEdge(3, 4);

        g2.addEdge(4, 0);

        g2.test();

  

        Graph g3 = new Graph(5);

        g3.addEdge(1, 0);

        g3.addEdge(0, 2);

        g3.addEdge(2, 1);

        g3.addEdge(0, 3);

        g3.addEdge(3, 4);

        g3.addEdge(1, 3);

        g3.test();

  

        // Давайте создадим граф с 3 вершинами

        // связаны в виде цикла

        Graph g4 = new Graph(3);

        g4.addEdge(0, 1);

        g4.addEdge(1, 2);

        g4.addEdge(2, 0);

        g4.test();

  

        // Давайте создадим граф со всеми вершинами

        // с нулевой степенью

        Graph g5 = new Graph(3);

        g5.test();

    }

}
// Этот код предоставлен Aakash Hasija

питон

# Python программа для проверки, является ли данный граф эйлеровым или нет
# Сложность: O (V + E)

   

from collections import defaultdict

   
# Этот класс представляет неориентированный граф, используя представление списка смежности

class Graph:

   

    def __init__(self,vertices):

        self.V= vertices #No. вершин

        self.graph = defaultdict(list) # словарь по умолчанию для хранения графика

   

    # функция для добавления ребра на график

    def addEdge(self,u,v):

        self.graph[u].append(v)

        self.graph[v].append(u)

   

    # Функция, используемая isConnected

    def DFSUtil(self,v,visited):

        # Отметить текущий узел как посещенный

        visited[v]= True

  

        # Повторить для всех вершин, смежных с этой вершиной

        for i in self.graph[v]:

            if visited[i]==False:

                self.DFSUtil(i,visited)

   

   

    '' 'Метод, чтобы проверить, все ли вершины ненулевой степени

    связано. В основном это обход DFS, начиная с

    узел с ненулевой степенью '' '

    def isConnected(self):

   

        # Отметить все вершины как не посещенные

        visited =[False]*(self.V)

  

        # Найти вершину с ненулевой степенью

        for i in range(self.V):

            if len(self.graph[i]) > 1:

                break

  

        # Если в графе нет ребер, вернуть true

        if i == self.V-1:

            return True

  

        # Запустить обход DFS из вершины с ненулевой степенью

        self.DFSUtil(i,visited)

  

        # Проверьте, посещены ли все вершины, отличные от нуля

        for i in range(self.V):

            if visited[i]==False and len(self.graph[i]) > 0:

                return False

          

        return True

  

  

    '' 'Функция возвращает одно из следующих значений

       0 -> Если грпа не эйлеров

       1 -> Если граф имеет эйлерову траекторию (полуэйлерово)

       2 -> Если граф имеет эйлерову цепь (эйлерово) '' '

    def isEulerian(self):

        # Проверьте, все ли вершины ненулевой степени связаны

        if self.isConnected() == False:

            return 0

        else:

            # Количество вершин с нечетной степенью

            odd = 0

            for i in range(self.V):

                if len(self.graph[i]) % 2 !=0:

                    odd +=1

  

            '' 'Если нечетное число равно 2, то полуевлерово.

            Если нечетное число 0, то эйлеров

            Если число больше 2, то график не является эйлеровым

            Обратите внимание, что нечетное число никогда не может быть 1 для неориентированного графа '' '

            if odd == 0:

                return 2

            elif odd == 2:

                return 1

            elif odd > 2:

                return 0

  

  

     # Функция для запуска тестовых случаев

     def test(self):

         res = self.isEulerian()

         if res == 0:

             print "graph is not Eulerian"

         elif res ==1 :

             print "graph has a Euler path"

         else:

             print "graph has a Euler cycle"

   

   

  
# Давайте создадим и протестируем графики, показанные на рисунках выше

g1 = Graph(5);

g1.addEdge(1, 0)

g1.addEdge(0, 2)

g1.addEdge(2, 1)

g1.addEdge(0, 3)

g1.addEdge(3, 4)

g1.test()

  

g2 = Graph(5)

g2.addEdge(1, 0)

g2.addEdge(0, 2)

g2.addEdge(2, 1)

g2.addEdge(0, 3)

g2.addEdge(3, 4)

g2.addEdge(4, 0)

g2.test();

  

g3 = Graph(5)

g3.addEdge(1, 0)

g3.addEdge(0, 2)

g3.addEdge(2, 1)

g3.addEdge(0, 3)

g3.addEdge(3, 4)

g3.addEdge(1, 3)

g3.test()

  
# Давайте создадим граф с 3 вершинами
# подключен в виде цикла

g4 = Graph(3)

g4.addEdge(0, 1)

g4.addEdge(1, 2)

g4.addEdge(2, 0)

g4.test()

  
# Давайте создадим граф со всеми вершинами
# с нулевой степенью

g5 = Graph(3)

g5.test()

  
# Этот код предоставлен Ниламом Ядавом

C #

// AC # программа для проверки, является ли данный граф эйлеровым или нет

using System;

using System.Collections.Generic;

  

   
// Этот класс представляет неориентированный граф, используя список смежности
// представление

public class Graph

{

    private int V;   // Количество вершин

   

    // Массив списков для представления списка смежности

    private List<int> []adj;

   

    // Конструктор

    Graph(int v)

    {

        V = v;

        adj = new List<int>[v];

        for (int i=0; i<v; ++i)

            adj[i] = new List<int>();

    }

   

    // Функция для добавления ребра в график

    void addEdge(int v, int w)

    {

        adj[v].Add(w);// Добавить w в список v.

        adj[w].Add(v); // График не ориентирован

    }

   

    // Функция, используемая DFS

    void DFSUtil(int v,bool []visited)

    {

        // Пометить текущий узел как посещенный

        visited[v] = true;

   

        // Повторение для всех вершин, смежных с этой вершиной

        foreach(int i in adj[v]){

            int n = i;

            if (!visited[n])

                DFSUtil(n, visited);

        }

    }

   

    // Метод проверки, если все вершины ненулевой степени

    // связано. В основном это обход DFS, начиная с

    bool isConnected()

    {

        // Пометить все вершины как не посещенные

        bool []visited = new bool[V];

        int i;

        for (i = 0; i < V; i++)

            visited[i] = false;

   

        // Найти вершину с ненулевой степенью

        for (i = 0; i < V; i++)

            if (adj[i].Count != 0)

                break;

   

        // Если в графе нет ребер, вернуть true

        if (i == V)

            return true;

   

        // Запускаем обход DFS из вершины с ненулевой степенью

        DFSUtil(i, visited);

   

        // Проверяем, все ли вершины отличны от нуля

        for (i = 0; i < V; i++)

           if (visited[i] == false && adj[i].Count > 0)

                return false;

   

        return true;

    }

   

    / * Функция возвращает одно из следующих значений

       0 -> Если грпа не эйлеров

       1 -> Если граф имеет эйлерову траекторию (полуэйлерово)

       2 -> Если в графе есть схема Эйлера (эйлерова) * /

    int isEulerian()

    {

        // Проверяем, все ли вершины ненулевой степени связаны

        if (isConnected() == false)

            return 0;

   

        // Считаем вершины с нечетной степенью

        int odd = 0;

        for (int i = 0; i < V; i++)

            if (adj[i].Count%2!=0)

                odd++;

   

        // Если число больше 2, то график не является эйлеровым

        if (odd > 2)

            return 0;

   

        // Если нечетное число равно 2, то полуевлерово.

        // Если нечетное число равно 0, то эйлерово

        // Обратите внимание, что нечетное число никогда не может быть 1 для неориентированного графа

        return (odd==2)? 1 : 2;

    }

   

    // Функция для запуска тестовых случаев

    void test()

    {

        int res = isEulerian();

        if (res == 0)

            Console.WriteLine("graph is not Eulerian");

        else if (res == 1)

            Console.WriteLine("graph has a Euler path");

        else

           Console.WriteLine("graph has a Euler cycle");

    }

   

    // Метод драйвера

    public static void Main(String []args)

    {

        // Давайте создадим и протестируем графики, показанные на рисунках выше

        Graph g1 = new Graph(5);

        g1.addEdge(1, 0);

        g1.addEdge(0, 2);

        g1.addEdge(2, 1);

        g1.addEdge(0, 3);

        g1.addEdge(3, 4);

        g1.test();

   

        Graph g2 = new Graph(5);

        g2.addEdge(1, 0);

        g2.addEdge(0, 2);

        g2.addEdge(2, 1);

        g2.addEdge(0, 3);

        g2.addEdge(3, 4);

        g2.addEdge(4, 0);

        g2.test();

   

        Graph g3 = new Graph(5);

        g3.addEdge(1, 0);

        g3.addEdge(0, 2);

        g3.addEdge(2, 1);

        g3.addEdge(0, 3);

        g3.addEdge(3, 4);

        g3.addEdge(1, 3);

        g3.test();

   

        // Давайте создадим граф с 3 вершинами

        // связаны в виде цикла

        Graph g4 = new Graph(3);

        g4.addEdge(0, 1);

        g4.addEdge(1, 2);

        g4.addEdge(2, 0);

        g4.test();

   

        // Давайте создадим граф со всеми вершинами

        // с нулевой степенью

        Graph g5 = new Graph(3);

        g5.test();

    }

}

  
// Этот код предоставлен PrinciRaj1992


Выход:

graph has a Euler path
graph has a Euler cycle
graph is not Eulerian
graph has a Euler cycle
graph has a Euler cycle

Сложность времени: O (V + E)

Следующие статьи:
Эйлерова траектория и схема для ориентированных графов.
Алгоритм Флери для печати эйлерова траектории или схемы?

Ссылки:
http://en.wikipedia.org/wiki/Eulerian_path

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Эйлерова траектория и схема для неориентированного графа

0.00 (0%) 0 votes