For å forstå inn- og utgraden til et toppunkt, må vi først lære om begrepet grad av et toppunkt. Etter det kan vi lett forstå inn- og ut-graden til et toppunkt. Vi bør vite at inn- og ut-graden bare kan bestemmes i den rettede grafen. Vi kan beregne graden av et toppunkt ved hjelp av en urettet graf. I den urettede grafen kan vi ikke beregne inn- og utgraden til et toppunkt.
Grad av et toppunkt
Hvis vi vil finne graden av hvert toppunkt i en graf, må vi i dette tilfellet telle antall relasjoner som er etablert av et bestemt toppunkt med det andre toppunktet. Med andre ord kan vi bestemme graden av et toppunkt ved hjelp av å beregne antall kanter som forbinder til det toppunktet. Graden av et toppunkt angis ved hjelp av deg(v). Hvis det er en enkel graf, som inneholder n antall toppunkter, i dette tilfellet vil graden av ethvert toppunkt være:
Deg(v) = n-1 ∀ v ∈ G
Et toppunkt har evnen til å danne en kant med alle andre toppunkter i en graf bortsett fra seg selv. Så i en enkel graf vil graden av et toppunkt finne ut av antall toppunkter i en graf minus 1. Her brukes 1 for selvvertexet fordi det ikke lager en løkke av seg selv. Hvis grafen inneholder toppunktene som har selvløkken, vil ikke den typen graf være en enkel graf.
Eksempel:
I dette eksemplet har vi en graf som har 6 toppunkter, dvs. a, b, c, d, e og f. Toppunktet 'a' har grad 5, og alle de andre toppunktene har grad 1. Hvis et toppunkt har grad 1, vil den typen toppunkt bli kjent som 'endetoppunktet'.
Det er to tilfeller av grafer der vi kan vurdere graden av et toppunkt, som er beskrevet som følger:
- Urettet graf
- Rettet graf
Nå skal vi lære graden av et toppunkt i en rettet graf og graden av et toppunkt i en urettet graf i detalj.
Grad av et toppunkt i en urettet graf
Hvis det er en urettet graf, vil det i denne typen grafer ikke være noen rettet kant. Eksemplene for å bestemme graden av et toppunkt i en urettet graf er beskrevet som følger:
Eksempel 1: I dette eksemplet vil vi vurdere en urettet graf. Nå skal vi finne ut graden av hvert toppunkt i den grafen.
Løsning: I den urettede grafen ovenfor er det totalt 5 antall hjørner, dvs. a, b, c, d og e. Graden av hvert toppunkt er beskrevet som følger:
- Grafen ovenfor inneholder 2 kanter som møtes ved toppunktet 'a'. Derfor Deg(a) = 2
- Denne grafen inneholder 3 kanter som møtes ved toppunktet 'b'. Derfor Deg(b) = 3
- Grafen ovenfor inneholder 1 kant, som møtes ved toppunktet 'c'. Derav Deg(c) = 1. Toppunktet c er også kjent som det hengende toppunktet.
- Grafen ovenfor inneholder 2 kanter som møtes ved toppunktet 'd'. Derfor Deg(d) = 2.
- Grafen ovenfor inneholder 0 kanter, som møtes ved toppunktet 'e'. Derav Deg(a) = 0. Toppunktet e kan også kalles det isolerte toppunktet.
Eksempel 2: I dette eksemplet vil vi vurdere en urettet graf. Nå skal vi finne ut graden av hvert toppunkt i den grafen.
Løsning: I den urettede grafen ovenfor er det totalt 5 antall hjørner, dvs. a, b, c, d og e. Graden av hvert toppunkt er beskrevet som følger:
Toppunktsgrad a = grader(a) = 2
Grad av toppunkt b = grader (b) = 2
Grad av toppunkt c = grader (c) = 2
Grad av toppunkt d = grader(d) = 2
Grad av toppunkt e = grader(e) = 0
I denne grafen er det ingen hengende toppunkt, og toppunktet 'e' er et isolert toppunkt.
Grad av toppunkt i rettet graf
Hvis grafen er en rettet graf, må hvert toppunkt i denne grafen ha en in-grad og ut-grad. Anta at det er en rettet graf. I denne grafen kan vi bruke de følgende trinnene for å finne ut i-grad, ut-grad og grad av et toppunkt.
I-grad av et toppunkt
In-graden til et toppunkt kan beskrives som et antall kanter med v, hvor v brukes for å indikere terminal toppunktet. Med andre ord kan vi beskrive det som en rekke kanter som kommer til toppunktet. Ved hjelp av syntaks deg-(v), kan vi skrive in-graden til et toppunkt. Hvis vi vil bestemme in-graden til et toppunkt, for dette, må vi telle antall kanter som ender ved toppunktet.
Ut-grad av et toppunkt
Ut-graden til et toppunkt kan beskrives som et antall kanter med v, der v brukes til å indikere startpunktet. Med andre ord kan vi beskrive det som en rekke kanter som kommer ut fra toppunktet. Ved hjelp av syntaks deg+(v), vi kan skrive ut-graden til et toppunkt. Hvis vi vil bestemme ut-graden til et toppunkt, for dette, må vi telle antall kanter som begynner fra toppunktet.
Grad av et toppunkt
Graden av et toppunkt angis ved hjelp av deg(v), som er lik addisjonen av inn-grad av et toppunkt og ut-grad av et toppunkt. Den symbolske representasjonen av graden av et toppunkt er beskrevet som følger:
Deg(v) = deg-(v) + deg+(v)
Eksempel 1: I dette eksemplet har vi en graf, og vi må bestemme graden av hvert toppunkt.
Løsning: For dette vil vi først finne ut graden av et toppunkt, i-graden av et toppunkt og deretter ut-graden til et toppunkt.
Som vi kan se at grafen ovenfor inneholder de totale 6 toppunktene, dvs. v1, v2, v3, v4, v5 og v6.
I grad:
In-grad av et toppunkt v1 = deg(v1) = 1
navn på by i usa
In-grad av et toppunkt v2 = deg(v2) = 1
In-grad av et toppunkt v3 = deg(v3) = 1
In-grad av et toppunkt v4 = deg(v4) = 5
In-grad av et toppunkt v5 = deg(v5) = 1
In-grad av et toppunkt v6 = deg(v6) = 0
Utegrad:
Ut-grad av et toppunkt v1 = deg(v1) = 2
Ut-grad av et toppunkt v2 = grader(v2) = 3
Ut-grad av et toppunkt v3 = grader(v3) = 2
Ut-grad av et toppunkt v4 = deg(v4) = 0
Ut-grad av et toppunkt v5 = grader(v5) = 2
Ut-grad av et toppunkt v6 = deg(v6) = 0
Grad av et toppunkt
Ved hjelp av definisjonen beskrevet ovenfor vet vi at graden av et toppunkt Deg(v) = deg-(v) + deg+(v). Nå vil vi beregne det ved hjelp av denne formelen slik:
Grad av et toppunkt v1 = deg(v1) = 1+2 = 3
Grad av et toppunkt v2 = grader(v2) = 1+3 = 4
Grad av et toppunkt v3 = deg(v3) = 1+2 = 3
Grad av et toppunkt v4 = deg(v4) = 5+0 = 5
Grad av et toppunkt v5 = deg(v5) = 1+2 = 3
Grad av et toppunkt v6 = deg(v6) = 0+0 = 0
Eksempel 2:
I dette eksemplet har vi en rettet graf med 7 hjørner. Toppunktet 'a' inneholder 2 kanter, dvs. 'ad' og 'ab', som går utover. Derfor inneholder toppunktet 'a' ut-graden, som er 2. På samme måte har toppunktet 'a' også en kant 'ga', som kommer mot dette toppunktet 'a'. Derfor inneholder toppunktet 'a' in-graden, som er 1.
Løsning: In-graden og out-graden for alle toppunktene ovenfor er beskrevet som følger:
I grad:
In-grad av et toppunkt a = deg(a) = 1
python-programmer
In-grad av et toppunkt b = deg(b) = 2
In-grad av et toppunkt c = deg(c) = 2
In-grad av et toppunkt d = deg(d) = 1
In-grad av et toppunkt e = deg(e) = 1
In-grad av et toppunkt f = deg(f) = 1
In-grad av et toppunkt g = deg(g) = 0
Utegrad:
Ut-grad av et toppunkt a = deg(a) = 2
Ut-grad av et toppunkt b = deg(b) = 0
Ut-grad av et toppunkt c = deg(c) = 1
Ut-grad av et toppunkt d = deg(d) = 1
Ut-grad av et toppunkt e = grader(e) = 1
Ut-grad av et toppunkt f = deg(f) = 1
Ut-grad av et toppunkt g = deg(g) = 2
Grad av hvert toppunkt:
Vi visste at graden av et toppunkt Deg(v) = deg-(v) + deg+(v). Nå vil vi beregne det ved hjelp av denne formelen slik:
Grad av et toppunkt a = deg(a) = 1+2 = 3
parallell behandling
Grad av et toppunkt b = deg(b) = 2+0 = 2
Grad av et toppunkt c = deg(c) = 2+1 = 3
Grad av et toppunkt d = deg(d) = 1+1 = 2
Grad av et toppunkt e = deg(e) = 1+1 = 2
Grad av et toppunkt f = deg(f) = 1+1 = 2
Grad av et toppunkt g = deg(g) = 0+2 = 2
Eksempel 3: I dette eksemplet har vi en rettet graf med 5 hjørner. Toppunktet 'a' inneholder 1 kant, dvs. 'ae', som går utover. Derfor inneholder toppunktet 'a' en ut-grad, som er 1. På samme måte har toppunktet 'a' også en kant 'ba', som kommer mot dette toppunktet 'a'. Derfor inneholder toppunktet 'a' in-graden, som er 1.
Løsning: In-graden og out-graden for alle toppunktene ovenfor er beskrevet som følger:
I grad
In-grad av et toppunkt a = deg(a) = 1
In-grad av et toppunkt b = deg(b) = 0
In-grad av et toppunkt c = deg(c) = 2
In-grad av et toppunkt d = deg(d) = 1
In-grad av et toppunkt e = deg(e) = 1
Utegrad:
Ut-grad av et toppunkt a = deg(a) = 1
Ut-grad av et toppunkt b = grader (b) = 2
Ut-grad av et toppunkt c = deg(c) = 0
Ut-grad av et toppunkt d = deg(d) = 1
Ut-grad av et toppunkt e = grader(e) = 1
Grad av hvert toppunkt:
Vi visste at graden av et toppunkt Deg(v) = deg-(v) + deg+(v). Nå vil vi beregne det ved hjelp av denne formelen slik:
Grad av et toppunkt a = deg(a) = 1+1 = 2
Grad av et toppunkt b = deg(b) = 0+2 = 2
Grad av et toppunkt c = deg(c) = 2+0 = 2
Grad av et toppunkt d = deg(d) = 1+1 = 2
Grad av et toppunkt e = deg(e) = 1+1 = 2
Eksempel 4: I dette eksemplet har vi en graf, og vi må bestemme graden, inn-graden og ut-graden for hvert toppunkt.
Løsning: For dette vil vi først finne ut i-graden til et toppunkt og deretter ut-graden til et toppunkt.
Som vi kan se at grafen ovenfor inneholder de totale 8 toppunktene, dvs. 0, 1, 2, 3, 4, 5 og 6.
I grad:
In-grad av et toppunkt 0 = deg(0) = 1
In-grad av et toppunkt 1 = deg(1) = 2
In-grad av et toppunkt 2 = deg(2) = 2
In-grad av et toppunkt 3 = deg(3) = 2
In-grad av et toppunkt 4 = deg(4) = 2
In-grad av et toppunkt 5 = deg(5) = 2
In-grad av et toppunkt 6 = grader(6) = 2
Utegrad:
Ut-grad av et toppunkt 0 = grader (0) = 2
Ut-grad av et toppunkt 1 = deg(1) = 1
Ut-grad av et toppunkt 2 = grader (2) = 3
blokkere YouTube-annonser på Android
Ut-grad av et toppunkt 3 = grader (3) = 2
Ut-grad av et toppunkt 4 = grader (4) = 2
Ut-grad av et toppunkt 5 = grader (5) = 2
Ut-grad av et toppunkt 6 = grader (6) = 1
Grad av hvert toppunkt:
Vi visste at graden av et toppunkt Deg(v) = deg-(v) + deg+(v). Nå vil vi beregne det ved hjelp av denne formelen slik:
Grad av et toppunkt 0 = deg(0) = 1+2 = 3
Grad av et toppunkt 1 = grader(1) = 2+1 = 3
Grad av et toppunkt 2 = grader(2) = 2+3 = 5
Grad av et toppunkt 3 = grader(3) = 2+2 = 4
Grad av et toppunkt 4 = grader(4) = 2+2 = 4
Grad av et toppunkt 5 = grader(5) = 2+2 = 4
Grad av et toppunkt 6 = grader(5) = 2+1 = 3
Gradsekvens av en graf
For å bestemme gradsekvensen til en graf, må vi først bestemme graden av hvert toppunkt i en graf. Etter det vil vi skrive disse gradene i stigende rekkefølge. Denne rekkefølgen/sekvensen kan kalles gradsekvensen til en graf.
For eksempel: I dette eksemplet har vi tre grafer som har 3, 4 og 5 toppunkter, og gradsekvensen til alle grafene er 3.
I grafen ovenfor er det 3 hjørner. Graden av en sekvens av denne grafen er beskrevet som følger:
I grafen ovenfor er det 4 hjørner. Gradsekvensen til denne grafen er beskrevet som følger:
I grafen ovenfor er det 5 hjørner. Gradsekvensen til denne grafen er beskrevet som følger: