Huippupisteen aste (graafiteoria)

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 28.6.2021 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Graafin kärjen aste ( valenssi ) on graafin kärkeen osuvien graafin reunojen lukumäärä . Astetta laskettaessa reunasilmukka otetaan huomioon kahdesti. [yksi] $G$ $x$

Huippupisteen aste on yleensä merkitty tai . Graafin G pisteiden maksimi- ja minimiasteet on merkitty Δ( G ) ja δ( G ), vastaavasti. Kuvassa 1, maksimiaste on 5, minimi on 0. Säännöisessä graafissa kaikkien kärkien asteet ovat samat, joten tässä tapauksessa voidaan puhua graafin asteesta . $d(x)$ $\deg(v)$

The handshake lemma

Kaavalla graafin potenssien summalle , $G=(V,E)$

\sum _{{v\in V}}\deg(v)=2|E|\,,

eli minkä tahansa graafin kärkien asteiden summa on yhtä suuri kuin sen reunojen määrä kaksi kertaa. Lisäksi kaavasta seuraa, että missä tahansa graafissa parittoman asteen kärkien lukumäärä on parillinen. Tämä lausunto (ja itse kaava) tunnetaan kädenpuristuslemmana . Nimi tulee tunnetusta matemaattisesta ongelmasta: on tarpeen todistaa, että missä tahansa ryhmässä on parillinen määrä ihmisiä, jotka kättelevät parittoman määrän muita.

Piikkien astejärjestys

Suuntaamattoman graafin kärkiastesekvenssi on ei- nouseva sekvenssi . [2] Kuvassa esitetylle kaaviolle. 1, sen muoto on (5, 3, 3, 2, 2, 1, 0). Huippuasteiden sarja on graafiinvariantti , joten se on sama isomorfisille graafiille. Huippuasteiden järjestys ei kuitenkaan ole graafin ainutlaatuinen ominaisuus: joissain tapauksissa myös ei-isomorfisilla graafilla on sama järjestys.

Astesekvenssiongelmana on löytää jotkin tai kaikki graafit tietyllä ei-nousevalla luonnollisten lukujen jonolla (nolla astetta voidaan tässä tapauksessa jättää huomiotta, koska niiden lukumäärää muutetaan lisäämällä tai poistamalla eristettyjä pisteitä). Sekvenssiä, joka on graafin asteiden sarja , kutsutaan graafiseksi sekvenssiksi . Asteiden summan kaavasta seuraa, että mikä tahansa sarja, jolla on pariton summa (kuten esimerkiksi 3, 3, 1), ei voi olla graafin astejono. Päinvastoin on myös totta: jos jonolla on parillinen summa, se on multigrafin potenssien sarja . Tällaisen graafin rakentaminen suoritetaan melko yksinkertaisella tavalla: parittomien asteiden kärjet on yhdistettävä pareiksi , silmukoita tulee lisätä jäljellä oleviin täyttämättömiin pisteisiin.

Yksinkertaisen graafin toteuttaminen tietyllä sekvenssillä on vaikeampaa . Erdős-Gallayn lauseessa sanotaan, että ei-kasvava jono d i (jos i = 1,…, n ) voi olla yksinkertainen graafijono vain , jos sen summa on parillinen ja epäyhtälö

\sum _{{i=1}}^{{k}}d_{i}\leq k(k-1)+\sum _{{i=k+1}}^{n}\min(d_{ i},k)\quad \ k\in \{1,\dots ,n-1\}\,.

Esimerkiksi sekvenssi (3, 3, 3, 1) ei voi olla yksinkertainen kaaviosekvenssi; se tyydyttää Erdős-Gallai-epäyhtälön vain, jos k on 1, mutta ei, jos k on 2 tai 3.

Havel-Hakimi-kriteerin mukaan , jos ei-kasvava jono ( d 1 , d 2 , …, d n ) on yksinkertaisen graafin astejono, niin ( d 2 − 1, d 3 − 1, …, d d 1 +1 − 1, d d 1 +2 , d d 1 +3 , …, d n ) yksinkertaisen graafin jokin astejono. Tämä tosiasia antaa meille mahdollisuuden rakentaa polynomialgoritmi yksinkertaisen graafin löytämiseksi tietyllä toteutettavissa olevalla sekvenssillä.

