Aby sme porozumeli in-stupeň a out-stupeň vrcholu, musíme sa najprv naučiť o koncepte stupňa vrcholu. Potom môžeme ľahko porozumieť in-stupňu a out-stupeň vrcholu. Mali by sme vedieť, že in-stupeň a out-stupeň možno určiť iba v orientovanom grafe. Stupeň vrcholu vieme vypočítať pomocou neorientovaného grafu. V neorientovanom grafe nemôžeme vypočítať in-stupeň a out-stupeň vrcholu.
Stupeň vrcholu
Ak chceme nájsť stupeň každého vrcholu v grafe, v tomto prípade musíme spočítať počet vzťahov, ktoré sú vytvorené konkrétnym vrcholom s druhým vrcholom. Inými slovami, môžeme určiť stupeň vrcholu pomocou výpočtu počtu hrán spájajúcich sa s týmto vrcholom. Stupeň vrcholu je označený pomocou deg(v). Ak existuje jednoduchý graf, ktorý obsahuje n počet vrcholov, v tomto prípade bude stupeň ktoréhokoľvek vrcholu:
Deg(v) = n-1 ∀ v ∈ G
Vrchol má schopnosť tvoriť hranu so všetkými ostatnými vrcholmi v grafe okrem seba. Takže v jednoduchom grafe sa stupeň vrcholu zistí počtom vrcholov v grafe mínus 1. Tu sa 1 používa pre vrchol self, pretože sám o sebe nerobí slučku. Ak graf obsahuje vrcholy, ktoré majú vlastnú slučku, potom tento typ grafu nebude jednoduchým grafom.
Príklad:
V tomto príklade máme graf, ktorý má 6 vrcholov, t.j. a, b, c, d, e a f. Vrchol 'a' má stupeň 5 a všetky ostatné vrcholy majú stupeň 1. Ak má niektorý vrchol stupeň 1, potom bude tento typ vrcholu známy ako 'koncový vrchol'.
Existujú dva prípady grafov, v ktorých môžeme zvážiť stupeň vrcholu, ktoré sú opísané nasledovne:
- Neorientovaný graf
- Orientovaný graf
Teraz sa podrobne naučíme stupeň vrcholu v orientovanom grafe a stupeň vrcholu v neorientovanom grafe.
Stupeň vrcholu v neorientovanom grafe
Ak existuje neorientovaný graf, potom v tomto type grafu nebude žiadna orientovaná hrana. Príklady na určenie stupňa vrcholu v neorientovanom grafe sú opísané nasledovne:
Príklad 1: V tomto príklade budeme uvažovať o neorientovanom grafe. Teraz zistíme stupeň každého vrcholu v tomto grafe.
Riešenie: Vo vyššie uvedenom neorientovanom grafe je celkovo 5 čísel vrcholov, t.j. a, b, c, d a e. Stupeň každého vrcholu je opísaný takto:
- Vyššie uvedený graf obsahuje 2 hrany, ktoré sa stretávajú vo vrchole 'a'. Preto stupeň (a) = 2
- Tento graf obsahuje 3 hrany, ktoré sa stretávajú vo vrchole 'b'. Preto Deg(b) = 3
- Vyššie uvedený graf obsahuje 1 hranu, ktorá sa stretáva vo vrchole 'c'. Preto Deg(c) = 1. Vrchol c je známy aj ako závesný vrchol.
- Vyššie uvedený graf obsahuje 2 hrany, ktoré sa stretávajú vo vrchole 'd'. Preto stupeň (d) = 2.
- Vyššie uvedený graf obsahuje 0 hrán, ktoré sa stretávajú vo vrchole 'e'. Preto Deg(a) = 0. Vrchol e možno nazvať aj izolovaným vrcholom.
Príklad 2: V tomto príklade budeme uvažovať o neorientovanom grafe. Teraz zistíme stupeň každého vrcholu v tomto grafe.
Riešenie: Vo vyššie uvedenom neorientovanom grafe je celkovo 5 čísel vrcholov, t.j. a, b, c, d a e. Stupeň každého vrcholu je opísaný takto:
Stupeň vrcholu a = stupeň (a) = 2
Stupeň vrcholu b = deg(b) = 2
Stupeň vrcholu c = deg(c) = 2
Stupeň vrcholu d = deg(d) = 2
Stupeň vrcholu e = deg(e) = 0
V tomto grafe nie je žiadny závesný vrchol a vrchol 'e' je izolovaný vrchol.
Stupeň vrcholu v orientovanom grafe
Ak je graf orientovaný, potom v tomto grafe musí mať každý vrchol in-stupeň a vonkajší stupeň. Predpokladajme, že existuje orientovaný graf. V tomto grafe môžeme pomocou nasledujúcich krokov zistiť in-stupeň, mimostupeň a stupeň vrcholu.
V stupni vrcholu
In-stupeň vrcholu môže byť opísaný ako počet hrán s v, kde v sa používa na označenie terminálneho vrcholu. Inými slovami, môžeme to opísať ako množstvo hrán prichádzajúcich do vrcholu. Pomocou syntaxe deg-(v), môžeme napísať stupeň vrcholu. Ak chceme určiť stupeň vrcholu, musíme spočítať počet hrán, ktoré končia vo vrchole.
Mimo stupňa vrcholu
Výškový stupeň vrcholu možno opísať ako počet hrán s v, kde v sa používa na označenie počiatočného vrcholu. Inými slovami, môžeme to opísať ako množstvo hrán vychádzajúcich z vrcholu. Pomocou syntaxe deg+(v), môžeme napísať vonkajší stupeň vrcholu. Ak chceme určiť vonkajší stupeň vrcholu, musíme spočítať počet hrán, ktoré začínajú od vrcholu.
Stupeň vrcholu
Stupeň vrcholu je označený pomocou stupňa (v), ktorý sa rovná súčtu stupňa vrcholu a vonkajšieho stupňa vrcholu. Symbolická reprezentácia stupňa vrcholu je opísaná takto:
Deg(v) = deg-(v) + deg+(v)
Príklad 1: V tomto príklade máme graf a musíme určiť stupeň každého vrcholu.
Riešenie: Najprv zistíme stupeň vrcholu, stupeň vrcholu a potom vonkajší stupeň vrcholu.
Ako vidíme, vyššie uvedený graf obsahuje celkovo 6 vrcholov, t.j. v1, v2, v3, v4, v5 a v6.
In-stupeň:
In-stupeň vrcholu v1 = stupeň(v1) = 1
In-stupeň vrcholu v2 = stupeň(v2) = 1
In-stupeň vrcholu v3 = stupeň(v3) = 1
In-stupeň vrcholu v4 = stupeň(v4) = 5
In-stupeň vrcholu v5 = stupeň(v5) = 1
In-stupeň vrcholu v6 = stupeň(v6) = 0
Mimo stupeň:
Mimo stupeň vrcholu v1 = stupeň (v1) = 2
Mimo stupňa vrcholu v2 = stupeň (v2) = 3
Mimo stupňa vrcholu v3 = stupeň(v3) = 2
Mimostupeň vrcholu v4 = stupeň(v4) = 0
Mimo stupňa vrcholu v5 = stupeň(v5) = 2
Mimostupeň vrcholu v6 = stupeň(v6) = 0
Stupeň vrcholu
Pomocou vyššie opísanej definície vieme, že stupeň vrcholu Deg(v) = deg-(v) + vy+(v). Teraz to vypočítame pomocou tohto vzorca:
Stupeň vrcholu v1 = stupeň(v1) = 1+2 = 3
Stupeň vrcholu v2 = stupeň(v2) = 1+3 = 4
Stupeň vrcholu v3 = stupeň(v3) = 1+2 = 3
Stupeň vrcholu v4 = stupeň(v4) = 5+0 = 5
Stupeň vrcholu v5 = stupeň(v5) = 1+2 = 3
Stupeň vrcholu v6 = deg(v6) = 0+0 = 0
Príklad 2:
V tomto príklade máme orientovaný graf so 7 vrcholmi. Vrchol „a“ obsahuje 2 hrany, t.j. „ad“ a „ab“, ktoré smerujú von. Preto vrchol 'a' obsahuje vonkajší stupeň, ktorý je 2. Podobne aj vrchol 'a' má hranu 'ga', ktorá smeruje k tomuto vrcholu 'a'. Preto vrchol „a“ obsahuje stupeň, ktorý je 1.
Riešenie: In-stupeň a out-stupeň všetkých vyššie uvedených vrcholov sú opísané nasledovne:
In-stupeň:
In-stupeň vrcholu a = stupeň (a) = 1
In-stupeň vrcholu b = stupeň (b) = 2
In-stupeň vrcholu c = stupeň (c) = 2
In-stupeň vrcholu d = stupeň (d) = 1
In-stupeň vrcholu e = stupeň (e) = 1
In-stupeň vrcholu f = stupeň (f) = 1
In-stupeň vrcholu g = stupeň (g) = 0
Mimo stupeň:
Mimo stupňa vrcholu a = stupeň (a) = 2
Mimo stupňa vrcholu b = stupeň (b) = 0
Mimo stupňa vrcholu c = stupeň (c) = 1
Mimo stupeň vrcholu d = stupeň (d) = 1
Mimo stupňa vrcholu e = stupeň (e) = 1
Mimo stupeň vrcholu f = stupeň (f) = 1
Mierny stupeň vrcholu g = stupeň (g) = 2
Stupeň každého vrcholu:
Vieme, že stupeň vrcholu Deg(v) = stupeň-(v) + vy+(v). Teraz to vypočítame pomocou tohto vzorca:
Stupeň vrcholu a = stupeň(a) = 1+2 = 3
Stupeň vrcholu b = stupeň(b) = 2+0 = 2
Stupeň vrcholu c = stupeň (c) = 2+1 = 3
Stupeň vrcholu d = stupeň (d) = 1+1 = 2
Stupeň vrcholu e = stupeň(e) = 1+1 = 2
Stupeň vrcholu f = deg(f) = 1+1 = 2
Stupeň vrcholu g = stupeň (g) = 0+2 = 2
Príklad 3: V tomto príklade máme orientovaný graf s 5 vrcholmi. Vrchol 'a' obsahuje 1 hranu, t.j. 'ae', ktoré smerujú von. Preto vrchol 'a' obsahuje vonkajší stupeň, ktorý je 1. Podobne aj vrchol 'a' má hranu 'ba', ktorá smeruje k tomuto vrcholu 'a'. Preto vrchol „a“ obsahuje stupeň, ktorý je 1.
Riešenie: In-stupeň a out-stupeň všetkých vyššie uvedených vrcholov sú opísané nasledovne:
In-stupeň
In-stupeň vrcholu a = stupeň (a) = 1
In-stupeň vrcholu b = stupeň (b) = 0
In-stupeň vrcholu c = stupeň (c) = 2
In-stupeň vrcholu d = stupeň (d) = 1
In-stupeň vrcholu e = stupeň (e) = 1
Mimo stupeň:
Mimo stupeň vrcholu a = stupeň (a) = 1
Mimo stupňa vrcholu b = stupeň (b) = 2
Mimostupeň vrcholu c = stupeň (c) = 0
Mimo stupeň vrcholu d = stupeň (d) = 1
Mimo stupňa vrcholu e = stupeň (e) = 1
Stupeň každého vrcholu:
Vieme, že stupeň vrcholu Deg(v) = stupeň-(v) + vy+(v). Teraz to vypočítame pomocou tohto vzorca:
Stupeň vrcholu a = stupeň(a) = 1+1 = 2
Stupeň vrcholu b = stupeň(b) = 0+2 = 2
Stupeň vrcholu c = deg(c) = 2+0 = 2
Stupeň vrcholu d = stupeň (d) = 1+1 = 2
Stupeň vrcholu e = stupeň(e) = 1+1 = 2
Príklad 4: V tomto príklade máme graf a musíme určiť stupeň, stupeň a mimostupeň každého vrcholu.
Riešenie: Na tento účel najprv zistíme vnútorný stupeň vrcholu a potom vonkajší stupeň vrcholu.
Ako vidíme, vyššie uvedený graf obsahuje celkovo 8 vrcholov, t.j. 0, 1, 2, 3, 4, 5 a 6.
In-stupeň:
In-stupeň vrcholu 0 = stupeň(0) = 1
In-stupeň vrcholu 1 = stupeň(1) = 2
In-stupeň vrcholu 2 = stupeň(2) = 2
In-stupeň vrcholu 3 = stupeň(3) = 2
In-stupeň vrcholu 4 = stupeň(4) = 2
In-stupeň vrcholu 5 = stupeň(5) = 2
In-stupeň vrcholu 6 = stupeň(6) = 2
Mimo stupeň:
Mimostupeň vrcholu 0 = stupeň (0) = 2
Mimo stupňa vrcholu 1 = stupeň (1) = 1
Mimo stupňa vrcholu 2 = stupeň (2) = 3
Mimo stupňa vrcholu 3 = stupeň(3) = 2
Mimo stupňa vrcholu 4 = stupeň (4) = 2
Mimo stupňa vrcholu 5 = stupeň (5) = 2
Mimo stupňa vrcholu 6 = stupeň (6) = 1
Stupeň každého vrcholu:
Vieme, že stupeň vrcholu Deg(v) = stupeň-(v) + vy+(v). Teraz to vypočítame pomocou tohto vzorca:
Stupeň vrcholu 0 = stupeň(0) = 1+2 = 3
Stupeň vrcholu 1 = stupeň(1) = 2+1 = 3
siete a typy
Stupeň vrcholu 2 = stupeň(2) = 2+3 = 5
Stupeň vrcholu 3 = stupeň(3) = 2+2 = 4
Stupeň vrcholu 4 = stupeň(4) = 2+2 = 4
Stupeň vrcholu 5 = stupeň(5) = 2+2 = 4
Stupeň vrcholu 6 = stupeň(5) = 2+1 = 3
Postupnosť stupňov grafu
Aby sme určili stupňovú postupnosť grafu, musíme najprv určiť stupeň každého vrcholu v grafe. Potom tieto stupne zapíšeme vo vzostupnom poradí. Toto poradie/sekvencia sa dá nazvať stupňovitá postupnosť grafu.
Napríklad: V tomto príklade máme tri grafy, ktoré majú 3, 4 a 5 vrcholov a postupnosť stupňov všetkých grafov je 3.
Vo vyššie uvedenom grafe sú 3 vrcholy. Stupeň postupnosti tohto grafu je opísaný takto:
Vo vyššie uvedenom grafe sú 4 vrcholy. Postupnosť stupňov tohto grafu je opísaná takto:
Vo vyššie uvedenom grafe je 5 vrcholov. Postupnosť stupňov tohto grafu je opísaná takto: