Рубрики

Двусвязный граф

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

Ниже приведены некоторые примеры.





Смотрите это для большего количества примеров.

Как узнать, является ли данный граф двусвязным или нет?

Связный граф является двусвязным, если он связен и не имеет точки сочленения . В основном нам нужно проверить две вещи на графике.
1) График связан.
2) На графе нет точки сочленения.

Мы начинаем с любой вершины и делаем обход DFS. При обходе DFS мы проверяем, есть ли точка сочленения. Если мы не найдем точку сочленения, то граф двусвязный. Наконец, нам нужно проверить, все ли вершины были доступны в DFS или нет. Если все вершины не были достижимы, то граф даже не связен.
Ниже приведена реализация C ++ вышеупомянутого подхода.

C ++

// Программа на C ++, чтобы найти, является ли данный неориентированный граф
// двунаправленный
#include<iostream>
#include <list>
#define NIL -1

using namespace std;

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

class Graph

{

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

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

    bool isBCUtil(int v, bool visited[], int disc[], int low[],

                 int parent[]);

public:

    Graph(int V);   // Конструктор

    void addEdge(int v, int w); // добавить ребро на график

    bool isBC();    // возвращает true, если граф двусвязный

};

  

Graph::Graph(int V)

{

    this->V = V;

    adj = new list<int>[V];

}

  

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

{

    adj[v].push_back(w);

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

}

  
// Рекурсивная функция, которая возвращает true, если есть артикуляция
// указывает на данный граф, в противном случае возвращает false.
// Эта функция почти такая же, как isAPUtil () здесь ( http://goo.gl/Me9Fw )
// u -> вершина, которую нужно посетить затем
// посещения [] -> сохраняет путь посещенных вершин
// disc [] -> Хранит время обнаружения посещенных вершин
// parent [] -> Сохраняет родительские вершины в дереве DFS

bool Graph::isBCUtil(int u, bool visited[], int disc[],int low[],int parent[])

{

    // Для простоты используется статическая переменная, мы можем избежать использования статической

    // переменная путем передачи указателя.

    static int time = 0;

  

    // Количество детей в DFS Tree

    int children = 0;

  

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

    visited[u] = true;

  

    // Инициализация времени обнаружения и низкого значения

    disc[u] = low[u] = ++time;

  

    // Проходим все вершины, прилегающие к этому

    list<int>::iterator i;

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

    {

        int v = *i;  // v текущий соседний с вами

  

        // Если v еще не посещено, то сделайте его дочерним для вас

        // в дереве DFS и повторяем за ним

        if (!visited[v])

        {

            children++;

            parent[v] = u;

  

            // проверяем, имеет ли подграф с корнем v точку сочленения

            if (isBCUtil(v, visited, disc, low, parent))

               return true;

  

            // Проверяем, имеет ли поддерево с корнем v соединение с

            // один из предков тебя

            low[u]  = min(low[u], low[v]);

  

            // u - точка сочленения в следующих случаях

  

            // (1) u является корнем дерева DFS и имеет двух или более детей.

            if (parent[u] == NIL && children > 1)

               return true;

  

            // (2) Если u не является корнем и низкое значение одного из его потомков

            // больше, чем ценность открытия u.

            if (parent[u] != NIL && low[v] >= disc[u])

               return true;

        }

  

        // Обновление низкого значения u для вызовов родительской функции.

        else if (v != parent[u])

            low[u]  = min(low[u], disc[v]);

    }

    return false;

}

  
// Основная функция, которая возвращает значение true, если граф Biconnected,
// иначе ложно. Он использует рекурсивную функцию isBCUtil ()

bool Graph::isBC()

{

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

    bool *visited = new bool[V];

    int *disc = new int[V];

    int *low = new int[V];

    int *parent = new int[V];

  

    // Инициализируем родительский и посещенный, и ap (точка артикуляции)

    // массивы

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

    {

        parent[i] = NIL;

        visited[i] = false;

    }

  

    // Вызываем рекурсивную вспомогательную функцию, чтобы найти, есть ли артикуляция

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

    if (isBCUtil(0, visited, disc, low, parent) == true)

        return false;

  

    // Теперь проверяем, связан ли данный граф или нет. Ненаправленный

    // граф связен, если все вершины достижимы с любого начала

    // точка (мы взяли 0 в качестве начальной точки)

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

        if (visited[i] == false)

            return false;

  

    return true;

}

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

int main()

{

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

    Graph g1(2);

    g1.addEdge(0, 1);

    g1.isBC()? cout << "Yes\n" : cout << "No\n";

  

    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(2, 4);

    g2.isBC()? cout << "Yes\n" : cout << "No\n";

  

    Graph g3(3);

    g3.addEdge(0, 1);

    g3.addEdge(1, 2);

    g3.isBC()? cout << "Yes\n" : cout << "No\n";

  

    Graph g4(5);

    g4.addEdge(1, 0);

    g4.addEdge(0, 2);

    g4.addEdge(2, 1);

    g4.addEdge(0, 3);

    g4.addEdge(3, 4);

    g4.isBC()? cout << "Yes\n" : cout << "No\n";

  

    Graph g5(3);

    g5.addEdge(0, 1);

    g5.addEdge(1, 2);

    g5.addEdge(2, 0);

    g5.isBC()? cout << "Yes\n" : cout << "No\n";

  

    return 0;

}

Джава

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

import java.io.*;

import java.util.*;

import java.util.LinkedList;

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

class Graph

{

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

  

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

    private LinkedList<Integer> adj[];

  

    int time = 0;

    static final int NIL = -1;

  

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

    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);  // Обратите внимание, что график не является ненаправленным.

        adj[w].add(v);

    }

  

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

    // указывает на данный граф, в противном случае возвращает false.

    // Эта функция почти такая же, как isAPUtil () @ http://goo.gl/Me9Fw

    // u -> вершина, которую нужно посетить затем

    // посещения [] -> сохраняет путь посещенных вершин

    // disc [] -> Хранит время обнаружения посещенных вершин

    // parent [] -> Сохраняет родительские вершины в дереве DFS

    boolean isBCUtil(int u, boolean visited[], int disc[],int low[],

                     int parent[])

    {

  

        // Количество детей в DFS Tree

        int children = 0;

  

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

        visited[u] = true;

  

        // Инициализация времени обнаружения и низкого значения

        disc[u] = low[u] = ++time;

  

        // Проходим все вершины, прилегающие к этому

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

        while (i.hasNext())

        {

            int v = i.next();  // v текущий соседний с вами

  

            // Если v еще не посещено, то сделайте его дочерним для вас

            // в дереве DFS и повторяем за ним

            if (!visited[v])

            {

                children++;

                parent[v] = u;

  

                // проверяем, имеет ли подграф с корнем v точку сочленения

                if (isBCUtil(v, visited, disc, low, parent))

                    return true;

  

                // Проверяем, имеет ли поддерево с корнем v соединение с

                // один из предков тебя

                low[u]  = Math.min(low[u], low[v]);

  

                // u - точка сочленения в следующих случаях

  

                // (1) u является корнем дерева DFS и имеет двух или более детей.

                if (parent[u] == NIL && children > 1)

                    return true;

  

                // (2) Если u не root и низкое значение одного из его

                // child больше чем значение открытия u.

                if (parent[u] != NIL && low[v] >= disc[u])

                    return true;

            }

  

            // Обновление низкого значения u для вызовов родительской функции.

            else if (v != parent[u])

                low[u]  = Math.min(low[u], disc[v]);

        }

        return false;

    }

  

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

    // иначе ложно. Он использует рекурсивную функцию isBCUtil ()

    boolean isBC()

    {

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

        boolean visited[] = new boolean[V];

        int disc[] = new int[V];

        int low[] = new int[V];

        int parent[] = new int[V];

  

        // Инициализируем родительский и посещенный, и ap (точка артикуляции)

        // массивы

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

        {

            parent[i] = NIL;

            visited[i] = false;

        }

  

        // Вызываем рекурсивную вспомогательную функцию, чтобы найти, есть ли

        // артикуляция / точка в данном графе. Мы делаем обход DFS

        // в главной роли от вершины 0

        if (isBCUtil(0, visited, disc, low, parent) == true)

            return false;

  

        // Теперь проверяем, связан ли данный граф или нет.

        // Ненаправленный граф связен, если все вершины

        // достижимы из любой начальной точки (мы взяли 0 как

        // отправная точка)

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

            if (visited[i] == false)

                return false;

  

        return true;

    }

  

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

    public static void main(String args[])

    {

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

        Graph g1 =new Graph(2);

        g1.addEdge(0, 1);

        if (g1.isBC())

            System.out.println("Yes");

        else

            System.out.println("No");

  

        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(2, 4);

        if (g2.isBC())

            System.out.println("Yes");

        else

            System.out.println("No");

  

        Graph g3 = new Graph(3);

        g3.addEdge(0, 1);

        g3.addEdge(1, 2);

        if (g3.isBC())

            System.out.println("Yes");

        else

            System.out.println("No");

  

        Graph g4 = new Graph(5);

        g4.addEdge(1, 0);

        g4.addEdge(0, 2);

        g4.addEdge(2, 1);

        g4.addEdge(0, 3);

        g4.addEdge(3, 4);

        if (g4.isBC())

            System.out.println("Yes");

        else

            System.out.println("No");

  

        Graph g5= new Graph(3);

        g5.addEdge(0, 1);

        g5.addEdge(1, 2);

        g5.addEdge(2, 0);

        if (g5.isBC())

            System.out.println("Yes");

        else

            System.out.println("No");

    }

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

питон

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

   

from collections import defaultdict

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

class Graph:

   

    def __init__(self,vertices):

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

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

        self.Time = 0

   

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

    def addEdge(self,u,v):

        self.graph[u].append(v)

        self.graph[v].append(u)

   

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

    точка в данном графе, в противном случае возвращает false.

    Эта функция почти такая же, как isAPUtil ()

    u -> вершина, которую нужно посетить затем

    посещенные [] -> хранит тракт посещенных вершин

    disc [] -> Хранит время обнаружения посещенных вершин

    parent [] -> Сохраняет родительские вершины в дереве DFS '' '

    def isBCUtil(self,u, visited, parent, low, disc):

  

        # Количество детей в текущем узле

        children =0

  

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

        visited[u]= True

  

        # Инициализировать время обнаружения и низкое значение

        disc[u] = self.Time

        low[u] = self.Time

        self.Time += 1

  

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

        for v in self.graph[u]:

            # Если v еще не посещено, сделайте его потомком

            # в дереве DFS и повторить его

            if visited[v] == False :

                parent[v] = u

                children += 1

                if self.isBCUtil(v, visited, parent, low, disc):

                    return True

  

                # Проверьте, подключено ли поддерево с корнем v

                # один из предков тебя

                low[u] = min(low[u], low[v])

  

                # u - точка сочленения в следующих случаях

                # (1) u является корнем дерева DFS и имеет двух или более детей.

                if parent[u] == -1 and children > 1:

                    return True

  

                # (2) Если u не является корнем и низкое значение одного из его дочерних элементов больше

                # чем значение открытия вас.

                if parent[u] != -1 and low[v] >= disc[u]:

                    return True    

                      

            elif v != parent[u]: # Обновление низкого значения u для вызовов родительской функции.

                low[u] = min(low[u], disc[v])

  

        return False

  

  

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

    # иначе ложь. Он использует рекурсивную функцию isBCUtil ()

    def isBC(self):

   

        # Отметить все вершины как не посещенные и инициализировать родительский и посещенный,

        Массивы # и ap (точка сочленения)

        visited = [False] * (self.V)

        disc = [float("Inf")] * (self.V)

        low = [float("Inf")] * (self.V)

        parent = [-1] * (self.V)

      

  

        # Вызовите рекурсивную вспомогательную функцию, чтобы найти, есть ли

        # точки сочленения в данном графике. Мы делаем запуск DFS обхода

        # из вершины 0

        if self.isBCUtil(0, visited, parent, low, disc):

            return False

  

        '' 'Теперь проверьте, связан ли данный граф или нет.

        Ненаправленный граф связен, если все вершины

        достижимы из любой начальной точки (мы взяли 0 в качестве

        отправная точка)'''

        if any(i == False for i in visited):

            return False

          

        return True

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

g1 =  Graph(2)

g1.addEdge(0, 1)

print "Yes" if g1.isBC() else "No"

  

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(2, 4)

print "Yes" if g2.isBC() else "No"

  

g3 = Graph(3)

g3.addEdge(0, 1)

g3.addEdge(1, 2)

print "Yes" if g3.isBC() else "No"

  

   

g4 = Graph (5)

g4.addEdge(1, 0)

g4.addEdge(0, 2)

g4.addEdge(2, 1)

g4.addEdge(0, 3)

g4.addEdge(3, 4)

print "Yes" if g4.isBC() else "No"

  

g5 = Graph(3)

g5.addEdge(0, 1)

g5.addEdge(1, 2)

g5.addEdge(2, 0)

print "Yes" if g5.isBC() else "No"

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


Выход:

Yes
Yes
No
No
Yes

Сложность времени: вышеуказанная функция представляет собой простой DFS с дополнительными массивами. Таким образом, временная сложность такая же, как и у DFS, которая является O (V + E) для представления графа в списке смежности.

Ссылки:
http://www.cs.purdue.edu/homes/ayg/CS251/slides/chap9d.pdf

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

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

Двусвязный граф

0.00 (0%) 0 votes