Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2021 mgr Jerzy Wałaszek
I LO w Tarnowie

Grafy dwudzielne

SPIS TREŚCI

Problem

Należy zbadać, czy dany graf nieskierowany i spójny jest grafem dwudzielnym.

Rozwiązanie

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

obrazek

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:

obrazek Mamy przykładowy graf, dla którego chcemy sprawdzić dwudzielność ( ang. bipartiteness ). Początkowo wszystkie wierzchołki posiadają kolor neutralny – tutaj szary.
obrazek 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 ).

obrazek 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.
obrazek Operację sprawdzania i kolorowania powtarzamy dla każdego sąsiada zgodnie z wybranym algorytmem przejścia grafu – tutaj BFS.
obrazek I dalej...
obrazek I dalej...
obrazek 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.
Zmienne 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 kroki 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 kroki K09...K15
rozpoczynamy przejście BFS
K09:         v  ← Q.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 kroki 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.


Przykładowe programy

Uwaga:

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.
Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli ):

Graf dwudzielny:

obrazek      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:

obrazek   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
Pascal
// 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.
C++
// 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;
}
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
Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2021 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.