Рубрики

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

Двудольный граф — это граф, вершины которого можно разделить на два независимых множества U и V, так что каждое ребро (u, v) либо соединяет вершину из U в V, либо вершину из V в U. Другими словами, для каждого ребра (u, v) либо u принадлежит U, а v — V, либо u принадлежит V, а v — U. Можно также сказать, что не существует ребра, соединяющего вершины одного и того же набора.

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

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

Алгоритм проверки, является ли граф двудольным:
Один из подходов состоит в том, чтобы проверить, является ли граф 2-раскрашиваемым или нет, используя алгоритм обратного отслеживания m задачи раскраски .
Ниже приведен простой алгоритм, позволяющий определить, является ли данный граф Birpartite или нет, используя поиск в ширину (BFS).
1. Присвойте КРАСНЫЙ цвет исходной вершине (поместив в набор U).
2. Раскрасьте всех соседей синим цветом (добавив в набор V).
3. Раскрасьте соседа всех соседей КРАСНЫМ цветом (добавив в набор U).
4. Таким образом, присвойте цвет всем вершинам так, чтобы он удовлетворял всем ограничениям задачи раскраски m-путей, где m = 2.
5. При назначении цветов, если мы найдем соседа, который окрашен в тот же цвет, что и текущая вершина, то график не может быть раскрашен двумя вершинами (или график не является двудольным)

C ++

// C ++ программа, чтобы узнать, является ли
// данный график является двудольным или нет
#include <iostream>
#include <queue>
#define V 4

  

using namespace std;

  
// Эта функция возвращает true, если graph
// G [V] [V] является двудольным, иначе ложно

bool isBipartite(int G[][V], int src)

{

    // Создаем массив цветов для хранения цветов

    // присваивается всем вершинам. темя

    // число используется в качестве индекса в этом массиве.

    // Значение '-1' colorArr [i]

    // используется для обозначения отсутствия цвета

    // присваивается вершине 'i'. Значение 1

    // используется для обозначения первого цвета

    // назначено и значение 0 указывает

    // второй цвет назначен.

    int colorArr[V];

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

        colorArr[i] = -1;

  

    // Назначаем первый цвет источнику

    colorArr[src] = 1;

  

    // Создать очередь (FIFO) вершины

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

    // для обхода BFS

    queue <int> q;

    q.push(src);

  

    // Выполнить, пока есть вершины

    // в очереди (аналогично BFS)

    while (!q.empty())

    {

        // Удаление вершины из очереди (см. Http://goo.gl/35oz8 )

        int u = q.front();

        q.pop();

  

        // Возвращаем false, если есть цикл

        if (G[u][u] == 1)

        return false

  

        // Найти все неокрашенные смежные вершины

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

        {

            // существует ребро от u до v и

            // пункт назначения v не окрашен

            if (G[u][v] && colorArr[v] == -1)

            {

                // Назначаем альтернативный цвет этому смежному v из вас

                colorArr[v] = 1 - colorArr[u];

                q.push(v);

            }

  

            // существует ребро от u до v и пункт назначения

            // v окрашивается тем же цветом, что и вы

            else if (G[u][v] && colorArr[v] == colorArr[u])

                return false;

        }

    }

  

    // Если мы доберемся сюда, то все смежные

    // вершины можно закрасить альтернативным цветом

    return true;

}

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

int main()

{

    int G[][V] = {{0, 1, 0, 1},

        {1, 0, 1, 0},

        {0, 1, 0, 1},

        {1, 0, 1, 0}

    };

  

    isBipartite(G, 0) ? cout << "Yes" : cout << "No";

    return 0;

}

Джава

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

import java.util.*;

import java.lang.*;

import java.io.*;

  

class Bipartite

{

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

  

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

    // график G [V] [V] является двудольным, иначе ложь

    boolean isBipartite(int G[][],int src)

    {

        // Создаем массив цветов для хранения

        // цвета назначены всем вершинам.

        // Номер вершины используется в качестве индекса

        // в этом массиве. Значение «-1»

        // of colorArr [i] используется для указания

        // что цвет не назначен

        // для вершины 'i'. Значение 1

        // используется для обозначения первого цвета

        // назначено и значение 0 указывает

        // второй цвет назначен.

        int colorArr[] = new int[V];

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

            colorArr[i] = -1;

  

        // Назначаем первый цвет источнику

        colorArr[src] = 1;

  

        // Создать очередь (FIFO) номеров вершин

        // и ставим исходную вершину в очередь для обхода BFS

        LinkedList<Integer>q = new LinkedList<Integer>();

        q.add(src);

  

        // Выполнить при наличии вершин в очереди (аналогично BFS)

        while (q.size() != 0)

        {

            // Удаление вершины из очереди

            int u = q.poll();

  

            // Возвращаем false, если есть цикл

            if (G[u][u] == 1)

                return false

  

            // Найти все неокрашенные смежные вершины

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

            {

                // существует ребро от u до v

                // и пункт назначения v не окрашен

                if (G[u][v]==1 && colorArr[v]==-1)

                {

                    // Назначаем альтернативный цвет этому смежному v из вас

                    colorArr[v] = 1-colorArr[u];

                    q.add(v);

                }

  

                // существует ребро от u до v и пункт назначения

                // v окрашивается тем же цветом, что и вы

                else if (G[u][v]==1 && colorArr[v]==colorArr[u])

                    return false;

            }

        }

        // Если мы достигнем здесь, то все смежные вершины могут

        // быть окрашенным альтернативным цветом

        return true;

    }

  

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

    public static void main (String[] args)

    {

        int G[][] = {{0, 1, 0, 1},

            {1, 0, 1, 0},

            {0, 1, 0, 1},

            {1, 0, 1, 0}

        };

        Bipartite b = new Bipartite();

        if (b.isBipartite(G, 0))

        System.out.println("Yes");

        else

        System.out.println("No");

    }

}

  
// Аакаш Хасия

питон

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

  

class Graph():

  

    def __init__(self, V):

        self.V = V

        self.graph = [[0 for column in range(V)] \

                                for row in range(V)]

  

    # Эта функция возвращает true, если граф G [V] [V]

    # является двудольным, иначе ложным

    def isBipartite(self, src):

  

        # Создайте массив цветов для хранения цветов

        # присваивается всем вершинам. темя

        Номер # используется в качестве индекса в этом массиве.

        # Значение '-1' colorArr [i] используется для

        # означает, что цвет не назначен

        # вершина 'i'. Значение 1 используется для указания

        # назначен первый цвет и значение 0

        # указывает, что назначен второй цвет.

        colorArr = [-1] * self.V

  

        # Назначить первый цвет источнику

        colorArr[src] = 1

  

        # Создать очередь (FIFO) номеров вершин и

        # поставить в очередь исходную вершину для обхода BFS

        queue = []

        queue.append(src)

  

        # Запускать, пока в очереди есть вершины

        # (Аналогично BFS)

        while queue:

  

            u = queue.pop()

  

            # Вернуть false, если есть цикл

            if self.graph[u][u] == 1:

                return False;

  

            for v in range(self.V):

  

                # Существует ребро от u до v и пункт назначения

                # v не окрашен

                if self.graph[u][v] == 1 and colorArr[v] == -1:

  

                    # Назначьте альтернативный цвет этому

                    # рядом с тобой

                    colorArr[v] = 1 - colorArr[u]

                    queue.append(v)

  

                # Существует ребро от u до v и пункт назначения

                # v окрашен тем же цветом, что и вы

                elif self.graph[u][v] == 1 and colorArr[v] == colorArr[u]:

                    return False

  

        # Если мы доберемся сюда, то все смежные

        # вершины могут быть закрашены альтернативными

        # цвет

        return True

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

g = Graph(4)

g.graph = [[0, 1, 0, 1],

            [1, 0, 1, 0],

            [0, 1, 0, 1],

            [1, 0, 1, 0]

            ]

              

print "Yes" if g.isBipartite(0) else "No"

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

C #

// C # программа, чтобы узнать,
// данный граф является двудольным или нет

using System;

using System.Collections.Generic;

  

class GFG

{

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

  

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

    // граф G [V, V] является двудольным, иначе ложь

    bool isBipartite(int [,]G, int src)

    {

        // Создаем массив цветов для хранения

        // цвета назначены всем вершинам.

        // Номер вершины используется в качестве индекса

        // в этом массиве. Значение «-1»

        // of colorArr [i] используется для указания

        // что цвет не назначен

        // для вершины 'i'. Значение 1

        // используется для обозначения первого цвета

        // назначено и значение 0 указывает

        // второй цвет назначен.

        int []colorArr = new int[V];

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

            colorArr[i] = -1;

  

        // Назначаем первый цвет источнику

        colorArr[src] = 1;

  

        // Создать очередь (FIFO) номеров вершин

        // и ставим исходную вершину в очередь для обхода BFS

        List<int>q = new List<int>();

        q.Add(src);

  

        // Выполнить, пока есть вершины

        // в очереди (аналогично BFS)

        while (q.Count != 0)

        {

            // Удаление вершины из очереди

            int u = q[0];

            q.RemoveAt(0);

  

            // Возвращаем false, если есть цикл

            if (G[u, u] == 1)

                return false

  

            // Найти все неокрашенные смежные вершины

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

            {

                // существует ребро от u до v

                // и пункт назначения v не окрашен

                if (G[u, v] == 1 && colorArr[v] == -1)

                {

                    // Назначаем альтернативный цвет

                    // к этому соседнему v из вас

                    colorArr[v] = 1 - colorArr[u];

                    q.Add(v);

                }

  

                // существует ребро от u до v и

                // место назначения v окрашено

                // того же цвета, что и вы

                else if (G[u, v] == 1 && 

                         colorArr[v] == colorArr[u])

                    return false;

            }

        }

          

        // Если мы достигаем здесь, то все смежные вершины

        // может быть окрашен альтернативным цветом

        return true;

    }

  

    // Код драйвера

    public static void Main(String[] args)

    {

        int [,]G = {{0, 1, 0, 1},

                    {1, 0, 1, 0},

                    {0, 1, 0, 1},

                    {1, 0, 1, 0}};

        GFG b = new GFG();

        if (b.isBipartite(G, 0))

            Console.WriteLine("Yes");

        else

            Console.WriteLine("No");

    }

}

  
// Этот код предоставлен Rajput-Ji


Выход:

Yes

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

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

C ++

// C ++ программа, чтобы узнать,
// данный граф является двудольным или нет.
// Работает и для отключенного графа.
#include <bits/stdc++.h>

  

using namespace std;

  

const int V = 4;

  
// Эта функция возвращает true, если
// график G [V] [V] является двудольным, иначе ложь

bool isBipartiteUtil(int G[][V], int src, int colorArr[])

{

    colorArr[src] = 1;

  

    // Создаем очередь (FIFO) номеров вершин

    // найти исходную вершину для обхода BFS

    queue <int> q;

    q.push(src);

  

    // Выполнить при наличии вершин в очереди (аналогично BFS)

    while (!q.empty())

    {

        // Удаление вершины из очереди (см. Http://goo.gl/35oz8 )

        int u = q.front();

        q.pop();

  

        // Возвращаем false, если есть цикл

        if (G[u][u] == 1)

        return false

  

        // Найти все неокрашенные смежные вершины

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

        {

            // существует ребро от u до v и

            // пункт назначения v не окрашен

            if (G[u][v] && colorArr[v] == -1)

            {

                // Назначаем альтернативный цвет этому

                // рядом с тобой

                colorArr[v] = 1 - colorArr[u];

                q.push(v);

            }

  

            // существует ребро от u до v и пункт назначения

            // v окрашивается тем же цветом, что и вы

            else if (G[u][v] && colorArr[v] == colorArr[u])

                return false;

        }

    }

  

    // Если мы достигнем здесь, то все смежные вершины могут

    // быть окрашенным альтернативным цветом

    return true;

}

  
// Возвращает true, если G [] [] является двудольным, иначе false

bool isBipartite(int G[][V])

{

    // Создание цветового массива для хранения цветов, назначенных всем

    // Вершины. Вершина / число используется в качестве индекса в этом

    // массив. Значение '-1' colorArr [i] используется для

    // указываем, что для вершины 'i' не назначен цвет.

    // Значение 1 используется для обозначения первого цвета

    // присваивается и значение 0 указывает, что второй цвет

    // назначен

    int colorArr[V];

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

        colorArr[i] = -1;

  

    // Этот код предназначен для обработки отключенного graoh

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

    if (colorArr[i] == -1)

        if (isBipartiteUtil(G, i, colorArr) == false)

        return false;

  

    return true;

}

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

int main()

{

    int G[][V] = {{0, 1, 0, 1},

        {1, 0, 1, 0},

        {0, 1, 0, 1},

        {1, 0, 1, 0}

    };

  

    isBipartite(G) ? cout << "Yes" : cout << "No";

    return 0;

}

Джава

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

import java.util.*;

  

class Bipartite {

      

    public static int V = 4;

       

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

    // G [V] [V] является двудольным, иначе ложно

    public static boolean isBipartiteUtil(int G[][], int src, 

                                           int colorArr[])

    {

        colorArr[src] = 1;

       

        // Создать очередь (FIFO) номеров вершин и

        // ставим в очередь исходную вершину для обхода BFS

        LinkedList<Integer> q = new LinkedList<Integer>();

        q.add(src);

       

        // Выполнить, пока в очереди есть вершины

        // (аналогично BFS)

        while (!q.isEmpty())

        {

            // Удаление вершины из очереди

            // (см. Http://goo.gl/35oz8 )

            int u = q.getFirst();

            q.pop();

       

            // Возвращаем false, если есть цикл

            if (G[u][u] == 1)

               return false;  

       

             // Найти все неокрашенные смежные вершины

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

            {

                // существует ребро от u до v и

                // пункт назначения v не окрашен

                if (G[u][v] ==1 && colorArr[v] == -1)

                {

                    // Назначаем альтернативный цвет этому

                    // рядом с тобой

                    colorArr[v] = 1 - colorArr[u];

                    q.push(v);

                }

       

                // существует ребро от u до v и

                // пункт назначения v окрашен тем же

                // цвет как ты

                else if (G[u][v] ==1 && colorArr[v] == 

                                         colorArr[u])

                    return false;

            }

        }

       

        // Если мы достигаем здесь, то все смежные вершины

        // может быть окрашен альтернативным цветом

        return true;

    }

       

    // Возвращает true, если G [] [] является двудольным, иначе false

    public static boolean isBipartite(int G[][])

    {

        // Создание цветового массива для хранения назначенных цветов

        // ко всем вершинам. Вершина / число используется как

        // индекс в этом массиве. Значение '-1'

        // colorArr [i] используется для обозначения отсутствия цвета

        // присваивается вершине 'i'. Значение 1 используется

        // для обозначения первого цвета и значения

        // 0 указывает, что назначен второй цвет.

        int colorArr[] = new int[V];

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

            colorArr[i] = -1;

       

        // Этот код предназначен для обработки отключенного graoh

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

          if (colorArr[i] == -1)

            if (isBipartiteUtil(G, i, colorArr) == false)

               return false;

       

         return true;

    }

      

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

    public static void main(String[] args) 

    {

         int G[][] = {{0, 1, 0, 1},

                      {1, 0, 1, 0},

                      {0, 1, 0, 1},

                      {1, 0, 1, 0}};

                        

                if (isBipartite(G))

                   System.out.println("Yes");

                else

                   System.out.println("No");

        }

    }

      
// Этот код предоставлен Арнавом Кр. Мандал.

питон

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

  

