For at forstå in-graden og ud-graden af ​​et toppunkt, skal vi først lære om begrebet grad af et toppunkt. Derefter kan vi nemt forstå in-graden og ud-graden af ​​et toppunkt. Vi bør vide, at in-graden og ud-graden kun kan bestemmes i den rettede graf. Vi kan beregne graden af ​​et toppunkt ved hjælp af en urettet graf. I den urettede graf kan vi ikke beregne in-graden og ud-graden af ​​et toppunkt.

Grad af et toppunkt

Hvis vi vil finde graden af ​​hvert knudepunkt i en graf, skal vi i dette tilfælde tælle antallet af relationer, der etableres af et bestemt knudepunkt med det andet knudepunkt. Med andre ord kan vi bestemme graden af ​​et toppunkt ved hjælp af at beregne antallet af kanter, der forbinder til det toppunkt. Graden af ​​et toppunkt angives ved hjælp af deg(v). Hvis der er en simpel graf, som indeholder n antal knudepunkter, vil graden af ​​ethvert knudepunkt i dette tilfælde være:

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

Et toppunkt har evnen til at danne en kant med alle andre toppunkter i en graf undtagen af ​​sig selv. Så i en simpel graf vil graden af ​​et toppunkt finde ud af antallet af toppunkter i en graf minus 1. Her bruges 1 til selvvertexet, fordi det ikke laver en løkke af sig selv. Hvis grafen indeholder de hjørner, som har selvløkken, så vil den type graf ikke være en simpel graf.

Eksempel:

I dette eksempel har vi en graf, der har 6 hjørner, dvs. a, b, c, d, e og f. Toppunktet 'a' har grad 5, og alle de andre toppunkter har grad 1. Hvis et toppunkt har grad 1, vil den type toppunkt blive kendt som 'endetoppunktet'.

Der er to tilfælde af grafer, hvor vi kan overveje graden af ​​et toppunkt, som er beskrevet som følger:

• Urettet graf
• Instrueret graf

Nu vil vi lære graden af ​​et toppunkt i en rettet graf og graden af ​​et toppunkt i en ikke-rettet graf i detaljer.

Graden af ​​et toppunkt i en urettet graf

Hvis der er en urettet graf, vil der i denne type graf ikke være nogen rettet kant. Eksemplerne til at bestemme graden af ​​et toppunkt i en urettet graf er beskrevet som følger:

Eksempel 1: I dette eksempel vil vi overveje en urettet graf. Nu vil vi finde ud af graden af ​​hvert toppunkt i den graf.

Løsning: I den ovenstående urettede graf er der i alt 5 antal knudepunkter, dvs. a, b, c, d og e. Graden af ​​hvert toppunkt er beskrevet som følger:

• Ovenstående graf indeholder 2 kanter, som mødes ved toppunktet 'a'. Derfor Deg(a) = 2
• Denne graf indeholder 3 kanter, som mødes ved toppunktet 'b'. Derfor Deg(b) = 3
• Ovenstående graf indeholder 1 kant, som mødes ved toppunktet 'c'. Derfor Deg(c) = 1. Toppunktet c er også kendt som det hængende toppunkt.
• Ovenstående graf indeholder 2 kanter, som mødes ved toppunktet 'd'. Derfor Deg(d) = 2.
• Ovenstående graf indeholder 0 kanter, som mødes ved toppunktet 'e'. Derfor Deg(a) = 0. Toppunktet e kan også kaldes det isolerede toppunkt.

Eksempel 2: I dette eksempel vil vi overveje en urettet graf. Nu vil vi finde ud af graden af ​​hvert toppunkt i den graf.

Løsning: I ovenstående urettede graf er der i alt 5 antal hjørner, dvs. a, b, c, d og e. Graden af ​​hvert toppunkt er beskrevet som følger:

Grad af toppunkt a = deg(a) = 2

Grad af toppunkt b = deg(b) = 2

Grad af toppunkt c = deg(c) = 2

Grad af toppunkt d = deg(d) = 2

Grad af toppunkt e = deg(e) = 0

I denne graf er der ingen hængende toppunkt, og toppunktet 'e' er et isoleret toppunkt.

Grad af toppunkt i rettet graf

Hvis grafen er en rettet graf, skal hvert hjørne i denne graf have en in-grad og ud-grad. Antag, at der er en rettet graf. I denne graf kan vi bruge følgende trin til at finde ud af in-graden, ud-graden og graden af ​​et toppunkt.

I-grad af et toppunkt

Et toppunkts in-grad kan beskrives som et antal kanter med v, hvor v bruges til at angive det terminale toppunkt. Med andre ord kan vi beskrive det som et antal kanter, der kommer til toppunktet. Ved hjælp af syntaks deg^-(v), kan vi skrive in-graden af ​​et toppunkt. Hvis vi vil bestemme in-graden af ​​et toppunkt, skal vi tælle antallet af kanter, der ender ved toppunktet.

Ud-grad af et toppunkt

Udgraden af ​​et toppunkt kan beskrives som et antal kanter med v, hvor v bruges til at angive startpunktet. Med andre ord kan vi beskrive det som et antal kanter, der kommer ud fra toppunktet. Ved hjælp af syntaks deg⁺(v), kan vi skrive ud-graden af ​​et toppunkt. Hvis vi vil bestemme ud-graden af ​​et toppunkt, skal vi tælle antallet af kanter, der begynder fra toppunktet.

Grad af et toppunkt

Graden af ​​et toppunkt angives ved hjælp af deg(v), som er lig med tilføjelsen af ​​in-grad af et toppunkt og ud-grad af et toppunkt. Den symbolske repræsentation af graden af ​​et toppunkt er beskrevet som følger:

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

Eksempel 1: I dette eksempel har vi en graf, og vi skal bestemme graden af ​​hvert toppunkt.

Løsning: Til dette vil vi først finde ud af graden af ​​et toppunkt, in-grad af et toppunkt og derefter ud-graden af ​​et toppunkt.

Som vi kan se, at ovenstående graf indeholder de i alt 6 toppunkter, dvs. v1, v2, v3, v4, v5 og v6.

I grad:

In-grad af et toppunkt v1 = deg(v1) = 1

navn by i usa

In-grad af et toppunkt v2 = deg(v2) = 1

In-grad af et toppunkt v3 = deg(v3) = 1

In-grad af et toppunkt v4 = deg(v4) = 5

In-grad af et toppunkt v5 = deg(v5) = 1

In-grad af et toppunkt v6 = deg(v6) = 0

Udegrad:

Ud-grad af et toppunkt v1 = deg(v1) = 2

Ud-grad af et toppunkt v2 = deg(v2) = 3

Ud-grad af et toppunkt v3 = deg(v3) = 2

Ud-grad af et toppunkt v4 = deg(v4) = 0

Ud-grad af et toppunkt v5 = deg(v5) = 2

Ud-grad af et toppunkt v6 = deg(v6) = 0

Grad af et toppunkt

Ved hjælp af definitionen beskrevet ovenfor ved vi, at graden af ​​et toppunkt Deg(v) = deg^-(v) + dig⁺(v). Nu vil vi beregne det ved hjælp af denne formel som denne:

Graden af ​​et toppunkt v1 = deg(v1) = 1+2 = 3

Grad af et toppunkt v2 = deg(v2) = 1+3 = 4

Grad af et toppunkt v3 = deg(v3) = 1+2 = 3

Grad af et toppunkt v4 = deg(v4) = 5+0 = 5

Grad af et toppunkt v5 = deg(v5) = 1+2 = 3

Grad af et toppunkt v6 = deg(v6) = 0+0 = 0

Eksempel 2:

I dette eksempel har vi en rettet graf med 7 hjørner. Toppunktet 'a' indeholder 2 kanter, dvs. 'ad' og 'ab', som går udad. Derfor indeholder toppunktet 'a' ud-graden, som er 2. På samme måde har toppunktet 'a' også en kant 'ga', som kommer mod dette toppunkt 'a'. Derfor indeholder toppunktet 'a' in-graden, som er 1.

Løsning: In-graden og ud-graden af ​​alle ovenstående hjørner er beskrevet som følger:

I grad:

In-grad af et toppunkt a = deg(a) = 1

python programmer

In-grad af et toppunkt b = deg(b) = 2

In-grad af et toppunkt c = deg(c) = 2

In-grad af et toppunkt d = deg(d) = 1

In-grad af et toppunkt e = deg(e) = 1

In-grad af et toppunkt f = deg(f) = 1

In-grad af et toppunkt g = deg(g) = 0

Udegrad:

Ud-grad af et toppunkt a = deg(a) = 2

Ud-grad af et toppunkt b = deg(b) = 0

Ud-grad af et toppunkt c = deg(c) = 1

Ud-grad af et toppunkt d = deg(d) = 1

Ud-grad af et toppunkt e = deg(e) = 1

Ud-grad af et toppunkt f = deg(f) = 1

Ud-grad af et toppunkt g = deg(g) = 2

Grad af hvert toppunkt:

Vi vidste, at graden af ​​et toppunkt Deg(v) = deg^-(v) + dig⁺(v). Nu vil vi beregne det ved hjælp af denne formel som denne:

Grad af et toppunkt a = deg(a) = 1+2 = 3

parallel bearbejdning

Grad af et toppunkt b = deg(b) = 2+0 = 2

Grad af et toppunkt c = deg(c) = 2+1 = 3

Grad af et toppunkt d = deg(d) = 1+1 = 2

Grad af et toppunkt e = deg(e) = 1+1 = 2

Graden af ​​et toppunkt f = deg(f) = 1+1 = 2

Grad af et toppunkt g = deg(g) = 0+2 = 2

Eksempel 3: I dette eksempel har vi en rettet graf med 5 hjørner. Toppunktet 'a' indeholder 1 kant, dvs. 'ae', som går udad. Derfor indeholder toppunktet 'a' en ud-grad, som er 1. På samme måde har toppunktet 'a' også en kant 'ba', som kommer mod dette toppunkt 'a'. Derfor indeholder toppunktet 'a' in-graden, som er 1.

Løsning: In-graden og out-graden af ​​alle ovenstående hjørner er beskrevet som følger:

I grad

In-grad af et toppunkt a = deg(a) = 1

In-grad af et toppunkt b = deg(b) = 0

In-grad af et toppunkt c = deg(c) = 2

In-grad af et toppunkt d = deg(d) = 1

In-grad af et toppunkt e = deg(e) = 1

Udegrad:

Ud-grad af et toppunkt a = deg(a) = 1

Ud-grad af et toppunkt b = deg(b) = 2

Ud-grad af et toppunkt c = deg(c) = 0

Ud-grad af et toppunkt d = deg(d) = 1

Ud-grad af et toppunkt e = deg(e) = 1

Grad af hvert toppunkt:

Vi vidste, at graden af ​​et toppunkt Deg(v) = deg^-(v) + dig⁺(v). Nu vil vi beregne det ved hjælp af denne formel som denne:

Grad af et toppunkt a = deg(a) = 1+1 = 2

Grad af et toppunkt b = deg(b) = 0+2 = 2

Graden af ​​et toppunkt c = deg(c) = 2+0 = 2

Grad af et toppunkt d = deg(d) = 1+1 = 2

Grad af et toppunkt e = deg(e) = 1+1 = 2

Eksempel 4: I dette eksempel har vi en graf, og vi skal bestemme graden, in-graden og ud-graden af ​​hvert toppunkt.

Løsning: Til dette vil vi først finde ud af in-graden af ​​et toppunkt og derefter ud-graden af ​​et toppunkt.

Som vi kan se, at ovenstående graf indeholder de samlede 8 toppunkter, dvs. 0, 1, 2, 3, 4, 5 og 6.

I grad:

In-grad af et toppunkt 0 = deg(0) = 1

In-grad af et toppunkt 1 = deg(1) = 2

In-grad af et toppunkt 2 = deg(2) = 2

In-grad af et toppunkt 3 = grader(3) = 2

In-grad af et toppunkt 4 = deg(4) = 2

In-grad af et toppunkt 5 = deg(5) = 2

In-grad af et toppunkt 6 = grader(6) = 2

Udegrad:

Ud-grad af et toppunkt 0 = deg(0) = 2

Ud-grad af et toppunkt 1 = deg(1) = 1

Ud-grad af et toppunkt 2 = deg(2) = 3

arraylist i java sortering

Ud-grad af et toppunkt 3 = grader(3) = 2

Ud-grad af et toppunkt 4 = grader(4) = 2

Ud-grad af et toppunkt 5 = grader(5) = 2

Ud-grad af et toppunkt 6 = grader(6) = 1

Grad af hvert toppunkt:

Vi vidste, at graden af ​​et toppunkt Deg(v) = deg^-(v) + dig⁺(v). Nu vil vi beregne det ved hjælp af denne formel som denne:

Grad af et toppunkt 0 = deg(0) = 1+2 = 3

Grad af et toppunkt 1 = deg(1) = 2+1 = 3

Graden af ​​et toppunkt 2 = grader(2) = 2+3 = 5

Grad af et toppunkt 3 = grader(3) = 2+2 = 4

Grad af et toppunkt 4 = grader(4) = 2+2 = 4

Grad af et toppunkt 5 = grader(5) = 2+2 = 4

Grad af et toppunkt 6 = grader(5) = 2+1 = 3

Gradrækkefølge af en graf

For at bestemme gradsekvensen af ​​en graf, skal vi først bestemme graden af ​​hvert toppunkt i en graf. Derefter vil vi skrive disse grader i stigende rækkefølge. Denne rækkefølge/sekvens kan kaldes gradsekvensen af ​​en graf.

For eksempel: I dette eksempel har vi tre grafer, der har 3, 4 og 5 toppunkter, og gradsekvensen for alle graferne er 3.

I ovenstående graf er der 3 hjørner. Graden af ​​en sekvens af denne graf er beskrevet som følger:

I ovenstående graf er der 4 hjørner. Gradsekvensen af ​​denne graf er beskrevet som følger:

I ovenstående graf er der 5 hjørner. Gradsekvensen af ​​denne graf er beskrevet som følger: