Da bi razumeli notranjo in izhodno stopnjo oglišča, se moramo najprej seznaniti s konceptom stopnje oglišča. Po tem lahko zlahka razumemo notranjo in izhodno stopnjo vozlišča. Vedeti moramo, da lahko notranjo in izhodno stopnjo določimo le v usmerjenem grafu. S pomočjo neusmerjenega grafa lahko izračunamo stopnjo vozlišča. V neusmerjenem grafu ne moremo izračunati notranje in zunanje stopnje vozlišča.
Stopnja vrha
Če želimo najti stopnjo posameznega vozlišča v grafu, moramo v tem primeru prešteti število relacij, ki jih določeno vozlišče vzpostavi z drugim vozliščem. Z drugimi besedami, lahko določimo stopnjo oglišča s pomočjo izračuna števila robov, ki se povezujejo s tem ogliščem. Stopnja oglišča je označena s pomočjo deg(v). Če obstaja preprost graf, ki vsebuje n število vozlišč, bo v tem primeru stopnja katerega koli vozlišča:
Deg(v) = n-1 ∀ v ∈ G
Vozlišče lahko tvori rob z vsemi drugimi vozlišči v grafu, razen s samim seboj. V preprostem grafu bo torej stopnja vozlišča ugotovljena s številom vozlišč v grafu minus 1. Tukaj se 1 uporablja za samo vozlišče, ker samo po sebi ne naredi zanke. Če graf vsebuje vozlišča, ki imajo samozanko, potem ta vrsta grafa ne bo preprost graf.
primer:
java break
V tem primeru imamo graf, ki ima 6 vozlišč, tj. a, b, c, d, e in f. Oglišče 'a' ima stopnjo 5, vsa druga oglišča pa stopnjo 1. Če ima katero koli oglišče stopnjo 1, bo ta tip oglišča znan kot 'končno oglišče'.
Obstajata dva primera grafov, v katerih lahko upoštevamo stopnjo vozlišča, ki sta opisana na naslednji način:
- Neusmerjeni graf
- Usmerjeni graf
Zdaj bomo podrobneje spoznali stopnjo vozlišča v usmerjenem grafu in stopnjo vozlišča v neusmerjenem grafu.
Stopnja vozlišča v neusmerjenem grafu
Če obstaja neusmerjen graf, potem v tej vrsti grafa ne bo usmerjenega roba. Primeri za določanje stopnje vozlišča v neusmerjenem grafu so opisani takole:
Primer 1: V tem primeru bomo obravnavali neusmerjeni graf. Zdaj bomo ugotovili stopnjo vsakega vozlišča v tem grafu.
rešitev: V zgornjem neusmerjenem grafu je skupaj 5 števil vozlišč, tj. a, b, c, d in e. Stopnja vsakega vozlišča je opisana na naslednji način:
- Zgornji graf vsebuje 2 roba, ki se srečata v točki 'a'. Zato je Deg(a) = 2
- Ta graf vsebuje 3 robove, ki se srečajo v točki 'b'. Zato je Deg(b) = 3
- Zgornji graf vsebuje 1 rob, ki se srečata v točki 'c'. Zato je Deg(c) = 1. Oglišče c je znano tudi kot viseče oglišče.
- Zgornji graf vsebuje 2 roba, ki se srečata v točki 'd'. Zato je Deg(d) = 2.
- Zgornji graf vsebuje 0 robov, ki se srečajo v točki 'e'. Zato je Deg(a) = 0. Oglišče e lahko imenujemo tudi izolirano oglišče.
Primer 2: V tem primeru bomo obravnavali neusmerjeni graf. Zdaj bomo ugotovili stopnjo vsakega vozlišča v tem grafu.
rešitev: V zgornjem neusmerjenem grafu je skupaj 5 števil vozlišč, tj. a, b, c, d in e. Stopnja vsakega vozlišča je opisana na naslednji način:
Stopnja oglišča a = deg(a) = 2
Stopnja oglišča b = deg(b) = 2
Stopnja oglišča c = deg(c) = 2
Stopnja oglišča d = deg(d) = 2
Stopnja oglišča e = deg(e) = 0
V tem grafu ni visečega oglišča in oglišče 'e' je izolirano oglišče.
Stopnja oglišča v usmerjenem grafu
Če je graf usmerjen graf, mora imeti v tem grafu vsako vozlišče notranjo in izhodno stopnjo. Recimo, da obstaja usmerjen graf. V tem grafu lahko uporabimo naslednje korake, da ugotovimo notranjo, izhodno stopnjo in stopnjo vozlišča.
In-stopnja vrha
In-stopnjo oglišča lahko opišemo kot število robov z v, kjer se v uporablja za označevanje končne oglišča. Z drugimi besedami, lahko ga opišemo kot več robov, ki prihajajo do vrha. S pomočjo sintakse deg-(v), lahko zapišemo in-stopnjo vozlišča. Če želimo določiti in-stopnjo oglišča, moramo za to prešteti število robov, ki se končajo na oglišču.
Zunanja stopnja oglišča
Zunanjo stopnjo oglišča lahko opišemo kot število robov z v, kjer se v uporablja za označevanje začetne oglišča. Z drugimi besedami, lahko ga opišemo kot več robov, ki izhajajo iz vrha. S pomočjo sintakse deg+(v), lahko zapišemo izhodno stopnjo vozlišča. Če želimo določiti izhodno stopnjo oglišča, moramo za to prešteti število robov, ki se začnejo iz oglišča.
Stopnja vrha
Stopnja oglišča je označena s pomočjo deg(v), ki je enaka seštevku in-stopnje oglišča in izhodne stopnje oglišča. Simbolna predstavitev stopnje oglišča je opisana takole:
Deg(v) = deg-(v) + deg+(v)
Primer 1: V tem primeru imamo graf in določiti moramo stopnjo vsakega vozlišča.
rešitev: Za to bomo najprej ugotovili stopnjo oglišča, notranjo stopnjo oglišča in nato izhodno stopnjo oglišča.
Kot lahko vidimo, zgornji graf vsebuje skupno 6 vozlišč, tj. v1, v2, v3, v4, v5 in v6.
V stopnji:
In-stopnja oglišča v1 = deg(v1) = 1
In-stopnja oglišča v2 = deg(v2) = 1
In-stopnja vozlišča v3 = deg(v3) = 1
In-stopnja oglišča v4 = deg(v4) = 5
In-stopnja oglišča v5 = deg(v5) = 1
In-stopnja vozlišča v6 = deg(v6) = 0
Izvenstopnja:
Zunanja stopnja oglišča v1 = deg(v1) = 2
Zunanja stopnja oglišča v2 = deg(v2) = 3
Zunanja stopnja oglišča v3 = deg(v3) = 2
Zunanja stopnja oglišča v4 = deg(v4) = 0
Zunanja stopnja oglišča v5 = deg(v5) = 2
Zunanja stopnja oglišča v6 = deg(v6) = 0
Stopnja vrha
S pomočjo zgoraj opisane definicije vemo, da je stopnja oglišča Deg(v) = deg-(v) + ti+(v). Zdaj ga bomo izračunali s pomočjo te formule, kot je ta:
Stopnja oglišča v1 = deg(v1) = 1+2 = 3
Stopnja oglišča v2 = deg(v2) = 1+3 = 4
Stopnja oglišča v3 = deg(v3) = 1+2 = 3
Stopnja oglišča v4 = deg(v4) = 5+0 = 5
Stopnja oglišča v5 = deg(v5) = 1+2 = 3
Stopnja oglišča v6 = deg(v6) = 0+0 = 0
Primer 2:
V tem primeru imamo usmerjen graf s 7 vozlišči. Oglišče 'a' vsebuje 2 robova, to sta 'ad' in 'ab', ki gresta navzven. Zato oglišče 'a' vsebuje izhodno stopnjo, ki je 2. Podobno ima oglišče 'a' tudi rob 'ga', ki prihaja proti temu oglišču 'a'. Zato oglišče 'a' vsebuje in-stopnjo, ki je 1.
rešitev: Notranja in izhodna stopnja vseh zgornjih vozlišč sta opisani takole:
V stopnji:
In-stopnja oglišča a = deg(a) = 1
In-stopnja oglišča b = deg(b) = 2
In-stopnja oglišča c = deg(c) = 2
In-stopnja oglišča d = deg(d) = 1
In-stopnja vozlišča e = deg(e) = 1
In-stopnja oglišča f = deg(f) = 1
In-stopnja oglišča g = deg(g) = 0
Izvenstopnja:
Zunanja stopnja oglišča a = deg(a) = 2
Zunanja stopnja oglišča b = deg(b) = 0
Zunanja stopnja oglišča c = deg(c) = 1
Zunanja stopnja oglišča d = deg(d) = 1
Zunanja stopnja oglišča e = deg(e) = 1
Zunanja stopnja oglišča f = deg(f) = 1
Zunanja stopnja oglišča g = deg(g) = 2
Stopnja vsakega vrha:
Vemo, da je stopnja oglišča Deg(v) = deg-(v) + ti+(v). Zdaj ga bomo izračunali s pomočjo te formule, kot je ta:
Stopnja oglišča a = deg(a) = 1+2 = 3
Stopnja oglišča b = deg(b) = 2+0 = 2
Stopnja oglišča c = deg(c) = 2+1 = 3
Stopnja oglišča d = deg(d) = 1+1 = 2
Stopnja oglišča e = deg(e) = 1+1 = 2
Stopnja oglišča f = deg(f) = 1+1 = 2
Stopnja oglišča g = deg(g) = 0+2 = 2
Primer 3: V tem primeru imamo usmerjen graf s 5 vozlišči. Oglišče 'a' vsebuje 1 rob, tj. 'ae', ki gresta navzven. Zato oglišče 'a' vsebuje izhodno stopnjo, ki je 1. Podobno ima oglišče 'a' tudi rob 'ba', ki prihaja proti temu oglišču 'a'. Zato oglišče 'a' vsebuje in-stopnjo, ki je 1.
rešitev: Notranja in izhodna stopnja vseh zgornjih vozlišč sta opisani takole:
V stopnji
In-stopnja oglišča a = deg(a) = 1
In-stopnja oglišča b = deg(b) = 0
razlika med podjetjem in družbo
In-stopnja oglišča c = deg(c) = 2
In-stopnja oglišča d = deg(d) = 1
In-stopnja vozlišča e = deg(e) = 1
Izvenstopnja:
Zunanja stopnja oglišča a = deg(a) = 1
Zunanja stopnja oglišča b = deg(b) = 2
anonimna funkcija java
Zunanja stopnja oglišča c = deg(c) = 0
Zunanja stopnja oglišča d = deg(d) = 1
Zunanja stopnja oglišča e = deg(e) = 1
Stopnja vsakega vrha:
Vemo, da je stopnja oglišča Deg(v) = deg-(v) + ti+(v). Zdaj ga bomo izračunali s pomočjo te formule, kot je ta:
Stopnja oglišča a = deg(a) = 1+1 = 2
Stopnja oglišča b = deg(b) = 0+2 = 2
Stopnja oglišča c = deg(c) = 2+0 = 2
Stopnja oglišča d = deg(d) = 1+1 = 2
Stopnja oglišča e = deg(e) = 1+1 = 2
Primer 4: V tem primeru imamo graf in določiti moramo stopnjo, notranjo in izhodno stopnjo vsakega vozlišča.
rešitev: Za to bomo najprej ugotovili notranjo stopnjo oglišča in nato izhodno stopnjo oglišča.
Kot lahko vidimo, zgornji graf vsebuje vseh 8 vozlišč, tj. 0, 1, 2, 3, 4, 5 in 6.
V stopnji:
In-stopnja oglišča 0 = deg(0) = 1
In-stopnja oglišča 1 = deg(1) = 2
In-stopnja oglišča 2 = deg(2) = 2
In-stopnja oglišča 3 = deg(3) = 2
In-stopnja oglišča 4 = deg(4) = 2
In-stopnja oglišča 5 = deg(5) = 2
In-stopnja oglišča 6 = deg(6) = 2
Izvenstopnja:
Zunanja stopnja oglišča 0 = deg(0) = 2
Zunanja stopnja oglišča 1 = deg(1) = 1
Zunanja stopnja oglišča 2 = deg(2) = 3
Zunanja stopnja oglišča 3 = deg(3) = 2
Zunanja stopnja oglišča 4 = deg(4) = 2
Zunanja stopnja oglišča 5 = deg(5) = 2
Zunanja stopnja oglišča 6 = deg(6) = 1
Stopnja vsakega vrha:
Vemo, da je stopnja oglišča Deg(v) = deg-(v) + ti+(v). Zdaj ga bomo izračunali s pomočjo te formule, kot je ta:
Stopnja oglišča 0 = deg(0) = 1+2 = 3
Stopnja oglišča 1 = deg(1) = 2+1 = 3
Stopnja oglišča 2 = deg(2) = 2+3 = 5
Stopnja oglišča 3 = deg(3) = 2+2 = 4
Stopnja oglišča 4 = deg(4) = 2+2 = 4
Stopnja oglišča 5 = deg(5) = 2+2 = 4
Stopnja oglišča 6 = deg(5) = 2+1 = 3
Stopenjsko zaporedje grafa
Da bi določili zaporedje stopenj grafa, moramo najprej določiti stopnjo vsakega vozlišča v grafu. Nato bomo te stopinje zapisali v naraščajočem vrstnem redu. Ta vrstni red/zaporedje lahko imenujemo stopenjsko zaporedje grafa.
Na primer: V tem primeru imamo tri grafe s 3, 4 in 5 vozlišči, zaporedje stopenj vseh grafov pa je 3.
V zgornjem grafu so 3 vozlišča. Stopnja zaporedja tega grafa je opisana na naslednji način:
V zgornjem grafu so 4 vozlišča. Zaporedje stopinj tega grafa je opisano takole:
V zgornjem grafu je 5 vozlišč. Zaporedje stopinj tega grafa je opisano takole: