Stopień grafu


Tematy pokrewne   Podrozdziały
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
  Stopień grafu nieskierowanego
Stopień grafu skierowanego

Problem

Wyznaczyć stopień grafu

 

 

Stopień grafu (ang. graph degree) jest równy maksymalnemu stopniowi wierzchołka (ang. vertex degree). Stopień wierzchołka to liczba krawędzi, które są incydentne z tym wierzchołkiem (pętle liczy się za 2).

 

Stopień grafu nieskierowanego

W grafie nieskierowanym stopień wierzchołka wyznaczamy bardzo prosto – wystarczy zliczyć sąsiadów (jeśli graf zawiera pętle, to należy je policzyć za 2). Następnie wyznaczamy największą wartość otrzymanego stopnia i w ten sposób otrzymamy stopień grafu.

 

Algorytm wyznaczania stopnia grafu nieskierowanego

Wejście
n  –  liczba wierzchołków w grafie G, n symbol C
G  –  graf zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje.
Wyjście:
dg  –  stopień grafu, dg symbol C
Elementy pomocnicze:
dv  –  stopień wierzchołka, dv symbol C
v,u  –  wierzchołki grafu, v,u symbol C
Lista kroków:
K01: dg ← 0 ; zerujemy stopień grafu
K02: Dla v = 0,1,...,n-1 wykonuj K02...K06 ; przechodzimy przez kolejne wierzchołki grafu
K03:     dv ← 0 ; zerujemy stopień wierzchołka
K04     Dla każdego sąsiada u wierzchołka v wykonuj K05 ; przechodzimy przez sąsiadów wierzchołka v
K05:         Jeśli u = v, to dv dv + 2
        inaczej dvdv + 1
; pętle zliczamy za 2
; zwykłe krawędzie za 1
K06:     Jeśli dv > dg, to dgdv ; ustalamy stopień grafu
K07: Zakończ z wynikiem dg  

 

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, a następnie wyznacza jego stopień. Graf może zawierać pętle oraz krawędzie wielokrotne. Dane wejściowe posiadają następującą postać:

 

Pierwsze dwie liczby oznaczają kolejno liczbę wierzchołków n oraz liczbę krawędzi m. Następne m par liczb definiuje wierzchołki grafu, pomiędzy którymi jest krawędź nieskierowana. W pętli oba wierzchołki pary są takie same.

 

 

Przykładowe dane wejściowe

    8 22
0 1 0 3 0 3 0 4
1 1 1 3 1 4 1 5
2 3 2 3 2 5
3 3 3 4 3 7
4 5 4 6 4 7
5 5 5 6
6 6 6 7
7 7

 

Lazarus
// Stopień grafu nieskierowanego
// Data   : 26.04.2014
// (C)2014 mgr Jerzy Wałaszek
//------------------------------

program graph_degree;

// Definicja elementu listy sąsiedztwa
type
  PslistEl = ^slistEl;
  slistEl = record
    next : PslistEl;              // Następny element listy
    v : integer;                  // Wierzchołek docelowy
  end;

var
  n,m : integer;                  // Liczba wierzchołków, liczba krawędzi
  G : array of PslistEl;          // Graf
  dg,dv,i,v,u : integer;
  p,r : PslistEl;
begin
  read(n,m);                      // Czytamy rozmiary grafu

  SetLength(G,n);                 // Tworzymy zerowy graf G
  for i := 0 to n - 1 do G[i] := nil;

  // Odczytujemy definicje krawędzi grafu G

  for i := 1 to m do
  begin
    read(v,u);                    // Czytamy wierzchołki
    new(p);                       // Tworzymy rekord listy
    p^.v := u;                    // Wypełniamy go danymi
    p^.next := G[v];              // Rekord dołączamy do listy sąsiedztwa wierzchołka v
    G[v] := p;

    if v <> u then                // To samo dla krawędzi odwrotnej o ile nie jest to pętla
    begin
      new(p);
      p^.v := v;
      p^.next := G[u];
      G[u] := p;
    end;
  end;

  // Wyznaczamy stopień grafu

  dg := 0;

  for v := 0 to n - 1 do          // Przechodzimy przez kolejne wierzchołki grafu
  begin
    dv := 0;                      // Zerujemy stopień wierzchołka
    p := G[v];                    // Przeglądamy sąsiadów wierzchołka v
    while p <> nil do
    begin
      if p^.v = v then inc(dv,2)  // Pętle zliczamy za 2
      else            inc(dv);    // Zwykłą krawędź zliczamy za 1
      p := p^.next;               // Następny sąsiad
    end;
    if dv > dg then dg := dv;     // Jeśli stopień jest większy od dg, to uaktualniamy
  end;

  // Wyświetlamy wynik

  writeln;
  writeln(dg);
  writeln;

  // Usuwamy dynamiczne struktury

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

end.
Code::Blocks
// Stopień grafu nieskierowanego
// Data   : 26.04.2014
// (C)2014 mgr Jerzy Wałaszek
//------------------------------

#include <iostream>

using namespace std;

// Definicja elementu listy sąsiedztwa

struct slistEl
{
  slistEl * next ;                // Następny element listy
  int v;                          // Wierzchołek docelowy
};

int main()
{
  int n,m;                        // Liczba wierzchołków, liczba krawędzi
  slistEl **G;                    // Graf
  int dg,dv,i,v,u;
  slistEl *p,*r;

  cin >> n >> m;                  // Czytamy rozmiary grafu

  G = new slistEl * [n];          // Tworzymy zerowy graf G
  for(i = 0; i < n; i++) G[i] = NULL;

  // Odczytujemy definicje krawędzi grafu G

  for(i = 0; i < m; i++)
  {
    cin >> v >> u;                // Czytamy wierzchołki
    p = new slistEl;              // Tworzymy rekord listy
    p->v = u;                     // Wypełniamy go danymi
    p->next = G[v];               // Rekord dołączamy do listy sąsiedztwa wierzchołka v
    G[v] = p;

    if(v != u)                    // To samo dla krawędzi odwrotnej o ile nie jest to pętla
    {
      p = new slistEl;
      p->v = v;
      p->next = G[u];
      G[u] = p;
    }
  }

  // Wyznaczamy stopień grafu

  dg = 0;

  for(v = 0; v < n; v++)          // Przechodzimy przez kolejne wierzchołki grafu
  {
    dv = 0;                       // Zerujemy stopień wierzchołka
    for(p = G[v]; p; p = p->next) // Przeglądamy sąsiadów wierzchołka v
      if(p->v == v) dv += 2;      // Pętle zliczamy za 2
      else          dv++;         // Zwykłą krawędź zliczamy za 1
    if(dv > dg) dg = dv;          // Jeśli stopień jest większy od dg, to uaktualniamy
  }

  // Wyświetlamy wynik

  cout << endl << dg << endl << endl;

  // Usuwamy dynamiczne struktury

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

  return 0;
}
Free Basic
' Stopień grafu nieskierowanego
' Data   : 26.04.2014
' (C)2014 mgr Jerzy Wałaszek
'------------------------------

' Definicja elementu listy sąsiedztwa

Type slistEl
  Dim As slistEl Ptr next         ' Następny element listy
  Dim As Integer v                ' Wierzchołek docelowy
End Type

Dim As Integer n,m                ' Liczba wierzchołków, liczba krawędzi
Dim As slistEl Ptr Ptr G          ' Graf
Dim As Integer dg,dv,i,v,u
Dim As slistEl Ptr p,r

Open Cons For Input As #1

Input #1,n,m                      ' Czytamy rozmiary grafu

G = new slistEl Ptr [n]           ' Tworzymy zerowy graf G
For i = 0 To n - 1
  G[i] = 0
Next

' Odczytujemy definicje krawędzi grafu G

For i = 1  to m
  Input #1,v,u                    ' Czytamy wierzchołki
  p = New slistEl                 ' Tworzymy rekord listy
  p->v = u                        ' Wypełniamy go danymi
  p->next = G[v]                  ' Rekord dołączamy do listy sąsiedztwa wierzchołka v
  G[v] = p

  If v <> u Then                  ' To samo dla krawędzi odwrotnej o ile nie jest to pętla
    p = new slistEl
    p->v = v
    p->next = G[u]
    G[u] = p
  End If
Next

Close #1

' Wyznaczamy stopień grafu

dg = 0

For v = 0 To n - 1                ' Przechodzimy przez kolejne wierzchołki grafu
  dv = 0                          ' Zerujemy stopień wierzchołka
  p = G[v]
  While p                         ' Przeglądamy sąsiadów wierzchołka v
    If p->v = v Then
      dv += 2                     ' Pętle zliczamy za 2
    Else
      dv += 1                     ' Zwykłą krawędź zliczamy za 1
    End If
    p = p->Next                   ' Następny sąsiad
  Wend  
  If dv > dg Then dg = dv         ' Jeśli stopień jest większy od dg, to uaktualniamy
Next

' Wyświetlamy wynik

Print
Print Using "&";dg
Print

' Usuwamy dynamiczne struktury

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

End
Wynik
8 22
0 1 0 3 0 3 0 4
1 1 1 3 1 4 1 5
2 3 2 3 2 5
3 3 3 4 3 7
4 5 4 6 4 7
5 5 5 6
6 6 6 7
7 7

9

 

Stopień grafu skierowanego

W grafie skierowanym stopień wierzchołka jest sumą stopni wchodzących (ang. in-degree) i wychodzących (ang. out-degree). Aby efektywnie wyznaczyć te stopnie, tworzymy pomocniczą tablicę DV o tylu elementach, ile wierzchołków posiada graf. Elementy tej tablicy będą zliczać stopnie wierzchołków grafu. W tym celu najpierw zerujemy wszystkie elementy tablicy DV, a następnie przechodzimy przez kolejne wierzchołki grafu. W danym wierzchołku v przeglądamy kolejnych sąsiadów u. Dla każdego sąsiada u zwiększamy o 1 DV[v] (krawędź wychodząca) oraz DV[u] (krawędź wchodząca). Gdy przeglądniemy cały graf, należy wyszukać w tablicy DV największy element, który będzie stopniem grafu.

 

Algorytm wyznaczania stopnia grafu skierowanego

Wejście
n  –  liczba wierzchołków w grafie G, n symbol C
G  –  graf zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje.
Wyjście:
d  –  stopień grafu, d symbol C
Elementy pomocnicze:
DV  –  n elementowa tablica stopni wierzchołków o elementach całkowitych
v,u  –  wierzchołki grafu, v,u symbol C
Lista kroków:
K01: Utwórz n elementową tablicę DV i wyzeruj ją  
K02: Dla v = 0,1,...,n - 1 wykonuj K03...K05 ; przechodzimy przez wszystkie wierzchołki grafu
K03:     Dla każdego sąsiada u wierzchołka v wykonuj K04...K05  
K04         DV[v] ← DV[v] + 1 ; zwiększamy stopień wyjściowy v
K05:         DV[u] ← DV[u] + 1 ; zwiększamy stopień wejściowy u
K06: d = DV[0] ; szukamy największego stopnia
K07: Dla v = 1,2,...,n-1 wykonuj K08  
K08:     Jeśli DV[v] > d, to dDV[v]  
K09 Zakończ z wynikiem d  

 

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 skierowanego, a następnie wyznacza jego stopień. Graf może zawierać pętle oraz krawędzie wielokrotne. Dane wejściowe posiadają następującą postać:

 

Pierwsze dwie liczby oznaczają kolejno liczbę wierzchołków n oraz liczbę krawędzi m. Następne m par liczb definiuje wierzchołki grafu: wierzchołek startowy i docelowy krawędzi. W pętli oba wierzchołki pary są takie same.

 

 

Przykładowe dane wejściowe

    8 20
0 0 0 1
1 4 1 5 1 6 1 8
2 3 2 5 2 7
4 0 4 2 4 6 4 7 4 8
5 5
6 6 6 3 6 7
7 0
8 8

 

Lazarus
// Stopień grafu skierowanego
// Data   : 26.04.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

program graph_degree;

// Definicja elementu listy sąsiedztwa
type
  PslistEl = ^slistEl;
  slistEl = record
    next : PslistEl;              // Następny element listy
    v : integer;                  // Wierzchołek docelowy
  end;

var
  n,m : integer;                  // Liczba wierzchołków, liczba krawędzi
  G : array of PslistEl;          // Graf
  DV : array of integer;          // Tablica stopni wierzchołków
  d,i,v,u : integer;
  p,r : PslistEl;
begin
  read(n,m);                      // Czytamy rozmiary grafu

  SetLength(G,n);                 // Tworzymy zerowy graf G
  SetLength(DV,n);                // Tworzymy tablicę DV
  for i := 0 to n - 1 do
  begin
    G[i] := nil;                  // Pusta lista
    DV[i] := 0;                   // Stopień zerowy
  end;

  // Odczytujemy definicje krawędzi grafu G

  for i := 1 to m do
  begin
    read(v,u);                    // Czytamy wierzchołki
    new(p);                       // Tworzymy rekord listy
    p^.v := u;                    // Wypełniamy go danymi
    p^.next := G[v];              // Rekord dołączamy do listy sąsiedztwa wierzchołka v
    G[v] := p;
  end;

  // Wyznaczamy stopień grafu

  for v := 0 to n - 1 do          // Przechodzimy przez kolejne wierzchołki grafu
  begin
    p := G[v];                    // Przeglądamy listę sąsiadów wierzchołka v
    while p <> NIL do
    begin
      inc(DV[v]);                 // Zwiększamy stopień wyjściowy v
      inc(DV[p^.v]);              // Zwiększamy stopień wejściowy sąsiada v
      p := p^.next;               // Następny sąsiad
    end;
  end;

  // Szukamy największego stopnia

  d := DV[0];
  for v := 1 to n - 1 do
    if DV[v] > d then d := DV[v];

  // Wyświetlamy wynik

  writeln;
  writeln(d);
  writeln;

  // Usuwamy dynamiczne struktury

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

