Ymmärtääksemme kärjen sisä- ja ulkoasteen, meidän on ensin opittava kärjen asteen käsite. Sen jälkeen voimme helposti ymmärtää kärjen sisä- ja ulkoasteen. Meidän pitäisi tietää, että sisä- ja ulkoaste voidaan määrittää vain suunnatussa graafissa. Voimme laskea kärjen asteen suuntaamattoman graafin avulla. Suuntaamattomassa graafissa emme voi laskea kärjen sisä- ja ulkoastetta.
Huippupisteen aste
Jos haluamme löytää graafin kunkin kärjen asteen, tässä tapauksessa meidän on laskettava niiden suhteiden määrä, jotka tietty huippupiste muodostaa toisen kärjen kanssa. Toisin sanoen voimme määrittää kärjen asteen laskemalla siihen kärkeen yhdistävien reunojen lukumäärän. Huippupisteen aste osoitetaan deg(v) avulla. Jos on olemassa yksinkertainen graafi, joka sisältää n lukumäärää pisteitä, tässä tapauksessa minkä tahansa kärjen aste on:
q1 q2 q3 q4
Deg(v) = n-1 ∀ v ∈ G
Huipulla on kyky muodostaa reuna kaikkien muiden graafin kärkien kanssa paitsi itsensä. Joten yksinkertaisessa graafissa kärjen aste selviää graafin kärkien lukumäärästä miinus 1. Tässä 1:tä käytetään itsepisteeksi, koska se ei tee silmukkaa itsestään. Jos graafi sisältää pisteet, joilla on itsesilmukka, tämän tyyppinen graafi ei ole yksinkertainen graafi.
Esimerkki:
Tässä esimerkissä meillä on graafi, jossa on 6 kärkeä, eli a, b, c, d, e ja f. Huipulla 'a' on aste 5, ja kaikilla muilla pisteillä on aste 1. Jos jollakin kärjellä on aste 1, tämän tyyppistä kärkeä kutsutaan 'päätypisteeksi'.
Graafeissa on kaksi tapausta, joissa voimme tarkastella kärjen astetta, jotka kuvataan seuraavasti:
- Suuntaamaton kaavio
- Suunnattu graafi
Nyt opimme tarkasti suunnatun graafin kärjen asteen ja suuntaamattoman graafin kärjen asteen.
Huippupisteen aste suuntaamattomassa graafissa
Jos on suuntaamaton graafi, tämän tyyppisessä graafissa ei ole suunnattua reunaa. Esimerkkejä suunnattoman graafin kärjen asteen määrittämiseksi kuvataan seuraavasti:
Esimerkki 1: Tässä esimerkissä tarkastelemme suuntaamatonta graafia. Nyt selvitetään kunkin graafin kärjen aste.
Ratkaisu: Yllä olevassa ohjaamattomassa graafissa on yhteensä 5 pistettä, eli a, b, c, d ja e. Kunkin kärjen aste kuvataan seuraavasti:
- Yllä oleva graafi sisältää 2 reunaa, jotka kohtaavat kärjessä 'a'. Tästä syystä Deg(a) = 2
- Tämä graafi sisältää 3 reunaa, jotka kohtaavat kärjessä 'b'. Tästä syystä Deg(b) = 3
- Yllä oleva graafi sisältää yhden reunan, jotka kohtaavat kärjessä 'c'. Tästä syystä Deg(c) = 1. Piikki c tunnetaan myös riippuvaisena kärjenä.
- Yllä oleva graafi sisältää 2 reunaa, jotka kohtaavat kärjessä 'd'. Tästä syystä Deg(d) = 2.
- Yllä oleva graafi sisältää 0 reunaa, jotka kohtaavat kärjessä 'e'. Tästä syystä Deg(a) = 0. Huippupistettä e voidaan kutsua myös eristetyksi kärjeksi.
Esimerkki 2: Tässä esimerkissä tarkastelemme suuntaamatonta graafia. Nyt selvitetään kunkin graafin kärjen aste.
Ratkaisu: Yllä olevassa suuntaamattomassa graafissa on yhteensä 5 pistettä, eli a, b, c, d ja e. Kunkin kärjen aste kuvataan seuraavasti:
Huippupisteen aste a = deg(a) = 2
Huippupisteen aste b = deg(b) = 2
Huippupisteen aste c = deg(c) = 2
Huippupisteen aste d = deg(d) = 2
Huippupisteen aste e = deg(e) = 0
Tässä kaaviossa ei ole riippuvaa kärkeä, ja kärki 'e' on eristetty kärki.
Huippupisteen aste suunnatussa graafissa
Jos graafi on suunnattu graafi, niin tässä graafissa jokaisella kärjellä on oltava sisä- ja ulkoaste. Oletetaan, että on olemassa suunnattu graafi. Tässä kaaviossa voimme käyttää seuraavia vaiheita selvittääksemme kärjen sisä-, ulko- ja asteen.
Vertexin aste
Huippupisteen sisäastetta voidaan kuvata reunojen lukumääränä v:llä, jossa v:llä osoitetaan päätepiste. Toisin sanoen voimme kuvata sitä useana kärkipisteeseen tulevina reunoina. Syntaksin deg avulla-(v), voimme kirjoittaa kärjen sisäasteen. Jos haluamme määrittää kärjen sisäasteen, tätä varten meidän on laskettava kärkeen päättyvien reunojen määrä.
Huippupisteen ulkopuolinen aste
Huippupisteen ulkoastetta voidaan kuvata reunojen lukumääränä v:llä, missä v:tä käytetään osoittamaan alkupiste. Toisin sanoen voimme kuvata sitä useina reunoilla, jotka tulevat ulos kärjestä. Syntaksin deg avulla+(v), voimme kirjoittaa kärjen ulkoasteen. Jos haluamme määrittää kärjen ulkoasteen, tätä varten meidän on laskettava kärjestä alkavien reunojen määrä.
Huippupisteen aste
Huippupisteen aste ilmaistaan asteen deg(v) avulla, joka on yhtä kuin kärjen sisäasteen ja kärjen ulkoasteen summa. Vertexin asteen symbolinen esitys kuvataan seuraavasti:
Deg(v) = deg-(v) + deg+(v)
Esimerkki 1: Tässä esimerkissä meillä on graafi, ja meidän on määritettävä kunkin kärjen aste.
Ratkaisu: Tätä varten selvitetään ensin kärjen aste, kärjen sisäaste ja sitten kärjen ulkoaste.
Kuten näemme, yllä oleva kaavio sisältää yhteensä 6 huippupistettä, eli v1, v2, v3, v4, v5 ja v6.
Tutkinto:
Huippupisteen in-aste v1 = deg(v1) = 1
Huippupisteen in-aste v2 = deg(v2) = 1
Huippupisteen in-aste v3 = deg(v3) = 1
Huippupisteen in-aste v4 = deg(v4) = 5
Huippupisteen in-aste v5 = deg(v5) = 1
Huippupisteen in-aste v6 = deg(v6) = 0
Poistutkinto:
Huippupisteen ulko-aste v1 = deg(v1) = 2
Huippupisteen ulko-aste v2 = deg(v2) = 3
Huippupisteen ulko-aste v3 = deg(v3) = 2
Huippupisteen ulko-aste v4 = deg(v4) = 0
Huippupisteen ulko-aste v5 = deg(v5) = 2
Huippupisteen ulko-aste v6 = deg(v6) = 0
Huippupisteen aste
Yllä kuvatun määritelmän avulla tiedämme, että kärjen aste Deg(v) = aste-(v) + sinä+(v). Nyt laskemme sen tämän kaavan avulla seuraavasti:
Huippupisteen aste v1 = astetta(v1) = 1+2 = 3
Huippupisteen aste v2 = astetta(v2) = 1+3 = 4
Huippupisteen aste v3 = astetta(v3) = 1+2 = 3
Huippupisteen aste v4 = astetta(v4) = 5+0 = 5
Huippupisteen aste v5 = astetta(v5) = 1+2 = 3
Huippupisteen aste v6 = astetta(v6) = 0+0 = 0
Esimerkki 2:
Tässä esimerkissä meillä on suunnattu graafi, jossa on 7 kärkeä. Vertex 'a' sisältää 2 reunaa, eli 'ad' ja 'ab', jotka menevät ulospäin. Näin ollen kärki 'a' sisältää ulkoasteen, joka on 2. Samoin kärjessä 'a' on myös reuna 'ga', joka tulee tätä kärkeä 'a' kohti. Näin ollen kärki 'a' sisältää in-asteen, joka on 1.
Ratkaisu: Kaikkien yllä olevien pisteiden sisä- ja ulkoasteet kuvataan seuraavasti:
Tutkinto:
Huippupisteen in-aste a = deg(a) = 1
Huippupisteen in-aste b = deg(b) = 2
Huippupisteen in-aste c = deg(c) = 2
Huippupisteen in-aste d = deg(d) = 1
Huippupisteen in-aste e = deg(e) = 1
Huippupisteen in-aste f = deg(f) = 1
Huippupisteen in-aste g = deg(g) = 0
Poistutkinto:
Huippupisteen ulko-aste a = deg(a) = 2
Huippupisteen ulko-aste b = deg(b) = 0
Huippupisteen ulko-aste c = deg(c) = 1
Huippupisteen ulko-aste d = deg(d) = 1
Huippupisteen ulko-aste e = deg(e) = 1
Huippupisteen ulko-aste f = deg(f) = 1
Huippupisteen ulko-aste g = deg(g) = 2
Jokaisen kärjen aste:
Tiesimme, että kärjen aste Deg(v) = aste-(v) + sinä+(v). Nyt laskemme sen tämän kaavan avulla seuraavasti:
Huippupisteen aste a = deg(a) = 1+2 = 3
Huippupisteen aste b = deg(b) = 2+0 = 2
Huippupisteen aste c = deg(c) = 2+1 = 3
Huippupisteen aste d = deg(d) = 1+1 = 2
Huippupisteen aste e = deg(e) = 1+1 = 2
Huippupisteen aste f = deg(f) = 1+1 = 2
Huippupisteen aste g = deg(g) = 0+2 = 2
Esimerkki 3: Tässä esimerkissä meillä on suunnattu graafi, jossa on 5 kärkeä. Vertex 'a' sisältää 1 reunan, eli 'ae', jotka menevät ulospäin. Täten kärki 'a' sisältää ulkoasteen, joka on 1. Samoin kärjessä 'a' on myös reuna 'ba', joka tulee tätä kärkeä 'a' kohti. Näin ollen kärki 'a' sisältää in-asteen, joka on 1.
Ratkaisu: Kaikkien yllä olevien pisteiden sisä- ja ulkoasteet kuvataan seuraavasti:
Tutkinnon tasolla
datalinkkikerroksen protokollia
Huippupisteen in-aste a = deg(a) = 1
Huippupisteen in-aste b = deg(b) = 0
Huippupisteen in-aste c = deg(c) = 2
Huippupisteen in-aste d = deg(d) = 1
Huippupisteen in-aste e = deg(e) = 1
Poistutkinto:
Huippupisteen ulko-aste a = deg(a) = 1
Huippupisteen ulko-aste b = deg(b) = 2
Huippupisteen ulko-aste c = deg(c) = 0
Huippupisteen ulko-aste d = deg(d) = 1
Huippupisteen ulko-aste e = deg(e) = 1
Jokaisen kärjen aste:
Tiesimme, että kärjen aste Deg(v) = aste-(v) + sinä+(v). Nyt laskemme sen tämän kaavan avulla seuraavasti:
Huippupisteen aste a = deg(a) = 1+1 = 2
Huippupisteen aste b = deg(b) = 0+2 = 2
Huippupisteen aste c = deg(c) = 2+0 = 2
Huippupisteen aste d = deg(d) = 1+1 = 2
Huippupisteen aste e = deg(e) = 1+1 = 2
Esimerkki 4: Tässä esimerkissä meillä on graafi, ja meidän on määritettävä kunkin kärjen aste, sisä- ja ulkoaste.
Ratkaisu: Tätä varten selvitetään ensin kärjen sisäaste ja sitten kärjen ulkoaste.
Kuten näemme, yllä oleva kaavio sisältää yhteensä 8 kärkeä, eli 0, 1, 2, 3, 4, 5 ja 6.
Tutkinto:
Huippupisteen in-aste 0 = astetta(0) = 1
Huippupisteen in-aste 1 = astetta(1) = 2
Huippupisteen in-aste 2 = astetta(2) = 2
Huippupisteen in-aste 3 = astetta(3) = 2
Huippupisteen in-aste 4 = astetta(4) = 2
Huippupisteen in-aste 5 = astetta(5) = 2
Huippupisteen in-aste 6 = astetta(6) = 2
Poistutkinto:
Huippupisteen ulko-aste 0 = astetta(0) = 2
Huippupisteen ulko-aste 1 = astetta(1) = 1
Huippupisteen ulko-aste 2 = astetta(2) = 3
Huippupisteen ulko-aste 3 = astetta(3) = 2
Huippupisteen ulko-aste 4 = astetta(4) = 2
Huippupisteen ulko-aste 5 = astetta(5) = 2
Huippupisteen ulko-aste 6 = aste(6) = 1
Jokaisen kärjen aste:
Tiesimme, että kärjen aste Deg(v) = aste-(v) + sinä+(v). Nyt laskemme sen tämän kaavan avulla seuraavasti:
Huippupisteen aste 0 = astetta(0) = 1+2 = 3
Huippupisteen aste 1 = aste(1) = 2+1 = 3
Huippupisteen aste 2 = astetta(2) = 2+3 = 5
Huippupisteen aste 3 = aste(3) = 2+2 = 4
Huippupisteen aste 4 = astetta(4) = 2+2 = 4
Huippupisteen aste 5 = astetta(5) = 2+2 = 4
Huippupisteen aste 6 = aste(5) = 2+1 = 3
Graafin astejärjestys
Graafin astesekvenssin määrittämiseksi meidän on ensin määritettävä graafin kunkin kärjen aste. Sen jälkeen kirjoitamme nämä tutkinnot nousevassa järjestyksessä. Tätä järjestystä/sekvenssiä voidaan kutsua graafin astesekvenssiksi.
Esimerkiksi: Tässä esimerkissä meillä on kolme graafia, joissa on 3, 4 ja 5 kärkeä, ja kaikkien graafien astejärjestys on 3.
Yllä olevassa kaaviossa on 3 kärkeä. Tämän kaavion sekvenssin aste kuvataan seuraavasti:
Yllä olevassa kaaviossa on 4 kärkeä. Tämän kaavion astejärjestys on kuvattu seuraavasti:
ohjelmointi c-taulukoissa
Yllä olevassa kaaviossa on 5 kärkeä. Tämän kaavion astejärjestys on kuvattu seuraavasti: