Grafy dwudzielne


Tematy pokrewne
Grafy
Podstawowe pojęcia dotyczące grafów
Reprezentacja grafów w komputerze
Przechodzenie grafów w głąb – DFS
Przechodzenie grafów wszerz – BFS
Transpozycja grafu
Kwadrat grafu
Graf krawędziowy
Stopień grafu
Znajdowanie ścieżki w grafie
Znajdowanie drogi w labiryncie
Spójność grafu
Znajdowanie spójnych składowych w grafie
Znajdowanie silnie spójnych składowych w grafie
Drzewa rozpinające grafu
Znajdowanie mostów w grafie
Znajdowanie punktów artykulacji w grafie
Grafy dwudzielne
Kojarzenie małżeństw
Cykliczność grafu
Znajdowanie cykli w grafie
Istnienie cyklu lub ścieżki Eulera
Znajdowanie cyklu lub ścieżki Eulera
Znajdowanie cyklu lub ścieżki Hamiltona
Sortowanie topologiczne grafu skierowanego
Najkrótsza ścieżka w grafie ważonym – algorytm Dijkstry
Najkrótsza ścieżka w grafie ważonym – algorytm Bellmana-Forda
Najkrótsze ścieżki pomiędzy wszystkimi parami wierzchołków w grafie ważonym
Problem chińskiego listonosza
Problem komiwojażera
Minimalne drzewo rozpinające
Kolorowanie grafu
Znajdowanie klik w grafie

Problem

Zbadać, czy dany graf nieskierowany i spójny jest grafem dwudzielnym.



Graf dwudzielny (ang. bipartite graph lub bigraph) jest grafem, którego wierzchołki możemy podzielić na dwa rozłączne zbiory U i V. Wierzchołki należące do zbioru U mogą się łączyć krawędziami tylko z wierzchołkami ze zbioru V i na odwrót.

 

 

Innymi słowy, każda krawędź grafu dwudzielnego łączy wierzchołki z różnych zbiorów.

Wierzchołki należące do zbioru U możemy traktować jako pokolorowane np. na niebiesko, a wierzchołki należące do zbioru V jako pokolorowane np. na czerwono. Graf będzie grafem dwudzielnym, jeśli uda nam się pokolorować wszystkie jego wierzchołki tak, aby żaden z sąsiadów danego wierzchołka nie był tego samego koloru co sam wierzchołek.

Do kolorowania grafu możemy wykorzystać algorytm przejścia wszerz BFS lub algorytm przejścia w głąb DFS. Zasada jest następująca:

 

Początkowo wszystkie wierzchołki grafu powinny posiadać kolor neutralny. Wybieramy dowolny wierzchołek w grafie i kolorujemy go np. na czerwono. Następnie przechodzimy algorytmem DFS lub BFS przez graf począwszy od wybranego wierzchołka kolorując po drodze wszystkich nie odwiedzonych sąsiadów na kolor przeciwny (czerwony → niebieski,  niebieski → czerwony) do koloru odwiedzanego wierzchołka. Jeśli któryś z odwiedzonych wierzchołków sąsiadujących posiada taki sam kolor jak wierzchołek odwiedzany, to graf nie jest grafem dwudzielnym - dana krawędź łączy wierzchołki tej samej klasy.

 

Prześledźmy te operacje na przykładowym grafie:

 

Mamy przykładowy graf, dla którego chcemy sprawdzić dwudzielność (ang. bipartiteness). Początkowo wszystkie wierzchołki posiadają kolor neutralny – tutaj szary.
W grafie wybieramy dowolny wierzchołek (u nas niech to dla prostoty będzie wierzchołek 0) i kolorujemy go np. na czerwono.

Wybrany wierzchołek posłuży jako punkt startowy dla przejścia BFS (lub alternatywnie DFS).

Sprawdzamy, czy każdy sąsiad posiada inny kolor od wierzchołka startowego (jeśli nie, to graf nie jest dwudzielny i operację sprawdzania dwudzielności możemy natychmiast zakończyć z wynikiem negatywnym), a następnie kolorujemy go na kolor przeciwny do koloru wierzchołka startowego – tutaj na niebiesko.
Operację sprawdzania i kolorowania powtarzamy dla każdego sąsiada zgodnie z wybranym algorytmem przejścia grafu – tutaj BFS.
I dalej...
I dalej...
Koniec, graf jest dwudzielny.

 

Algorytm sprawdzania dwudzielności grafu za pomocą BFS

Wejście
n  –  liczba wierzchołków w grafie, n C
graf  –  zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje
Wyjście:
true – graf jest dwudzielny
false – graf nie jest dwudzielny
Elementy pomocnicze:
Q  –  kolejka
i,v,u  –  wierzchołki, i,v,u C
C  –  n elementowa tablica zawierająca kolory wierzchołków, w przypadku grafu dwudzielnego:
 0 - kolor szary
 1 - kolor czerwony
-1 - kolor niebieski
Lista kroków:
K01: Utwórz n elementową tablicę C  
K02: Ustaw wszystkie elementy tablicy C na 0 ; 0 oznacza kolor szary
K03: Utwórz pustą kolejkę Q  
K04: Dla i = 0,1,...,n - 1, wykonuj K05...K15 ; przechodzimy przez kolejne wierzchołki grafu
K05:     Jeśli C[i] ≠ 0, to następny obieg pętli K04 ; szukamy wierzchołka szarego, który będzie wierzchołkiem startowym
K06:     C[i] ← 1 ; wierzchołek startowy kolorujemy na czerwono
K07:     Q.push(i) ; numer wierzchołka umieszczamy w kolejce
K08:     Dopóki Q.empty() = false, wykonuj K09...K15 ; rozpoczynamy przejście BFS
K09:         vQ.front() ; pobieramy element z początku kolejki
K10:         Q.pop() ; pobrany element usuwamy z kolejki
K11:         Dla każdego sąsiada u wierzchołka v, wykonuj K12...K15 ; przetwarzamy sąsiadów wierzchołka v
K12:             Jeśli C[u] = C[v], to zakończ z wynikiem false ; sąsiad ma ten sam kolor, więc graf nie może być dwudzielny
K13:             Jeśli C[u] ≠ 0, to następny obieg pętli K11 ; szukamy wierzchołka niepokolorowanego, czyli jeszcze nieodwiedzonego
K14:             C[u] = -C[v] ; kolorujemy sąsiada na kolor przeciwny
K15:             Q.push(u) ; sąsiada umieszczamy w kolejce
K16: Zakończ z wynikiem true  

 

Algorytm z przejściem DFS jest identyczny z powyższym. Jedyna zmiana polega na zastąpieniu kolejki Q stosem S.

Algorytm po niewielkiej przeróbce pozwala również wyznaczyć oba zbiory U i V. Odpowiednia informacja zawarta jest w tablicy color.

Z postaci przedstawionego powyżej algorytmu wynika, że najlepszym sposobem reprezentowania grafu jest tablica list sąsiedztwa.

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program odczytuje definicję grafu nieskierowanego, tworzy tablicę list sąsiedztwa, a następnie sprawdza, czy graf jest dwudzielny. Jeśli tak, to wypisuje 'BIPARTITE GRAPH'. W przeciwnym razie wypisuje 'NOT A BIPARTITE GRAPH'. Za wierzchołek startowy przyjmowany jest wierzchołek nr 0.

 

Graf dwudzielny:
     17 23
0 2 0 3
1 2 1 14
2 6
3 4 3 6 3 13
4 7 4 12
5 6 5 9 5 10
6 7 6 8 6 12
7 13
8 9
10 11
10 14
10 15
11 16
12 16
 

Graf niedwudzielny:

  17 24
0 2 0 3
1 2 1 14
2 6
3 4 3 6 3 13
4 7 4 12
5 6 5 9 5 10
6 7 6 8 6 12
7 13
8 9
10 11
10 14
10 15
11 16
12 16
13 16

 

Lazarus
// Testowanie dwudzielności grafu
// Data: 24.11.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

program test_bigraph;

// Typy dla dynamicznej tablicy list sąsiedztwa i kolejki
type
  PslistEl = ^slistEl;
  slistEl =  record
    next  : PslistEl;
    v     : integer;
  end;

  TList = array of PslistEl;

// Definicja typu obiektowego queue
//---------------------------------
  queue = object
    private
      head : PslistEl;
      tail : PslistEl;

    public
      constructor init;
      destructor destroy;
      function empty : boolean;
      function front : integer;
      procedure push(v : integer);
      procedure pop;
  end;

//---------------------
// Metody obiektu queue
//---------------------

// Konstruktor - tworzy pustą listę
//---------------------------------
constructor queue.init;
begin
  head := nil;
  tail := nil;
end;

// Destruktor - usuwa listę z pamięci
//-----------------------------------
destructor queue.destroy;
begin
  while not empty do pop;
end;

// Sprawdza, czy kolejka jest pusta
//---------------------------------
function queue.empty : boolean;
begin
  if head = nil then empty := true
  else               empty := false;
end;

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
function queue.front : integer;
begin
  if head = nil then front := -MAXINT
  else               front := head^.v;
end;

// Zapisuje do kolejki
//--------------------
procedure queue.push(v : integer);
var
  p : PslistEl;
begin
  new(p);
  p^.next := nil;
  p^.v := v;
  if tail = nil then head := p
  else tail^.next := p;
  tail := p;
end;

// Usuwa z kolejki
//----------------
procedure queue.pop;
var
  p : PslistEl;
begin
  if head <> nil then
  begin
    p := head;
    head := head^.next;
    if head = nil then tail := nil;
    dispose(p);
  end;
end;

// Funkcja testuje dwudzielność grafu
// n - liczba wierzchołków grafu
// A - tablica list sąsiedztwa
//-----------------------------------
function isBipartite(n : integer; var A : TList) : boolean;
var
  Q     : queue;
  C     : array of integer;
  v,u,i : integer;
  p     : PslistEl;

begin
  SetLength(C,n);          // Tworzymy tablicę kolorów
  for i := 0 to n - 1 do C[i] := 0;

  Q.init;                  // Tworzymy pustą kolejkę

  for i := 0 to n - 1 do   // Przechodzimy przez kolejne wierzchołki
    if C[i] = 0 then       // Szukamy wierzchołka szarego
    begin
      C[i] := 1;           // Wierzchołek startowy kolorujemy na czerwono
      Q.push(i);           // i umieszczamy w kolejce

      while Q.empty = false do // Przejście BFS
      begin
        v := Q.front;      // Pobieramy wierzchołek z kolejki
        Q.pop;             // Pobrany wierzchołek usuwamy z kolejki
        p := A[v];         // Przeglądamy sąsiadów wierzchołka v
        while p <> nil do
        begin
          u := p^.v;       // pobieramy z listy sąsiedztwa numer sąsiada
          if C[u] = C[v] then
          begin
            SetLength(C,0);
            Q.destroy;
            Exit(false);   // Sąsiad ma ten sam kolor
          end;

          if C[u] = 0 then // Jeśli wierzchołek nie jest odwiedzony,
          begin
            C[u] := -C[v]; // kolorujemy go na kolor przeciwny
            Q.push(u);     // i umieszczamy w kolejce
          end;
          p := p^.next;    // Następny sąsiad
        end;
      end;
    end;

  SetLength(C,0);

  isBipartite := true;
end;

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

var
  n,m,i,v1,v2 : integer;
  p,r         : PslistEl;
  A           : TList;

begin
  read(n,m);             // Czytamy liczbę wierzchołków i krawędzi

  SetLength(A,n);        // Tworzymy tablicę list sąsiedztwa

  // Tablice wypełniamy pustymi listami

  for i := 0 to n - 1 do A[i] := nil;

  // Odczytujemy kolejne definicje krawędzi

  for i := 0 to m - 1 do
  begin
    read(v1,v2);        // Wierzchołek startowy i końcowy krawędzi
    new(p);             // Tworzymy nowy element
    p^.v := v2;         // Numerujemy go jako v2
    p^.next := A[v1];   // Dodajemy go na początek listy A[v1]
    A[v1] := p;
    new(p);             // Krawędź w drugą stronę, bo graf jest nieskierowany
    p^.v := v1;
    p^.next := A[v2];
    A[v2] := p;
  end;

  if isBipartite(n,A) then writeln('BIPARTITE GRAPH') else writeln('NOT A BIPARTITE GRAPH');

  // Usuwamy tablicę list sąsiedztwa

  for i := 0 to n - 1 do
  begin
    p := A[i];
    while p <> nil do
    begin
      r := p;
      p := p^.next;
      dispose(r);
    end;
  end;

  SetLength(A,0);
end.
Code::Blocks
// Testowanie dwudzielności grafu
// Data: 24.11.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>

using namespace std;

const int MAXINT = -2147483647;

// Typy dla dynamicznej tablicy list sąsiedztwa i kolejki

struct slistEl
{
  slistEl * next;
  int v;
};

// Definicja typu obiektowego queue
//---------------------------------
class queue
{
  private:
    slistEl * head;
    slistEl * tail;

  public:
    queue();      // konstruktor
    ~queue();     // destruktor
    bool empty(void);
    int  front(void);
    void push(int v);
    void pop(void);
};

//---------------------
// Metody obiektu queue
//---------------------

// Konstruktor - tworzy pustą listę
//---------------------------------
queue::queue()
{
  head = tail = NULL;
}

// Destruktor - usuwa listę z pamięci
//-----------------------------------
queue::~queue()
{
  while(head) pop();
}

// Sprawdza, czy kolejka jest pusta
//---------------------------------
bool queue::empty(void)
{
  return !head;
}

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
int queue::front(void)
{
  if(head) return head->v;
  else     return -MAXINT;
}

// Zapisuje do kolejki
//--------------------
void queue::push(int v)
{
  slistEl * p = new slistEl;
  p->next = NULL;
  p->v = v;
  if(tail) tail->next = p;
  else     head = p;
  tail = p;
}

// Usuwa z kolejki
//----------------
void queue::pop(void)
{
  if(head)
  {
    slistEl * p = head;
    head = head->next;
    if(!head) tail = NULL;
    delete p;
  }
}

// Funkcja testuje dwudzielność grafu
// n - liczba wierzchołków grafu
// A - tablica list sąsiedztwa
//-----------------------------------
bool isBipartite(int n, slistEl ** A)
{
  queue Q;
  int * C;
  int v,u,i;
  slistEl * p;

  C = new int [n];         // Tworzymy tablicę kolorów
  for(i = 0; i < n; i++) C[i] = 0;

  for(i = 0; i < n; i++)   // Przechodzimy przez kolejne wierzchołki
    if(!C[i])              // Szukamy wierzchołka szarego
    {
      C[i] = 1;            // Wierzchołek startowy kolorujemy na czerwono
      Q.push(i);           // i umieszczamy w kolejce

      while(!Q.empty())    // Przejście BFS
      {
        v = Q.front();     // Pobieramy wierzchołek z kolejki
        Q.pop();           // Pobrany wierzchołek usuwamy z kolejki
        for(p = A[v]; p; p = p->next) // Przeglądamy sąsiadów wierzchołka v
        {
          u = p->v;        // pobieramy z listy sąsiedztwa numer sąsiada
          if(C[u] == C[v])
          {
            delete [] C;
            return false;  // Sąsiad ma ten sam kolor
          }

          if(!C[u])        // Jeśli wierzchołek nie jest odwiedzony,
          {
            C[u] = -C[v];  // kolorujemy go na kolor przeciwny
            Q.push(u);     // i umieszczamy w kolejce
          }
        }
      }
    }

  delete [] C;

  return true;
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main()
{
  int n,m,i,v1,v2;
  slistEl * p,* r,** A;

  cin >> n >> m;         // Czytamy liczbę wierzchołków i krawędzi

  A = new slistEl * [n]; // Tworzymy tablicę list sąsiedztwa

  // Tablice wypełniamy pustymi listami

  for(i = 0; i < n; i++) A[i] = NULL;

  // Odczytujemy kolejne definicje krawędzi

  for(i = 0; i < m; i++)
  {
    cin >> v1 >> v2;    // Wierzchołek startowy i końcowy krawędzi
    p = new slistEl;    // Tworzymy nowy element
    p->v = v2;          // Numerujemy go jako v2
    p->next = A[v1];    // Dodajemy go na początek listy A[v1]
    A[v1] = p;
    p = new slistEl;    // Krawędź w drugą stronę, bo graf jest nieskierowany
    p->v = v1;
    p->next = A[v2];
    A[v2] = p;
  }

  if(isBipartite(n,A)) cout << "BIPARTITE GRAPH"; else cout << "NOT A BIPARTITE GRAPH";

  cout << endl;

  // Usuwamy tablicę list sąsiedztwa

  for(i = 0; i < n; i++)
  {
    p = A[i];
    while(p)
    {
      r = p;
      p = p->next;
      delete r;
    }
  }

  delete [] A;

  return 0;
}
Free Basic
' Testowanie dwudzielności grafu
' Data: 24.11.2013
' (C)2013 mgr Jerzy Wałaszek
'---------------------------

Const MAXINT = 2147483647

' Typy dla dynamicznej tablicy list sąsiedztwa i kolejki

Type slistEl
  next As slistEl Ptr
  v As Integer
End Type

' Definicja typu obiektowego queue
'---------------------------------
Type queue
  Private:
    head As slistEl Ptr
    tail As slistEl Ptr

  Public:
    Declare Constructor()
    Declare Destructor()
    Declare Function empty() As Integer
    Declare Function front As Integer
    Declare Sub push(ByVal v As Integer)
    Declare Sub pop()
End Type

'---------------------
' Metody obiektu queue
'---------------------

' Konstruktor - tworzy pustą listę
'---------------------------------
Constructor queue()
  head = 0
  tail = 0
End Constructor

' Destruktor - usuwa listę z pamięci
'-----------------------------------
Destructor queue()
  While empty = 0: pop: Wend
End Destructor

' Sprawdza, czy kolejka jest pusta
'---------------------------------
Function queue.empty() As Integer
  If head = 0 Then Return 1
  Return 0
End Function

' Zwraca początek kolejki.
' Wartość specjalna to -MAXINT
'-----------------------------
Function queue.front() As Integer
  If head = 0 then
    front = -MAXINT
  Else
    front = head->v
  End If
End Function

' Zapisuje do kolejki
'--------------------
Sub queue.push(ByVal v As Integer)
  Dim p As slistEl Ptr
  p = new slistEl
  p->next = 0
  p->v = v
  If tail = 0 Then
    head = p
  Else
    tail->next = p
  End If
  tail = p
End Sub

' Usuwa z kolejki
'----------------
Sub queue.pop()
  Dim p As slistEl Ptr
  If head Then
    p = head
    head = head->next
    If head = 0 Then tail = 0
    Delete p
  End If
End Sub

' Funkcja testuje dwudzielność grafu
' n - liczba wierzchołków grafu
' A - tablica list sąsiedztwa
'-----------------------------------
Function isBipartite(ByVal n As integer, ByVal A As slistEl Ptr Ptr) As Integer

  Dim As queue Q
  Dim As Integer Ptr C
  Dim As Integer v,u,i
  Dim As slistEl Ptr p

  C = New Integer [n]      ' Tworzymy tablicę kolorów
  For i = 0 To n - 1
  	 C[i] = 0
  Next

  For i = 0 To n - 1       ' Przechodzimy przez kolejne wierzchołki
    If C[i] = 0 Then       ' Szukamy wierzchołka szarego
      C[i] = 1             ' Wierzchołek startowy kolorujemy na czerwono
      Q.push(i)            ' i umieszczamy w kolejce

      While Q.empty() = 0  ' Przejście BFS
        v = Q.front()      ' Pobieramy wierzchołek z kolejki
        Q.pop()            ' Pobrany wierzchołek usuwamy z kolejki
        p = A[v]
        While p            ' Przeglądamy sąsiadów wierzchołka v
          u = p->v         ' pobieramy z listy sąsiedztwa numer sąsiada
          If C[u] = C[v] Then
            Delete [] C
            Return 0       ' Sąsiad ma ten sam kolor
          End If

          If C[u] = 0 Then ' Jeśli wierzchołek nie jest odwiedzony,
            C[u] = -C[v]   ' kolorujemy go na kolor przeciwny
            Q.push(u)      ' i umieszczamy w kolejce
          End If
          
          p = p->Next      ' Następny wierzchołek
          
        Wend
      Wend
    End If
  Next
  
  Delete [] C

  Return 1
End Function

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As Integer n,m,i,v1,v2
Dim As slistEl Ptr p,r
Dim As slistEl Ptr Ptr A

Open Cons For Input As #1

Input #1,n,m            ' Czytamy liczbę wierzchołków i krawędzi

A = new slistEl Ptr [n] ' Tworzymy tablicę list sąsiedztwa

' Tablicę wypełniamy pustymi listami

For i = 0 To n - 1
  A[i] = 0
Next

' Odczytujemy kolejne definicje krawędzi

For i = 0 To m -1
  Input #1,v1,v2       ' Wierzchołek startowy i końcowy krawędzi
  p = new slistEl      ' Tworzymy nowy element
  p->v = v2            ' Numerujemy go jako v2
  p->next = A[v1]      ' Dodajemy go na początek listy A[v1]
  A[v1] = p
  p = new slistEl      ' Krawędź w drugą stronę, bo graf jest nieskierowany
  p->v = v1
  p->next = A[v2]
  A[v2] = p
Next

Close #1

If isBipartite(n,A) Then
  Print "BIPARTITE GRAPH"
Else
  Print "NOT A BIPARTITE GRAPH"
EndIf

' Usuwamy tablicę list sąsiedztwa

For i = 0 To n - 1
  p = A[i]
  While p
    r = p
    p = p->Next
    Delete r
  Wend
Next

Delete [] A

End
Wynik
17 23
0 2 0 3
1 2 1 14
2 6
3 4 3 6 3 13
4 7 4 12
5 6 5 9 5 10
6 7 6 8 6 12
7 13
8 9
10 11
10 14
10 15
11 16
12 16
BIPARTITE GRAPH
17 24
0 2 0 3
1 2 1 14
2 6
3 4 3 6 3 13
4 7 4 12
5 6 5 9 5 10
6 7 6 8 6 12
7 13
8 9
10 11
10 14
10 15
11 16
12 16
13 16
NOT A BIPARTITE GRAPH

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.