Serwis Edukacyjny w I-LO w Tarnowie ![]() Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej Autor artykułu: mgr Jerzy Wałaszek |
©2025 mgr Jerzy Wałaszek |
ProblemNależy wyznaczyć stopień grafu. Stopień grafu (ang. graph degree) jest równy maksymalnemu stopniowi wierzchołka (ang. vertex degree) w tym grafie. Stopień wierzchołka to liczba krawędzi, które są incydentne z wierzchołkiem (pętle liczy się za 2). |
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.
K01: dg ← 0 ; zerujemy stopień grafu K02: Dla v = 0, 1, …, n-1: ; przechodzimy przez kolejne wykonuj kroki K02…K06 ; wierzchołki grafu K03: dv ← 0 ; zerujemy stopień wierzchołka K04 Dla każdego sąsiada u wierzchołka v : ; przechodzimy wykonuj krok K05 ; przez sąsiadów wierzchołka v K05: Jeśli u = v, to dv ← dv+2 ; pętle zliczamy za 2, inaczej dv ← dv+1 ; zwykłe krawędzie za 1 K06: Jeśli dv > dg, ; ustalamy stopień grafu to dg ← dv K07: Zakończ z wynikiem dg
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, 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 |
Dane przykładowe (przekopiuj do schowka
i wklej do okna konsoli):
|
Pascal// Stopień grafu nieskierowanego // Data : 26.04.2014 // (C)2014 mgr Jerzy Wałaszek //------------------------------ program graph_degree; // Definicja elementu // listy sąsiedztwa type PSLel = ^SLel; SLel = record // Następny element listy next : PSLel; // Wierzchołek docelowy v : integer; end; var // Liczba wierzchołków, // liczba krawędzi n, m : integer; // Graf G : array of PSLel; dg, dv, i, v, u : integer; p, r : PSLel; begin // Czytamy rozmiary grafu read(n, m); // Tworzymy zerowy graf G SetLength(G, n); for i := 0 to n-1 do G[i] := nil; // Odczytujemy definicje // krawędzi grafu G for i := 1 to m do begin // Czytamy wierzchołki read(v, u); // Tworzymy rekord listy new(p); // Wypełniamy go danymi p^.v := u; // Rekord dołączamy // do listy sąsiedztwa // wierzchołka v p^.next := G[v]; G[v] := p; // To samo dla krawędzi // odwrotnej, // o ile nie jest to pętla if v <> u then begin new(p); p^.v := v; p^.next := G[u]; G[u] := p; end; end; // Wyznaczamy stopień grafu dg := 0; // Przechodzimy przez kolejne // wierzchołki grafu for v := 0 to n-1 do begin // Zerujemy stopień // wierzchołka dv := 0; // Przeglądamy sąsiadów // wierzchołka v p := G[v]; while p <> nil do begin if p^.v = v then // Pętle zliczamy za 2 inc(dv, 2) else // Zwykłą krawędź // zliczamy za 1 inc(dv); // Przeglądamy sąsiadów // wierzchołka v // Następny sąsiad p := p^.next; end; // Jeśli stopień jest większy // od dg, to uaktualniamy if dv > dg then dg := dv; 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. |
// Stopień grafu nieskierowanego // Data : 26.04.2014 // (C)2014 mgr Jerzy Wałaszek //------------------------------ #include <iostream> using namespace std; // Definicja elementu // listy sąsiedztwa struct SLel { // Następny element listy SLel * next; // Wierzchołek docelowy int v; }; int main() { // Liczba wierzchołków, // liczba krawędzi int n, m; // Graf SLel **G; int dg, dv, i, v, u; SLel *p, *r; // Czytamy rozmiary grafu cin >> n >> m; // Tworzymy zerowy graf G G = new SLel * [n]; for(i = 0; i < n; i++) G[i] = nullptr; // Odczytujemy definicje // krawędzi grafu G for(i = 0; i < m; i++) { // Czytamy wierzchołki cin >> v >> u; // Tworzymy rekord listy p = new SLel; // Wypełniamy go danymi p->v = u; // Rekord dołączamy do // listy sąsiedztwa // wierzchołka v p->next = G[v]; G[v] = p; // To samo dla krawędzi // odwrotnej o ile nie // jest to pętla if(v != u) { p = new SLel; p->v = v; p->next = G[u]; G[u] = p; } } // Wyznaczamy stopień grafu dg = 0; // Przechodzimy przez kolejne // wierzchołki grafu for(v = 0; v < n; v++) { // Zerujemy stopień wierzchołka dv = 0; // Przeglądamy sąsiadów // wierzchołka v for(p = G[v]; p; p = p->next) // Pętle zliczamy za 2 if(p->v == v) dv += 2; // Zwykłą krawędź zliczamy za 1 else dv++; // Jeśli stopień jest większy // od dg, to uaktualniamy if(dv > dg) dg = dv; } // 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; } |
Basic' Stopień grafu nieskierowanego ' Data : 26.04.2014 ' (C)2014 mgr Jerzy Wałaszek '------------------------------ ' Definicja elementu listy sąsiedztwa Type SLel ' Następny element listy Dim As SLel Ptr next ' Wierzchołek docelowy Dim As Integer v End Type ' Liczba wierzchołków, liczba krawędzi Dim As Integer n, m Dim As SLel Ptr Ptr G ' Graf Dim As Integer dg, dv, i, v, u Dim As SLel Ptr p, r Open Cons For Input As #1 ' Czytamy rozmiary grafu Input #1, n, m ' Tworzymy zerowy graf G G = new SLel Ptr [n] For i = 0 To n-1 G[i] = 0 Next ' Odczytujemy definicje krawędzi grafu G For i = 1 to m ' Czytamy wierzchołki Input #1, v, u ' Tworzymy rekord listy p = New SLel ' Wypełniamy go danymi p->v = u ' Rekord dołączamy do listy ' sąsiedztwa wierzchołka v p->next = G[v] G[v] = p ' To samo dla krawędzi odwrotnej ' o ile nie jest to pętla If v <> u Then p = new SLel p->v = v p->next = G[u] G[u] = p End If Next Close #1 ' Wyznaczamy stopień grafu dg = 0 ' Przechodzimy przez kolejne ' wierzchołki grafu For v = 0 To n-1 ' Zerujemy stopień wierzchołka dv = 0 p = G[v] ' Przeglądamy sąsiadów wierzchołka v While p If p->v = v Then ' Pętle zliczamy za 2 dv += 2 Else ' Zwykłą krawędź zliczamy za 1 dv += 1 End If ' Następny sąsiad p = p->Next Wend ' Jeśli stopień jest większy od dg, ' to uaktualniamy If dv > dg Then dg = dv 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 |
Python
(dodatek)# Stopień grafu nieskierowanego # Data : 18.12.2024 # (C)2024 mgr Jerzy Wałaszek #------------------------------ # Definicja klasy elementu listy sąsiedztwa class SLel: def __init__(self): # Następny element listy self.next = None # Wierzchołek docelowy self.v = 0 # Czytamy rozmiary grafu x = input().split() n = int(x[0]) m = int(x[1]) # Tworzymy zerowy graf G g = [None] * n # Odczytujemy definicje krawędzi grafu G for i in range(m): # Czytamy wierzchołki x = input().split() v = int(x[0]) u = int(x[1]) # Tworzymy rekord listy p = SLel() # Wypełniamy go danymi p.v = u # Rekord dołączamy do listy # sąsiedztwa wierzchołka v p.next = g[v] g[v] = p # To samo dla krawędzi odwrotnej # o ile nie jest to pętla if v is not u: p = SLel() p.v = v p.next = g[u] g[u] = p # Wyznaczamy stopień grafu dg = 0 # Przechodzimy przez kolejne # wierzchołki grafu for v in range(n): # Zerujemy stopień wierzchołka dv = 0 p = g[v] # Przeglądamy sąsiadów wierzchołka v while p: if p.v == v: # Pętle zliczamy za 2 dv += 2 else: # Zwykłą krawędź zliczamy za 1 dv += 1 # Następny sąsiad p = p.next # Jeśli stopień jest większy od dg, # to uaktualniamy if dv > dg: dg = dv # Wyświetlamy wynik print() print(dg) print() # Usuwamy dynamiczne struktury for i in range(n): while g[i]: g[i] = g[i].next del g |
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 |
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.
K01: Utwórz n elementową tablicę DV i wyzeruj ją K02: Dla v = 0, 1, …, n-1: ; przechodzimy przez wszystkie wykonuj kroki K03…K05 ; wierzchołki grafu K03: Dla każdego sąsiada u wierzchołka v : wykonuj kroki 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 krok K08 K08: Jeśli DV[v] > d, to d ← DV[v] K09: Zakończ z wynikiem d
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 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. |
Dane przykładowe (przekopiuj do schowka i wklej
do okna konsoli):
|
Pascal// Stopień grafu skierowanego // Data : 26.04.2014 // (C)2014 mgr Jerzy Wałaszek //--------------------------- program graph_degree; // Definicja elementu listy sąsiedztwa type PSLel = ^SLel; SLel = record // Następny element listy next : PSLel; // Wierzchołek docelowy v : integer; end; var // Liczba wierzchołków, // liczba krawędzi n, m : integer; // Graf G : array of PSLel; // Tablica stopni wierzchołków DV : array of integer; d, i, v, u : integer; p, r : PSLel; begin // Czytamy rozmiary grafu read(n, m); // Tworzymy zerowy graf G SetLength(G, n); // Tworzymy tablicę DV SetLength(DV, n); for i := 0 to n-1 do begin // Pusta lista G[i] := nil; // Stopień zerowy DV[i] := 0; end; // Odczytujemy definicje // krawędzi grafu G for i := 1 to m do begin // Czytamy wierzchołki read(v, u); // Tworzymy rekord listy new(p); // Wypełniamy go danymi p^.v := u; // Rekord dołączamy do listy // sąsiedztwa wierzchołka v p^.next := G[v]; G[v] := p; end; // Wyznaczamy stopień grafu // Przechodzimy przez kolejne // wierzchołki grafu for v := 0 to n-1 do begin // Przeglądamy listę // sąsiadów wierzchołka v p := G[v]; while p <> NIL do begin // Zwiększamy stopień // wyjściowy v inc(DV[v]); // Zwiększamy stopień // wejściowy sąsiada v inc(DV[p^.v]); // Następny sąsiad p := p^.next; 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. |
// Stopień grafu skierowanego // Data : 26.04.2014 // (C)2014 mgr Jerzy Wałaszek //--------------------------- #include <iostream> using namespace std; // Definicja elementu // listy sąsiedztwa struct SLel { // Następny element listy SLel * next; // Wierzchołek docelowy int v; }; int main() { // Liczba wierzchołków, // liczba krawędzi int n, m; // Graf SLel **G; // Tablica stopni wierzchołków int *DV; int d, i, v, u; SLel *p, *r; // Czytamy rozmiary grafu cin >> n >> m; // Tworzymy zerowy graf G G = new SLel * [n]; // Tworzymy tablicę DV DV = new int [n]; for(i = 0; i < n; i++) { // Pusta lista G[i] = nullptr; // Stopień zerowy DV[i] = 0; } // Odczytujemy definicje // krawędzi grafu G for(i = 0; i < m; i++) { // Czytamy wierzchołki cin >> v >> u; // Tworzymy rekord listy p = new SLel; // Wypełniamy go danymi p->v = u; // Rekord dołączamy do listy // sąsiedztwa wierzchołka v p->next = G[v]; G[v] = p; } // Wyznaczamy stopień grafu // Przechodzimy przez kolejne // wierzchołki grafu for(v = 0; v < n; v++) // Przeglądamy listę sąsiadów // wierzchołka v for(p = G[v]; p; p = p->next) { // Zwiększamy stopień // wyjściowy v DV[v] ++; // Zwiększamy stopień // wejściowy sąsiada v DV[p->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; } |
Basic' Stopień grafu skierowanego ' Data : 26.04.2014 ' (C)2014 mgr Jerzy Wałaszek '--------------------------- ' Definicja elementu listy sąsiedztwa Type SLel ' Następny element listy Dim As SLel Ptr Next ' Wierzchołek docelowy Dim As Integer v End Type ' Liczba wierzchołków, liczba krawędzi Dim As Integer n, m ' Graf Dim As SLel Ptr Ptr G ' Tablica stopni wierzchołków Dim As Integer Ptr DV Dim As Integer d, i, v, u Dim As SLel Ptr p, r Open Cons For Input As #1 ' Czytamy rozmiary grafu Input #1, n, m ' Tworzymy zerowy graf G G = New SLel Ptr [n] ' Tworzymy tablicę DV DV = New Integer [n] For i = 0 To n-1 ' Pusta lista G[i] = 0 ' Stopień zerowy DV[i] = 0 Next ' Odczytujemy definicje krawędzi grafu G For i = 1 To m ' Czytamy wierzchołki Input #1, v, u ' Tworzymy rekord listy p = New SLel ' Wypełniamy go danymi p->v = u ' Rekord dołączamy do listy ' sąsiedztwa wierzchołka v p->next = G[v] G[v] = p Next ' Wyznaczamy stopień grafu ' Przechodzimy przez kolejne ' wierzchołki grafu For v = 0 To n-1 p = G[v] ' Przeglądamy listę ' sąsiadów wierzchołka v While p ' Zwiększamy stopień ' wyjściowy v DV[v] += 1 ' Zwiększamy stopień ' wejściowy sąsiada v DV[p->v] += 1 ' Następny sąsiad p = p->Next 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 |
Python
(dodatek)# Stopień grafu skierowanego # Data : 19.12.2024 # (C)2024 mgr Jerzy Wałaszek #--------------------------- # Definicja klasy elementu listy sąsiedztwa class SLel: def __init__(self): # Następny element listy self.next = None # Wierzchołek docelowy self.v = 0 # Czytamy rozmiary grafu x = input().split() n = int(x[0]) m = int(x[1]) # Tworzymy zerowy graf G g = [None] * n # Tworzymy tablicę DV dv = [0] * n # Odczytujemy definicje krawędzi grafu G for i in range(m): # Czytamy wierzchołki x = input().split() v = int(x[0]) u = int(x[1]) # Tworzymy rekord listy p = SLel() # Wypełniamy go danymi p.v = u # Rekord dołączamy do listy # sąsiedztwa wierzchołka v p.next = g[v] g[v] = p # Wyznaczamy stopień grafu # Przechodzimy przez kolejne # wierzchołki grafu for v in range(n): p = g[v] # Przeglądamy listę # sąsiadów wierzchołka v while p: # Zwiększamy stopień # wyjściowy v dv[v] += 1 # Zwiększamy stopień # wejściowy sąsiada v dv[p.v] += 1 # Następny sąsiad p = p.next # Szukamy największego stopnia d = dv[0] for v in range(1,n): if dv[v] > d: d = dv[v] # Wyświetlamy wynik print() print(d) print() # Usuwamy dynamiczne struktury for i in range(n): while g[i]: g[i] = g[i].next del g, dv |
Wynik: |
9 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 |
![]() |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2025 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:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.