Verrataan graafin ilman reunoja kärkien alkulukusarjaa vaadittuihin asteisiin. Tämä sekvenssimuunnos määrittää ainakin yhden graafin kärjen, kaikki siihen kohdistuvat reunat ja joukon pisteitä uusilla vaadituilla astekomplementeilla. Järjestämällä loput kärjet ei-nousevien astekomplementtien mukaan, saadaan yksinkertaisen graafin ei-nouseva astejono. Toistamalla muunnos ja järjestämällä enintään n-1 kertaa, saadaan koko graafi.

Graafeiden lukumäärän löytäminen tai estimointi tietyssä sekvenssissä kuuluu graafien luetteloimisen alaan .

Yksityiset arvot

0-asteista kärkeä kutsutaan eristettyksi .
Asteen 1 kärkeä kutsutaan terminaaliksi ( eng. end vertex ), riippuvaksi ( eng. pendant vertex ) tai graafilehdeksi ( eng . leaf vertex ). Reunaa, joka osuu tällaiseen kärkeen, kutsutaan roikkuvaksi ( englanniksi terminaali (riippuva) reuna, end-edge ). Kuvassa 3, riippureuna on {3,5}. Samanlaista terminologiaa käytetään puiden tutkimuksessa yleensä ja tietorakenteina .
Pistettä, jonka aste on n -1 kertaluvun n graafissa , kutsutaan hallitsevaksi kärjeksi .

Yleiset ominaisuudet

Jos graafin kaikilla pisteillä on sama aste k , kuvaajaa kutsutaan k -säännölliseksi tai säännölliseksi k-asteen graafiksi . Tässä tapauksessa itse graafilla on aste k .
Eulerin polku on olemassa suuntaamattomassa, yhdistetyssä graafissa silloin ja vain, jos graafissa on 0 tai 2 parittoman asteen kärkeä. Jos graafissa on 0 parittoman asteen kärkeä, Eulerin polku on sykli.
Digraafi on pseudometsä[ tuntematon termi ] vain , jos kunkin kärjen ulkoaste on enintään 1. Funktionaalinen graafi on pseudometsän erikoistapaus, jossa kaikkien kärkien ulkoasteet ovat yhtä suuria kuin 1.
Brooksin lauseen mukaan minkään graafin kromaattinen luku , paitsi klikkiä tai paritonta sykliä, ei ylitä sen kärkien maksimiastetta (Δ). Vizingin lauseen mukaan minkään graafin kromaattinen indeksi ei ylitä arvoa Δ + 1.
K -degeneroitu graafi on graafi, jossa jokaisella osagraafilla on korkeintaan k asteinen kärki .

Katso myös

Suunnattujen graafien kärkien sisään - ja ulos -aste
Tutkintojen jakautuminen

Muistiinpanot

↑ Distel, s. 5
↑ Distel, s. 278

Lähteet

Distel, Reinhard (2005), Graph Theory (3. painos), Berliini, New York: Springer-Verlag, ISBN 978-3-540-26183-4 , < http://diestel-graph-theory.com/index. html > .
Erdős, P. & Gallai, T. (1960), Gráfok előírt fokszámú pontokkal , Matematikai Lapok T. 11: 264-274 , < http://www.renyi.hu/~p_erdos/1961-05.pdf > .
Hakimi, S. L. (1962), Kokonaislukujoukon realisoitavuudesta lineaarisen graafin kärkien asteina. I, Journal of the Society for Industrial and Applied Mathematics, osa 10: 496–506 .
Sirksma, Hirard & Hoohefen, Khan (1991), Seitsemän kriteeriä, joiden mukaan kokonaislukusekvenssit ovat graafisia , Journal of Graph Theory, osa 15 (2): 223–231 , DOI 10.1002/jgt.3190150209 .