end.
Code::Blocks
// Stopień grafu skierowanego
// Data   : 26.04.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>

using namespace std;

// Definicja elementu listy sąsiedztwa

struct slistEl
{
  slistEl * next;                 // Następny element listy
  int v;                          // Wierzchołek docelowy
};

int main()
{
  int n,m;                        // Liczba wierzchołków, liczba krawędzi
  slistEl **G;                    // Graf
  int *DV;                        // Tablica stopni wierzchołków
  int d,i,v,u;
  slistEl *p,*r;

  cin >> n >> m;                  // Czytamy rozmiary grafu

  G = new slistEl * [n];          // Tworzymy zerowy graf G
  DV = new int [n];               // Tworzymy tablicę DV
  for(i = 0; i < n; i++)
  {
    G[i] = NULL;                  // Pusta lista
    DV[i] = 0;                    // Stopień zerowy
  }

  // Odczytujemy definicje krawędzi grafu G

  for(i = 0; i < m; i++)
  {
    cin >> v >> u;                // Czytamy wierzchołki
    p = new slistEl;              // Tworzymy rekord listy
    p->v = u;                     // Wypełniamy go danymi
    p->next = G[v];               // Rekord dołączamy do listy sąsiedztwa wierzchołka v
    G[v] = p;
  }

  // Wyznaczamy stopień grafu

  for(v = 0; v < n; v++)          // Przechodzimy przez kolejne wierzchołki grafu
    for(p = G[v]; p; p = p->next) // Przeglądamy listę sąsiadów wierzchołka v
    {
      DV[v]++;                    // Zwiększamy stopień wyjściowy v
      DV[p->v]++;                 // Zwiększamy stopień wejściowy sąsiada v
    }

  // Szukamy największego stopnia

  d = DV[0];
  for(v = 1; v < n; v++)
    if(DV[v] > d) d = DV[v];

  // Wyświetlamy wynik

  cout << endl << d << endl << endl;

  // Usuwamy dynamiczne struktury

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

  return 0;
}
Free Basic
' Stopień grafu skierowanego
' Data   : 26.04.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------

' Definicja elementu listy sąsiedztwa

Type slistEl
  Dim As slistEl Ptr Next         ' Następny element listy
  Dim As Integer v                ' Wierzchołek docelowy
End Type

Dim As Integer n,m                ' Liczba wierzchołków, liczba krawędzi
Dim As slistEl Ptr Ptr G          ' Graf
Dim As Integer Ptr DV             ' Tablica stopni wierzchołków
Dim As Integer d,i,v,u
Dim As slistEl Ptr p,r

Open Cons For Input As #1
  
Input #1,n,m                      ' Czytamy rozmiary grafu

G = New slistEl Ptr [n]           ' Tworzymy zerowy graf G
DV = New Integer [n]              ' Tworzymy tablicę DV
For i = 0 To n - 1
  G[i] = 0                        ' Pusta lista
  DV[i] = 0                       ' Stopień zerowy
Next

' Odczytujemy definicje krawędzi grafu G

For i = 1 To m
  Input #1,v,u                    ' Czytamy wierzchołki
  p = New slistEl                 ' Tworzymy rekord listy
  p->v = u                        ' Wypełniamy go danymi
  p->next = G[v]                  ' Rekord dołączamy do listy sąsiedztwa wierzchołka v
  G[v] = p
Next

' Wyznaczamy stopień grafu

For v = 0 To n - 1                ' Przechodzimy przez kolejne wierzchołki grafu
  p = G[v]
  While p                         ' Przeglądamy listę sąsiadów wierzchołka v
    DV[v] += 1                    ' Zwiększamy stopień wyjściowy v
    DV[p->v] += 1                 ' Zwiększamy stopień wejściowy sąsiada v
    p = p->Next                   ' Następny sąsiad
  Wend
Next

' Szukamy największego stopnia

d = DV[0]
For v = 1 To n - 1
  If DV[v] > d Then d = DV[v]
Next

' Wyświetlamy wynik

Print
Print Using "&";d
Print
  
' Usuwamy dynamiczne struktury

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

End
Wynik
8 20
0 0 0 1
1 4 1 5 1 6 1 8
2 3 2 5 2 7
4 0 4 2 4 6 4 7 4 8
5 5
6 6 6 3 6 7
7 0
8 8

6

 



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.