Рубрики

Схема Эйлера в ориентированном графе

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

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

Например, следующий граф имеет эйлеров цикл как {1, 0, 3, 4, 0, 2, 1}

Как проверить, является ли ориентированный граф эйлеровым?
Ориентированный граф имеет эйлеров цикл, если выполняются следующие условия (Источник: Wiki )
1) Все вершины с ненулевой степенью принадлежат одной сильно связной компоненте .
2) По степени равен степени выхода для каждой вершины.

Мы можем обнаружить односвязный компонент, используя простой алгоритм Kosaraju на основе DFS .
Чтобы сравнить степень и степень, нам нужно хранить степень и степень каждой вершины. Степень выхода может быть получена размером списка смежности. В степени можно сохранить, создав массив размером, равным количеству вершин.

Ниже приведены реализации C ++ и Java вышеуказанного подхода.

C ++

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

using namespace std;

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

class Graph

{

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

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

    int *in;

public:

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

    Graph(int V);

    ~Graph()   { delete [] adj; delete [] in; }

  

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

    void addEdge(int v, int w) { adj[v].push_back(w);  (in[w])++; }

  

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

    bool isEulerianCycle();

  

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

    bool isSC();

  

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

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

  

    Graph getTranspose();

};

  

Graph::Graph(int V)

{

    this->V = V;

    adj = new list<int>[V];

    in = new int[V];

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

       in[i] = 0;

}

  
/ * Эта функция возвращает true, если ориентированный граф имеет эйлерово

   цикл, в противном случае возвращает false * /

bool Graph::isEulerianCycle()

{

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

    if (isSC() == false)

        return false;

  

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

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

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

            return false;

  

    return true;

}

  
// Рекурсивная функция для выполнения DFS, начиная с 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);

}

  
// Функция, которая возвращает реверс (или транспонирование) этого графа
// Эта функция нужна в isSC ()
Graph Graph::getTranspose()
{

    Graph g(V);

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

    {

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

        list<int>::iterator i;

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

        {

            g.adj[*i].push_back(v);

            (g.in[v])++;

        }

    }

    return g;

}

  
// Эта функция возвращает true, если все вершины ненулевой степени
// График сильно связан (пожалуйста, обратитесь
// https://www.geeksforgeeks.org/connectivity-in-a-directed-graph/amp/ )

bool Graph::isSC()

{

    // Пометить все вершины как не посещенные (для первой DFS)

    bool visited[V];

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

        visited[i] = false;

  

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

    int n;

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

        if (adj[n].size() > 0)

          break;

  

    // Выполнение обхода DFS, начиная с первой вершины, не равной нулю.

    DFSUtil(n, visited);

  

     // Если обход DFS не посещает все вершины, вернуть false.

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

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

              return false;

  

    // Создать перевернутый график

    Graph gr = getTranspose();

  

    // Пометить все вершины как не посещенные (для второго DFS)

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

        visited[i] = false;

  

    // Делаем DFS для обратного графа, начиная с первой вершины.

    // Начинающая вершина должна быть той же отправной точкой первой DFS

    gr.DFSUtil(n, visited);

  

    // Если все вершины не посещены во второй DFS, то

    // вернуть ложь

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

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

             return false;

  

    return true;

}

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

int main()

{

    // Создать график, приведенный на диаграмме выше

    Graph g(5);

    g.addEdge(1, 0);

    g.addEdge(0, 2);

    g.addEdge(2, 1);

    g.addEdge(0, 3);

    g.addEdge(3, 4);

    g.addEdge(4, 0);

  

    if (g.isEulerianCycle())

       cout << "Given directed graph is eulerian n";

    else

       cout << "Given directed graph is NOT eulerian n";

    return 0;

}

Джава

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

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

import java.io.*;

import java.util.*;

import java.util.LinkedList;

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

class Graph

{

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

    private LinkedList<Integer> adj[];// Список смежности

    private int in[];            // поддержание в степени

  

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

    Graph(int v)

    {

        V = v;

        adj = new LinkedList[v];

        in = new int[V];

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

        {

            adj[i] = new LinkedList();

            in[i]  = 0;

        }

    }

  

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

    void addEdge(int v,int w)

    {

        adj[v].add(w);

        in[w]++;

    }

  

    // Рекурсивная функция для печати DFS, начиная с v

    void DFSUtil(int v,Boolean visited[])

    {

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

        visited[v] = true;

  

        int n;

  

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

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

        while (i.hasNext())

        {

            n = i.next();

            if (!visited[n])

                DFSUtil(n,visited);

        }

    }

  

    // Функция, которая возвращает реверс (или транспонирование) этого графа

    Graph getTranspose()

    {

        Graph g = new Graph(V);

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

        {

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

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

            while (i.hasNext())

            {

                g.adj[i.next()].add(v);

                (g.in[v])++;

            }

        }

        return g;

    }

  

    // Основная функция, которая возвращает true, если граф сильно

    // связано

    Boolean isSC()

    {

        // Шаг 1: Отметить все вершины как не посещенные (Для

        // первая DFS)

        Boolean visited[] = new Boolean[V];

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

            visited[i] = false;

  

        // Шаг 2: Выполнить обход DFS, начиная с первой вершины.

        DFSUtil(0, visited);

  

        // Если обход DFS не посещает все вершины, вернуть false.

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

            if (visited[i] == false)

                return false;

  

        // Шаг 3: Создать перевернутый график

        Graph gr = getTranspose();

  

        // Шаг 4: Пометить все вершины как не посещенные (для второго DFS)

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

            visited[i] = false;

  

        // Шаг 5: сделать DFS для обратного графа, начиная с первой вершины.

        // Начинающая вершина должна быть той же отправной точкой первой DFS

        gr.DFSUtil(0, visited);

  

        // Если все вершины не посещены во второй DFS, то

        // вернуть ложь

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

            if (visited[i] == false)

                return false;

  

        return true;

    }

  

    / * Эта функция возвращает true, если ориентированный граф имеет эйлерово

       цикл, в противном случае возвращает false * /

    Boolean isEulerianCycle()

    {

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

        if (isSC() == false)

            return false;

  

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

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

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

                return false;

  

        return true;

    }

  

    public static void main (String[] args) throws java.lang.Exception

    {

        Graph g = new Graph(5);

        g.addEdge(1, 0);

        g.addEdge(0, 2);

        g.addEdge(2, 1);

        g.addEdge(0, 3);

        g.addEdge(3, 4);

        g.addEdge(4, 0);

  

        if (g.isEulerianCycle())

            System.out.println("Given directed graph is eulerian ");

        else

            System.out.println("Given directed graph is NOT eulerian ");

    }

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

питон

# Программа Python, чтобы проверить, является ли данный
# ориентированный граф является эйлеровым или нет

  

from collections import defaultdict

  

class Graph():

  

    def __init__(self, vertices):

        self.V = vertices

        self.graph = defaultdict(list)

        self.IN = [0] * vertices

  

    def addEdge(self, v, u):

  

        self.graph[v].append(u)

        self.IN[u] += 1

  

    def DFSUtil(self, v, visited):

        visited[v] = True

        for node in self.graph[v]:

            if visited[node] == False:

                self.DFSUtil(node, visited)

  

    def getTranspose(self):

        gr = Graph(self.V)

  

        for node in range(self.V):

            for child in self.graph[node]:

                gr.addEdge(child, node)

  

        return gr

  

    def isSC(self):

        visited = [False] * self.V

  

        v = 0

        for v in range(self.V):

            if len(self.graph[v]) > 0:

                break

  

        self.DFSUtil(v, visited)

  

        # Если обход DFS не посещает все

        # вершины, затем верните false.

        for i in range(self.V):

            if visited[i] == False:

                return False

  

        gr = self.getTranspose()

  

        visited = [False] * self.V

        gr.DFSUtil(v, visited)

  

        for i in range(self.V):

            if visited[i] == False:

                return False

  

        return True

  

    def isEulerianCycle(self):

  

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

        # подключены

        if self.isSC() == False:

            return False

  

        # Проверьте, если в степени и степени

        # каждая вершина одинакова

        for v in range(self.V):

            if len(self.graph[v]) != self.IN[v]:

                return False

  

        return True

  

  

g = Graph(5);

g.addEdge(1, 0);

g.addEdge(0, 2);

g.addEdge(2, 1);

g.addEdge(0, 3);

g.addEdge(3, 4);

g.addEdge(4, 0);

if g.isEulerianCycle():

   print "Given directed graph is eulerian";

else:

   print "Given directed graph is NOT eulerian";

  
# Этот код предоставлен Divyanshu Mehta


Выход:

Given directed graph is eulerian 

Временная сложность вышеописанной реализации составляет O (V + E), поскольку алгоритм Косараю занимает O (V + E) время. После запуска алгоритма Косараю мы пересекаем все вершины и сравниваем по степени с нашей степенью, что занимает время O (V).

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

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

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

Схема Эйлера в ориентированном графе

0.00 (0%) 0 votes