Grad af et toppunkt (grafteori)

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 28. juni 2021; verifikation kræver 1 redigering .

Graden ( valensen ) af et grafens toppunkt er antallet af grafkanter , der falder ind på toppunktet . Ved beregning af graden tages kantsløjfen i betragtning to gange. [en] $G$ $x$

Graden af et toppunkt betegnes normalt som eller . De maksimale og mindste grader af hjørner af en graf G er angivet med henholdsvis Δ( G ) og δ( G ). På fig. 1, den maksimale grad er 5, minimum er 0. I en almindelig graf er graderne af alle hjørner de samme, så i dette tilfælde kan vi tale om graden af grafen . $d(x)$ $\grader(v)$

Håndtrykslemmaet

Ved formlen for summen af potenser for en graf , $G=(V,E)$

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

det vil sige, at summen af graderne af hjørnerne af enhver graf er lig med det dobbelte af antallet af dens kanter. Derudover følger det af formlen, at i enhver graf er antallet af hjørner af ulige grad lige. Denne erklæring (og selve formlen) er kendt som håndtrykslemmaet . Navnet kommer fra et velkendt matematisk problem: det er nødvendigt at bevise, at i enhver gruppe er antallet af mennesker, der gav hånd med et ulige antal andre, lige.

Gradrækkefølge af hjørner

Topgradssekvensen af en urettet graf er en ikke -stigende sekvens . [2] For grafen vist i fig. 1, har den formen (5, 3, 3, 2, 2, 1, 0). Rækkefølgen af toppunktsgrader er grafen invariant , så den er den samme for isomorfe grafer. Rækkefølgen af toppunktsgrader er dog ikke et unikt kendetegn ved en graf: I nogle tilfælde har ikke-isomorfe grafer også den samme sekvens.

Gradsekvensproblemet er at finde nogle eller alle grafer med en given ikke-stigende sekvens af naturlige tal (nul grader kan ignoreres i dette tilfælde, da deres antal ændres ved at tilføje eller fjerne isolerede hjørner). En sekvens, der er en sekvens af grader af en graf, kaldes en grafisk sekvens . Det følger af formlen for summen af grader, at enhver sekvens med en ulige sum (som f.eks. 3, 3, 1) ikke kan være en sekvens af grader af en graf. Det omvendte er også sandt: hvis en sekvens har en lige sum, er det en sekvens af potenser af en multigraf . Konstruktionen af en sådan graf udføres på en ret enkel måde: det er nødvendigt at kombinere hjørnerne af ulige grader i par , sløjfer skal tilføjes til de resterende ufyldte hjørner.

Det er sværere at implementere en simpel graf med en given rækkefølge. Erdős-Gallay-sætningen siger, at en ikke-stigende sekvens d i (for i = 1,..., n ) kan kun være en simpel grafsekvens , hvis summen er lige og uligheden

\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\}\,.

For eksempel kan sekvensen (3, 3, 3, 1) ikke være en simpel grafsekvens; den opfylder kun Erdős-Gallai-uligheden for k lig med 1, men ikke for k lig med 2 eller 3.

Ifølge Havel-Hakimi-kriteriet , hvis en ikke-stigende sekvens ( d 1 , d 2 , …, d n ) er en sekvens af grader af en simpel graf, så ( d 2 − 1, d 3 − 1, …, d d 1 +1 − 1, d d 1 +2 , d d 1 +3 , …, d n ) en eller anden sekvens af grader af en simpel graf. Dette faktum giver os mulighed for at konstruere en polynomial algoritme til at finde en simpel graf med en given realiserbar sekvens.

Lad os sammenligne den indledende talrække af grafens hjørner uden kanter med de nødvendige grader. Denne sekvenstransformation definerer mindst ét grafisk toppunkt, alle kanter, der falder ind dertil, og et sæt toppunkter med nye nødvendige gradkomplementer. Ved at sortere de resterende hjørner efter ikke-stigende gradkomplementer får vi en ikke-stigende sekvens af grader af en simpel graf. Ved at gentage transformationen og ikke bestille mere end n-1 gange får vi hele grafen.

Problemet med at finde eller estimere antallet af grafer i en given rækkefølge hører til feltet med optælling af grafer .

Private værdier

Et toppunkt på grad 0 kaldes isoleret .
Et toppunkt af grad 1 kaldes en terminal ( eng. end vertex ), hængende ( eng. pendant vertex ) eller grafblad ( eng. leaf vertex ). En kant, der falder ind på et sådant toppunkt, kaldes hængende ( engelsk terminal (pendant) edge, end-edge ). På fig. 3, er den hængende kant {3,5}. Lignende terminologi bruges i studiet af træer generelt og som datastrukturer .
Et toppunkt af grad n-1 i en graf af orden n kaldes et dominerende toppunkt .

Generelle egenskaber

Hvis alle hjørner af en graf har samme grad k , kaldes grafen en k -regulær eller regulær graf af grad k . I dette tilfælde har selve grafen grad k .
En Euler-sti eksisterer i en urettet, forbundet graf, hvis og kun hvis grafen har 0 eller 2 hjørner af ulige grader. Hvis grafen indeholder 0 hjørner af ulige grader, er Euler-stien en cyklus.
Digrafen er en pseudo-skov[ ukendt udtryk ] kun hvis udgraden af hvert toppunkt højst er 1. En funktionel graf er et specialtilfælde af en pseudo-skov, hvor udgraderne af alle toppunkter er lig med 1.
Ifølge Brooks' sætning overstiger det kromatiske tal for enhver graf, bortset fra en klike eller en ulige cyklus, ikke den maksimale grad af dens hjørner (Δ). Ifølge Vizings teorem overstiger det kromatiske indeks for enhver graf ikke Δ + 1.
En k -degenereret graf er en graf, hvor hver undergraf har et toppunkt på højst k .

Se også

Ind- og ud -grad af hjørner af rettede grafer
Gradfordeling

Noter

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

Kilder

Distel, Reinhard (2005), Graph Theory (3. udgave), Berlin, 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), Om realiserbarheden af et sæt af heltal som grader af hjørnerne af en lineær graf. I, Journal of the Society for Industrial and Applied Mathematics bind 10: 496–506 .
Sirksma, Hirard & Hoohefen, Khan (1991), Syv kriterier for, at heltalssekvenser er grafiske , Journal of Graph Theory bind 15 (2): 223–231 , DOI 10.1002/jgt.3190150209 .