För att förstå in- och utgraden av en vertex, måste vi först lära oss om begreppet grad av en vertex. Efter det kan vi enkelt förstå in- och utgraden av en vertex. Vi bör veta att in- och ut-graden endast kan bestämmas i den riktade grafen. Vi kan beräkna graden av ett vertex med hjälp av en oriktad graf. I den oriktade grafen kan vi inte beräkna in- och utgraden för en vertex.
Grad av ett vertex
Om vi vill hitta graden av varje vertex i en graf, i det här fallet, måste vi räkna antalet relationer som upprättas av en viss vertex med den andra vertexen. Med andra ord kan vi bestämma graden av ett vertex med hjälp av att beräkna antalet kanter som ansluter till det vertexet. Graden av ett vertex anges med hjälp av deg(v). Om det finns en enkel graf som innehåller n antal hörn, i det här fallet kommer graden av någon vertex att vara:
Deg(v) = n-1 ∀ v ∈ G
En vertex har förmågan att bilda en kant med alla andra hörn i en graf utom av sig själv. Så i en enkel graf kommer graden av en vertex att ta reda på genom antalet hörn i en graf minus 1. Här används 1 för självvertexen eftersom den inte gör en slinga av sig själv. Om grafen innehåller de hörn som har självslingan, kommer den typen av graf inte att vara en enkel graf.
Exempel:
I det här exemplet har vi en graf som har 6 hörn, dvs a, b, c, d, e och f. Hörnet 'a' har grad 5, och alla andra hörn har grad 1. Om någon vertex har grad 1, kommer den typen av vertex att kallas 'ändpunkten'.
Det finns två fall av grafer där vi kan överväga graden av en vertex, som beskrivs enligt följande:
- Oriktad graf
- Riktad graf
Nu ska vi lära oss graden av ett vertex i en riktad graf och graden av ett vertex i en oriktad graf i detalj.
Graden av en vertex i en oriktad graf
Om det finns en oriktad graf, kommer det inte att finnas någon riktad kant i denna typ av graf. Exemplen för att bestämma graden av ett vertex i en oriktad graf beskrivs enligt följande:
Exempel 1: I det här exemplet kommer vi att betrakta en oriktad graf. Nu ska vi ta reda på graden av varje vertex i den grafen.
Lösning: I den ovan oriktade grafen finns det totalt 5 antal hörn, d.v.s. a, b, c, d och e. Graden av varje vertex beskrivs enligt följande:
- Ovanstående graf innehåller 2 kanter, som möts vid vertex 'a'. Därför Deg(a) = 2
- Denna graf innehåller 3 kanter, som möts vid vertex 'b'. Därför Deg(b) = 3
- Grafen ovan innehåller 1 kant, som möts vid vertex 'c'. Därav Deg(c) = 1. Spetsen c är också känd som den hängande vertexen.
- Ovanstående graf innehåller 2 kanter, som möts vid vertex 'd'. Därför Deg(d) = 2.
- Ovanstående graf innehåller 0 kanter, som möts vid vertex 'e'. Därav Deg(a) = 0. Spetsen e kan också kallas den isolerade spetsen.
Exempel 2: I det här exemplet kommer vi att betrakta en oriktad graf. Nu ska vi ta reda på graden av varje vertex i den grafen.
Lösning: I ovanstående oriktade graf finns det totalt 5 antal hörn, d.v.s. a, b, c, d och e. Graden av varje vertex beskrivs enligt följande:
Grad av vertex a = deg(a) = 2
Grad av vertex b = deg(b) = 2
Grad av vertex c = deg(c) = 2
Grad av vertex d = deg(d) = 2
Grad av vertex e = deg(e) = 0
I den här grafen finns det ingen hängande vertex, och vertex 'e' är en isolerad vertex.
Grad av vertex i Riktad graf
Om grafen är en riktad graf, måste varje vertex i denna graf ha en in-grad och en ut-grad. Antag att det finns en riktad graf. I den här grafen kan vi använda följande steg för att ta reda på in-graden, ut-graden och graden av en vertex.
I grad av en vertex
In-graden av en vertex kan beskrivas som ett antal kanter med v, där v används för att indikera den terminala vertexen. Med andra ord kan vi beskriva det som ett antal kanter som kommer till vertexet. Med hjälp av syntax deg-(v), kan vi skriva in-graden av en vertex. Om vi vill bestämma in-graden av en vertex, för detta måste vi räkna antalet kanter som slutar vid vertex.
string.replaceall java
Ut-grad av en vertex
Ut-graden av en vertex kan beskrivas som ett antal kanter med v, där v används för att indikera den initiala vertexen. Med andra ord kan vi beskriva det som ett antal kanter som kommer ut från vertexet. Med hjälp av syntax deg+(v), vi kan skriva ut-graden av en vertex. Om vi vill bestämma ut-graden av en vertex, för detta måste vi räkna antalet kanter som börjar från vertex.
Grad av ett vertex
Graden av ett vertex anges med hjälp av deg(v), vilket är lika med tillägget av in-graden av en vertex och ut-graden av en vertex. Den symboliska representationen av graden av en vertex beskrivs på följande sätt:
Deg(v) = deg-(v) + deg+(v)
Exempel 1: I det här exemplet har vi en graf, och vi måste bestämma graden av varje vertex.
Lösning: För detta kommer vi först att ta reda på graden av en vertex, in-graden av en vertex och sedan ut-graden av en vertex.
Som vi kan se att grafen ovan innehåller de totalt 6 hörn, dvs v1, v2, v3, v4, v5 och v6.
I examen:
In-grad av en vertex v1 = deg(v1) = 1
In-grad av en vertex v2 = deg(v2) = 1
In-grad av en vertex v3 = deg(v3) = 1
In-grad av en vertex v4 = deg(v4) = 5
In-grad av en vertex v5 = deg(v5) = 1
In-grad av en vertex v6 = deg(v6) = 0
manuell testning
Utegrad:
Ut-grad av en vertex v1 = deg(v1) = 2
Ut-grad av en vertex v2 = deg(v2) = 3
Ut-grad av en vertex v3 = deg(v3) = 2
Ut-graden av en vertex v4 = deg(v4) = 0
Ut-grad av en vertex v5 = deg(v5) = 2
Ut-graden av en vertex v6 = deg(v6) = 0
Grad av ett vertex
Med hjälp av definitionen som beskrivs ovan vet vi att graden av en vertex Deg(v) = deg-(v) + du+(v). Nu kommer vi att beräkna det med hjälp av denna formel så här:
Grad av en vertex v1 = deg(v1) = 1+2 = 3
Grad av en vertex v2 = deg(v2) = 1+3 = 4
Grad av en vertex v3 = deg(v3) = 1+2 = 3
Grad av en vertex v4 = deg(v4) = 5+0 = 5
Grad av en vertex v5 = deg(v5) = 1+2 = 3
Grad av en vertex v6 = deg(v6) = 0+0 = 0
Exempel 2:
I det här exemplet har vi en riktad graf med 7 hörn. Spetsen 'a' innehåller 2 kanter, d.v.s. 'ad' och 'ab', som går utåt. Därför innehåller vertex 'a' ut-graden, vilket är 2. På samma sätt har vertex 'a' också en kant 'ga', som kommer mot denna vertex 'a'. Därför innehåller vertex 'a' in-graden, som är 1.
Lösning: In- och utgraden för alla ovanstående hörn beskrivs enligt följande:
I examen:
In-grad av en vertex a = deg(a) = 1
In-grad av en vertex b = deg(b) = 2
In-grad av en vertex c = deg(c) = 2
css-listor
In-grad av en vertex d = deg(d) = 1
In-grad av en vertex e = deg(e) = 1
In-grad av en vertex f = deg(f) = 1
In-grad av en vertex g = deg(g) = 0
Utegrad:
Ut-grad av en vertex a = deg(a) = 2
Ut-grad av en vertex b = deg(b) = 0
Ut-grad av en vertex c = deg(c) = 1
Ut-grad av en vertex d = deg(d) = 1
Ut-graden av en vertex e = deg(e) = 1
Ut-graden av en vertex f = deg(f) = 1
Ut-grad av en vertex g = deg(g) = 2
Grad av varje vertex:
Vi visste att graden av en vertex Deg(v) = deg-(v) + du+(v). Nu kommer vi att beräkna det med hjälp av denna formel så här:
Grad av ett vertex a = deg(a) = 1+2 = 3
Grad av en vertex b = deg(b) = 2+0 = 2
Graden av en vertex c = deg(c) = 2+1 = 3
Graden av en vertex d = deg(d) = 1+1 = 2
Graden av en vertex e = deg(e) = 1+1 = 2
Graden av en vertex f = deg(f) = 1+1 = 2
Graden av en vertex g = deg(g) = 0+2 = 2
Exempel 3: I det här exemplet har vi en riktad graf med 5 hörn. Spetsen 'a' innehåller 1 kant, d.v.s. 'ae', som går utåt. Därför innehåller vertex 'a' en ut-grad, som är 1. På samma sätt har vertex 'a' också en kant 'ba', som kommer mot denna vertex 'a'. Därför innehåller vertex 'a' in-graden, som är 1.
Lösning: In- och utgraden för alla ovanstående hörn beskrivs enligt följande:
I examen
In-grad av en vertex a = deg(a) = 1
In-grad av en vertex b = deg(b) = 0
sammanlänkningssträng i java
In-grad av en vertex c = deg(c) = 2
In-grad av en vertex d = deg(d) = 1
In-grad av en vertex e = deg(e) = 1
Utegrad:
Ut-grad av en vertex a = deg(a) = 1
Ut-grad av en vertex b = deg(b) = 2
Ut-graden av en vertex c = deg(c) = 0
Ut-grad av en vertex d = deg(d) = 1
Ut-graden av en vertex e = deg(e) = 1
Grad av varje vertex:
Vi visste att graden av en vertex Deg(v) = deg-(v) + du+(v). Nu kommer vi att beräkna det med hjälp av denna formel så här:
Graden av en vertex a = deg(a) = 1+1 = 2
Graden av en vertex b = deg(b) = 0+2 = 2
Graden av en vertex c = deg(c) = 2+0 = 2
Graden av en vertex d = deg(d) = 1+1 = 2
Graden av en vertex e = deg(e) = 1+1 = 2
Exempel 4: I det här exemplet har vi en graf, och vi måste bestämma graden, in-graden och ut-graden för varje vertex.
Lösning: För detta kommer vi först att ta reda på in-graden av en vertex och sedan ut-graden av en vertex.
Som vi kan se att grafen ovan innehåller de totala 8 hörn, dvs 0, 1, 2, 3, 4, 5 och 6.
I examen:
In-grad av en vertex 0 = deg(0) = 1
In-grad av en vertex 1 = deg(1) = 2
In-grad av en vertex 2 = deg(2) = 2
In-grad av en vertex 3 = deg(3) = 2
In-grad av en vertex 4 = deg(4) = 2
In-grad av en vertex 5 = deg(5) = 2
In-grad av en vertex 6 = deg(6) = 2
Utegrad:
Ut-graden av en vertex 0 = deg(0) = 2
Ut-grad av en vertex 1 = deg(1) = 1
Ut-graden av en vertex 2 = deg(2) = 3
Ut-grad av en vertex 3 = deg(3) = 2
Ut-grad av en vertex 4 = grader (4) = 2
Ut-grad av en vertex 5 = grader (5) = 2
Ut-grad av en vertex 6 = grader (6) = 1
sträng för att chatta
Grad av varje vertex:
Vi visste att graden av en vertex Deg(v) = deg-(v) + du+(v). Nu kommer vi att beräkna det med hjälp av denna formel så här:
Grad av en vertex 0 = deg(0) = 1+2 = 3
Grad av en vertex 1 = deg(1) = 2+1 = 3
Grad av en vertex 2 = deg(2) = 2+3 = 5
Grad av en vertex 3 = deg(3) = 2+2 = 4
Grad av en vertex 4 = deg(4) = 2+2 = 4
Grad av en vertex 5 = deg(5) = 2+2 = 4
Grad av en vertex 6 = deg(5) = 2+1 = 3
Gradföljd av en graf
För att bestämma gradsekvensen för en graf måste vi först bestämma graden av varje vertex i en graf. Efter det kommer vi att skriva dessa grader i stigande ordning. Denna ordning/sekvens kan kallas gradsekvensen för en graf.
Till exempel: I det här exemplet har vi tre grafer som har 3, 4 och 5 hörn, och gradsekvensen för alla grafer är 3.
I grafen ovan finns det 3 hörn. Graden av en sekvens av denna graf beskrivs enligt följande:
I grafen ovan finns det 4 hörn. Gradsekvensen för denna graf beskrivs enligt följande:
I grafen ovan finns det 5 hörn. Gradsekvensen för denna graf beskrivs enligt följande: