logo

In- Degree i Out-stopień w matematyce dyskretnej

Aby zrozumieć stopień wejściowy i wyjściowy wierzchołka, musimy najpierw poznać pojęcie stopnia wierzchołka. Następnie możemy łatwo zrozumieć stopień wejściowy i końcowy wierzchołka. Powinniśmy wiedzieć, że stopień wejściowy i stopień wyjściowy można określić tylko na wykresie skierowanym. Stopień wierzchołka możemy obliczyć za pomocą grafu nieskierowanego. W grafie nieskierowanym nie możemy obliczyć stopnia wejściowego i końcowego wierzchołka.

Stopień wierzchołka

Jeśli chcemy znaleźć stopień każdego wierzchołka w grafie, w tym przypadku musimy policzyć liczbę relacji, jakie tworzy dany wierzchołek z drugim wierzchołkiem. Innymi słowy, możemy określić stopień wierzchołka, obliczając liczbę krawędzi łączących się z tym wierzchołkiem. Stopień wierzchołka określa się za pomocą deg(v). Jeśli istnieje graf prosty, który zawiera n wierzchołków, to w tym przypadku stopień dowolnego wierzchołka będzie wynosił:

 Deg(v) = n-1 ∀ v ∈ G 

Wierzchołek może tworzyć krawędź ze wszystkimi innymi wierzchołkami grafu, z wyjątkiem samego wierzchołka. Zatem na prostym grafie stopień wierzchołka można określić na podstawie liczby wierzchołków na wykresie minus 1. Tutaj 1 jest używane jako wierzchołek własny, ponieważ sam w sobie nie tworzy pętli. Jeśli graf zawiera wierzchołki posiadające pętlę własną, to graf tego typu nie będzie grafem prostym.

Przykład:

W tym przykładzie mamy graf mający 6 wierzchołków, tj. a, b, c, d, e i f. Wierzchołek „a” ma stopień 5, a wszystkie pozostałe wierzchołki mają stopień 1. Jeśli jakikolwiek wierzchołek ma stopień 1, wówczas ten typ wierzchołka będzie nazywany „wierzchołkiem końcowym”.

In- Degree i Out-stopień w matematyce dyskretnej

Istnieją dwa przypadki grafów, w których możemy uwzględnić stopień wierzchołka, które opisano w następujący sposób:

  • Wykres nieskierowany
  • Kierowany wykres

Teraz poznamy szczegółowo stopień wierzchołka w grafie skierowanym i stopień wierzchołka w grafie nieskierowanym.

Stopień wierzchołka w grafie nieskierowanym

Jeżeli istnieje graf nieskierowany, to w grafie tego typu nie będzie krawędzi skierowanej. Przykłady określenia stopnia wierzchołka w grafie nieskierowanym opisano poniżej:

Przykład 1: W tym przykładzie rozważymy graf nieskierowany. Teraz dowiemy się, jaki jest stopień każdego wierzchołka na tym grafie.

In- Degree i Out-stopień w matematyce dyskretnej

Rozwiązanie: Na powyższym grafie nieskierowanym znajduje się łącznie 5 liczb wierzchołków, tj. a, b, c, d i e. Stopień każdego wierzchołka opisano w następujący sposób:

  • Powyższy graf zawiera 2 krawędzie, które spotykają się w wierzchołku „a”. Stąd Deg(a) = 2
  • Graf ten zawiera 3 krawędzie, które spotykają się w wierzchołku „b”. Stąd stopień(b) = 3
  • Powyższy graf zawiera 1 krawędź, która spotyka się w wierzchołku „c”. Stąd Deg(c) = 1. Wierzchołek c jest również znany jako wierzchołek wiszący.
  • Powyższy graf zawiera 2 krawędzie, które spotykają się w wierzchołku „d”. Stąd stopień(d) = 2.
  • Powyższy graf zawiera 0 krawędzi, które spotykają się w wierzchołku „e”. Stąd Deg(a) = 0. Wierzchołek e można również nazwać wierzchołkiem izolowanym.

Przykład 2: W tym przykładzie rozważymy graf nieskierowany. Teraz dowiemy się, jaki jest stopień każdego wierzchołka na tym grafie.

In- Degree i Out-stopień w matematyce dyskretnej

Rozwiązanie: Na powyższym grafie nieskierowanym znajduje się łącznie 5 liczb wierzchołków, tj. a, b, c, d i e. Stopień każdego wierzchołka opisano w następujący sposób:

Stopień wierzchołka a = stopień(a) = 2

Stopień wierzchołka b = stopień(b) = 2

Stopień wierzchołka c = stopień(c) = 2

Stopień wierzchołka d = deg(d) = 2

Stopień wierzchołka e = deg(e) = 0

Na tym grafie nie ma wierzchołka wiszącego, a wierzchołek „e” jest wierzchołkiem izolowanym.

Stopień wierzchołka w grafie skierowanym

Jeśli graf jest grafem skierowanym, to na tym wykresie każdy wierzchołek musi mieć stopień wejściowy i stopień wyjściowy. Załóżmy, że istnieje graf skierowany. Na tym wykresie możemy wykonać następujące kroki, aby określić stopień wejściowy, stopień wyjściowy i stopień wierzchołka.

Stopień wierzchołka

Stopień wierzchołka można opisać jako liczbę krawędzi za pomocą v, gdzie v służy do wskazania wierzchołka końcowego. Innymi słowy, możemy to opisać jako liczbę krawędzi dochodzących do wierzchołka. Za pomocą składni deg-(v) możemy zapisać stopień początkowy wierzchołka. Jeśli chcemy określić stopień wierzchołka, w tym celu musimy policzyć liczbę krawędzi kończących się na wierzchołku.

Stopień zewnętrzny wierzchołka

Stopień zewnętrzny wierzchołka można opisać jako liczbę krawędzi za pomocą v, gdzie v służy do wskazania początkowego wierzchołka. Innymi słowy, możemy to opisać jako liczbę krawędzi wychodzących z wierzchołka. Za pomocą składni deg+(v) możemy zapisać stopień zewnętrzny wierzchołka. Jeśli chcemy określić stopień zewnętrzny wierzchołka, musimy w tym celu policzyć liczbę krawędzi rozpoczynających się od wierzchołka.

Stopień wierzchołka

Stopień wierzchołka określa się za pomocą stopnia (v), który jest równy dodaniu stopnia wejściowego wierzchołka i stopnia zewnętrznego wierzchołka. Symboliczną reprezentację stopnia wierzchołka opisano w następujący sposób:

 Deg(v) = deg-(v) + deg+(v) 

Przykład 1: W tym przykładzie mamy graf i musimy określić stopień każdego wierzchołka.

In- Degree i Out-stopień w matematyce dyskretnej

Rozwiązanie: W tym celu najpierw ustalimy stopień wierzchołka, stopień początkowy wierzchołka, a następnie stopień zewnętrzny wierzchołka.

Jak widzimy, powyższy graf zawiera w sumie 6 wierzchołków, czyli v1, v2, v3, v4, v5 i v6.

Stopień:

Stopień początkowy wierzchołka v1 = stopień(v1) = 1

Stopień początkowy wierzchołka v2 = stopień(v2) = 1

Stopień początkowy wierzchołka v3 = stopień(v3) = 1

Stopień początkowy wierzchołka v4 = stopień(v4) = 5

Stopień początkowy wierzchołka v5 = stopień(v5) = 1

Stopień początkowy wierzchołka v6 = stopień(v6) = 0

Stopień wyjściowy:

Stopień zewnętrzny wierzchołka v1 = stopień(v1) = 2

Stopień zewnętrzny wierzchołka v2 = stopień(v2) = 3

Stopień zewnętrzny wierzchołka v3 = stopień(v3) = 2

Stopień zewnętrzny wierzchołka v4 = deg(v4) = 0

Stopień zewnętrzny wierzchołka v5 = stopień(v5) = 2

Stopień zewnętrzny wierzchołka v6 = stopień(v6) = 0