class Graph(): 

  

    def __init__(self, V): 

        self.V =

        self.graph = [[0 for column in range(V)] 

                         for row in range(V)] 

  

        self.colorArr = [-1 for i in range(self.V)]

          

    # Эта функция возвращает true, если граф G [V] [V]

    # является двудольным, иначе ложным

    def isBipartiteUtil(self, src): 

  

        # Создайте массив цветов для хранения цветов

        # присваивается всем вершинам. темя

        Номер # используется в качестве индекса в этом массиве.

        # Используется значение «-1» для self.colorArr [i]

        #, чтобы указать, что цвет не назначен

        # вершина 'i'. Значение 1 используется для указания

        # назначен первый цвет и значение 0

        # указывает, что назначен второй цвет.

  

        # Назначить первый цвет источнику

  

        # Создать очередь (FIFO) номеров вершин и

        # поставить в очередь исходную вершину для обхода BFS

        queue = [] 

        queue.append(src) 

  

        # Запускать, пока в очереди есть вершины

        # (Аналогично BFS)

        while queue: 

  

            u = queue.pop() 

  

            # Вернуть false, если есть цикл

            if self.graph[u][u] == 1

                return False

  

            for v in range(self.V): 

  

                # Существует ребро от u до v и

                # пункт назначения v не окрашен

                if (self.graph[u][v] == 1 and 

                    self.colorArr[v] == -1): 

  

                    # Назначить альтернативный цвет

                    # это смежный с тобой

                    self.colorArr[v] = 1 - self.colorArr[u] 

                    queue.append(v) 

  

                # Существует ребро от u до v и пункт назначения

                # v окрашен тем же цветом, что и вы

                elif (self.graph[u][v] == 1 and 

                      self.colorArr[v] == self.colorArr[u]): 

                    return False

  

        # Если мы доберемся сюда, то все смежные

        # вершины могут быть закрашены альтернативными

        # цвет

        return True

          

    def isBipartite(self):

        self.colorArr = [-1 for i in range(self.V)]

        for i in range(self.V):

            if self.colorArr[i] == -1:

                if not self.isBipartiteUtil(i):

                    return False

        return True

                      
Код водителя

g = Graph(4

g.graph = [[0, 1, 0, 1], 

           [1, 0, 1, 0], 

           [0, 1, 0, 1], 

           [1, 0, 1, 0]] 

              

print "Yes" if g.isBipartite() else "No"

  
# Этот код предоставлен Anshuman Sharma


Выход:

Yes

Сложность по времени вышеупомянутого подхода такая же, как у поиска в ширину. В вышеприведенной реализации O (V ^ 2), где V — число вершин. Если граф представлен с использованием списка смежности, то сложность становится O (V + E).

Упражнение:
1. Можно ли использовать алгоритм DFS для проверки двудольности графа? Если да, то как?
Решение :

C ++

// C ++ программа, чтобы узнать, является ли данный граф двудольным или нет.
// Использование рекурсии.
#include <iostream>

  

using namespace std;

#define V 4

  

  

bool colorGraph(int G[][V],int color[],int pos, int c){

      

    if(color[pos] != -1 && color[pos] !=c)

        return false;

          

    // раскрасить это положение как c и все его соседи и 1-c

    color[pos] = c;

    bool ans = true;

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

        if(G[pos][i]){

            if(color[i] == -1)

                ans &= colorGraph(G,color,i,1-c);

                  

            if(color[i] !=-1 && color[i] != 1-c)

                return false;

        }

        if (!ans)

            return false;

    }

      

    return true;

}

  

bool isBipartite(int G[][V]){

    int color[V];

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

        color[i] = -1;

          

    // начало - вершина 0;

    int pos = 0;

    // два цвета 1 и 0

    return colorGraph(G,color,pos,1);

      
}

  

int main()

{

    int G[][V] = {{0, 1, 0, 1},

        {1, 0, 1, 0},

        {0, 1, 0, 1},

        {1, 0, 1, 0}

    };

  

    isBipartite(G) ? cout<< "Yes" : cout << "No";

    return 0;


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

python3

# Программа Python3, чтобы узнать, является ли данный
# graph является двудольным или не использует рекурсию.

V = 4 

  

def colorGraph(G, color, pos, c): 

      

    if color[pos] != -1 and color[pos] != c: 

        return False 

          

    # раскрасить этот поз как c и всех его соседей и 1-c

    color[pos] =

    ans = True 

    for i in range(0, V): 

        if G[pos][i]: 

            if color[i] == -1

                ans &= colorGraph(G, color, i, 1-c) 

                  

            if color[i] !=-1 and color[i] != 1-c: 

                return False 

           

        if not ans: 

            return False 

       

    return True 

   

def isBipartite(G): 

      

    color = [-1] *

          

    #start - вершина 0

    pos = 0 

    # два цвета 1 и 0

    return colorGraph(G, color, pos, 1

  

if __name__ == "__main__"

   

    G = [[0, 1, 0, 1], 

         [1, 0, 1, 0], 

         [0, 1, 0, 1], 

         [1, 0, 1, 0]] 

       

    if isBipartite(G): print("Yes"

    else: print("No"

  
# Этот код предоставлен Rituraj Jain

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

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

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

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

0.00 (0%) 0 votes