Stopień wierzchołka

Z definicji opisanej powyżej wiemy, że stopień wierzchołka Deg(v) = stopień-(v) + ty+(v). Teraz obliczymy to za pomocą następującego wzoru:

Stopień wierzchołka v1 = deg(v1) = 1+2 = 3

Stopień wierzchołka v2 = deg(v2) = 1+3 = 4

Stopień wierzchołka v3 = deg(v3) = 1+2 = 3

Stopień wierzchołka v4 = deg(v4) = 5+0 = 5

Stopień wierzchołka v5 = deg(v5) = 1+2 = 3

Stopień wierzchołka v6 = deg(v6) = 0+0 = 0

Przykład 2:

W tym przykładzie mamy graf skierowany z 7 wierzchołkami. Wierzchołek „a” zawiera 2 krawędzie, tj. „ad” i „ab”, które wychodzą na zewnątrz. Zatem wierzchołek „a” zawiera stopień wyjściowy, który wynosi 2. Podobnie wierzchołek „a” ma również krawędź „ga”, która zbliża się do wierzchołka „a”. Zatem wierzchołek „a” zawiera stopień in, który wynosi 1.

In- Degree i Out-stopień w matematyce dyskretnej

Rozwiązanie: Stopień wejściowy i wyjściowy wszystkich powyższych wierzchołków opisano w następujący sposób:

Stopień:

Stopień wierzchołka a = stopień(a) = 1

Stopień wierzchołka b = stopień(b) = 2

Stopień wierzchołka c = stopień (c) = 2

Stopień wierzchołka d = stopień (d) = 1

Stopień wierzchołka e = stopień (e) = 1

Stopień wierzchołka f = stopień(f) = 1

Stopień wierzchołka g = deg(g) = 0

Stopień wyjściowy:

Stopień zewnętrzny wierzchołka a = stopień(a) = 2

Stopień zewnętrzny wierzchołka b = stopień(b) = 0

Stopień zewnętrzny wierzchołka c = stopień (c) = 1

Stopień zewnętrzny wierzchołka d = deg(d) = 1

Stopień zewnętrzny wierzchołka e = deg(e) = 1

Stopień zewnętrzny wierzchołka f = stopień(f) = 1

Stopień zewnętrzny wierzchołka g = deg(g) = 2

Stopień każdego wierzchołka:

Wiemy, że stopień wierzchołka Deg(v) = stopień-(v) + ty+(v). Teraz obliczymy to za pomocą następującego wzoru:

Stopień wierzchołka a = deg(a) = 1+2 = 3

Stopień wierzchołka b = stopień(b) = 2+0 = 2

Stopień wierzchołka c = deg(c) = 2+1 = 3

Stopień wierzchołka d = deg(d) = 1+1 = 2

Stopień wierzchołka e = deg(e) = 1+1 = 2

Stopień wierzchołka f = deg(f) = 1+1 = 2

Stopień wierzchołka g = deg(g) = 0+2 = 2

Przykład 3: W tym przykładzie mamy graf skierowany z 5 wierzchołkami. Wierzchołek „a” zawiera 1 krawędź, tj. „ae”, które wychodzą na zewnątrz. Zatem wierzchołek „a” zawiera stopień wyjściowy, który wynosi 1. Podobnie wierzchołek „a” ma również krawędź „ba”, która zbliża się do wierzchołka „a”. Zatem wierzchołek „a” zawiera stopień in, który wynosi 1.

In- Degree i Out-stopień w matematyce dyskretnej

Rozwiązanie: Stopień wejściowy i wyjściowy wszystkich powyższych wierzchołków opisano w następujący sposób:

Stopień

Stopień wierzchołka a = stopień(a) = 1

Stopień wierzchołka b = stopień(b) = 0

Stopień wierzchołka c = stopień (c) = 2

Stopień wierzchołka d = stopień (d) = 1

Stopień wierzchołka e = stopień (e) = 1

Stopień wyjściowy:

Stopień zewnętrzny wierzchołka a = stopień(a) = 1

Stopień zewnętrzny wierzchołka b = stopień(b) = 2

Stopień zewnętrzny wierzchołka c = deg(c) = 0

Stopień zewnętrzny wierzchołka d = deg(d) = 1

Stopień zewnętrzny wierzchołka e = deg(e) = 1

Stopień każdego wierzchołka:

Wiemy, że stopień wierzchołka Deg(v) = stopień-(v) + ty+(v). Teraz obliczymy to za pomocą następującego wzoru:

Stopień wierzchołka a = deg(a) = 1+1 = 2

Stopień wierzchołka b = stopień(b) = 0+2 = 2

Stopień wierzchołka c = deg(c) = 2+0 = 2

Stopień wierzchołka d = deg(d) = 1+1 = 2

Stopień wierzchołka e = deg(e) = 1+1 = 2

Przykład 4: W tym przykładzie mamy graf i musimy określić stopień, stopień wejściowy i stopień wyjściowy każdego wierzchołka.

In- Degree i Out-stopień w matematyce dyskretnej

Rozwiązanie: W tym celu najpierw ustalimy stopień wejściowy wierzchołka, a następnie stopień wyjściowy wierzchołka.

Jak widzimy, powyższy graf zawiera w sumie 8 wierzchołków, czyli 0, 1, 2, 3, 4, 5 i 6.

Stopień:

Stopień wierzchołka 0 = stopień(0) = 1

Stopień wierzchołka 1 = stopień(1) = 2

Stopień wierzchołka 2 = stopień(2) = 2

Stopień wierzchołka 3 = stopień(3) = 2

Stopień wierzchołka 4 = stopień(4) = 2

Stopień wierzchołka 5 = stopień(5) = 2

indeks javy

Stopień wierzchołka 6 = stopień(6) = 2

Stopień wyjściowy:

Stopień zewnętrzny wierzchołka 0 = stopień(0) = 2

Stopień zewnętrzny wierzchołka 1 = stopień(1) = 1

Stopień zewnętrzny wierzchołka 2 = stopień(2) = 3

Stopień zewnętrzny wierzchołka 3 = stopień(3) = 2

Stopień zewnętrzny wierzchołka 4 = stopień(4) = 2

Stopień zewnętrzny wierzchołka 5 = stopień(5) = 2

Stopień zewnętrzny wierzchołka 6 = stopień(6) = 1

Stopień każdego wierzchołka:

Wiemy, że stopień wierzchołka Deg(v) = stopień-(v) + ty+(v). Teraz obliczymy to za pomocą następującego wzoru:

Stopień wierzchołka 0 = stopień(0) = 1+2 = 3

Stopień wierzchołka 1 = stopień(1) = 2+1 = 3

Stopień wierzchołka 2 = stopień(2) = 2+3 = 5

Stopień wierzchołka 3 = stopień(3) = 2+2 = 4

Stopień wierzchołka 4 = stopień(4) = 2+2 = 4

Stopień wierzchołka 5 = stopień(5) = 2+2 = 4

Stopień wierzchołka 6 = stopień(5) = 2+1 = 3

Sekwencja stopni wykresu

Aby określić kolejność stopni w grafie, musimy najpierw określić stopień każdego wierzchołka na wykresie. Następnie napiszemy te stopnie w kolejności rosnącej. Ten porządek/sekwencję można nazwać sekwencją stopni wykresu.

Na przykład: W tym przykładzie mamy trzy grafy mające 3, 4 i 5 wierzchołków, a kolejność stopni wszystkich grafów wynosi 3.

In- Degree i Out-stopień w matematyce dyskretnej

Na powyższym grafie znajdują się 3 wierzchołki. Stopień sekwencji tego grafu opisuje się następująco:

In- Degree i Out-stopień w matematyce dyskretnej

Na powyższym grafie znajdują się 4 wierzchołki. Sekwencja stopni tego wykresu jest opisana w następujący sposób:

In- Degree i Out-stopień w matematyce dyskretnej

Na powyższym grafie jest 5 wierzchołków. Sekwencja stopni tego wykresu jest opisana w następujący sposób: