Examen (grafteori) - Degree (graph theory)

En graf med en slinga med hörn märkta efter grad

I grafteori , den grad (eller valens ) hos en vertex av en graf är antalet kanter som är infallande till vertex; i en multigraf bidrar en slinga 2 till en toppunktsgrad för de två ändarna av kanten. Graden av en toppunkt betecknas eller . Den maximala graden av en graf , betecknad med , och den minsta graden av en graf, betecknad med , är högsta och lägsta av dess hörns grader. I multigrafen som visas till höger är maxgraden 5 och lägsta graden 0.

I en vanlig kurva , varje vertex har samma grad, och så att vi kan tala om den grad av grafen. En komplett graf (betecknas , där är antalet hörn i diagrammet) är en speciell typ av regelbunden kurva där alla hörn har den högsta graden, .

I en signerad graf kallas antalet positiva kanter som är anslutna till vertexen positiv deg och antalet anslutna negativa kanter har namnet negativ deg .

Handshaking lemma

Huvudartikel: Handshaking lemma

Den grad summan formel anges att, givet en graf ,

.

Formeln innebär att antalet hörn med udda grader i alla oriktade diagram är jämnt. Detta uttalande (liksom formeln för gradersumma) är känt som handskakningslemma . Det senare namnet kommer från ett populärt matematiskt problem, som ska bevisa att i alla grupper av människor är antalet människor som har skakat hand med ett udda antal andra personer från gruppen jämnt.

Gradsekvens

Två icke-isomorfa grafer med samma gradsekvens (3, 2, 2, 2, 2, 1, 1, 1).

Den grad sekvensen av en oriktad graf är den icke-ökande sekvens av dess vertex grader; för grafen ovan är det (5, 3, 3, 2, 2, 1, 0). Gradsekvensen är en grafinvariant , så isomorfa grafer har samma gradsekvens. Gradsekvensen identifierar emellertid inte i allmänhet en graf unikt; i vissa fall har icke-isomorfa grafer samma gradssekvens.

Den grad sekvens problem är problemet med att hitta vissa eller alla grafer med graden sekvensen är en given icke-ökande sekvens av positiva heltal. (Släpande nollor kan ignoreras eftersom de realiseras trivialt genom att lägga till ett lämpligt antal isolerade hörn till grafen.) En sekvens som är gradens sekvens för någon graf, dvs för vilken gradersekvensproblemet har en lösning, kallas en grafik eller grafisk sekvens . Som en konsekvens av graden summas formel kan vilken sekvens som helst med en udda summa, såsom (3, 3, 1), inte realiseras som grafsekvensen för en graf. Det omvända är också sant: om en sekvens har en jämn summa är det gradersekvensen för en multigraf. Konstruktionen av en sådan graf är enkel: anslut hörn med udda grader i par (bilda en matchning ) och fyll i de återstående jämna gradräkningarna med självslingor. Frågan om en given gradersekvens kan realiseras med ett enkelt diagram är mer utmanande. Detta problem kallas också grafförverkligandeproblem och kan lösas med antingen Erdős – Gallai -satsen eller Havel -Hakimi -algoritmen . Problemet med att hitta eller uppskatta antalet grafer med en given gradsekvens är ett problem från området grafuppräkning .

Mer allmänt är graden av sekvens för en hypergraf den icke-ökande sekvensen för dess hörngrader. En sekvens är -grafisk om det är gradsekvensen för någon -uniform hypergraf. I synnerhet är en -grafisk sekvens grafisk. Att avgöra om en given sekvens är -Grafisk är genomförbart i polynomisk tid för via Erdős-Gallai sats men är NP-komplett för alla (Deza et al., 2018).

Särskilda värden

En oriktad graf med bladnoder 4, 5, 6, 7, 10, 11 och 12
  • En toppunkt med grad 0 kallas en isolerad topp .
  • En toppunkt med grad 1 kallas för en bladpunkt eller en ändpunkt, och kanten som infaller med den punkten kallas för en hängande kant. I diagrammet till höger är {3,5} en hängande kant. Denna terminologi är vanlig vid studier av träd i grafteori och särskilt träd som datastrukturer .
  • En toppunkt med grad n  - 1 i en graf på n hörn kallas en dominerande toppunkt .

Globala fastigheter

  • Om varje hörn i grafen har samma grad  k , kallas grafen för en k -regelbunden graf och själva grafen sägs ha grad  k . På liknande sätt, en tvådelad graf är i vilken varje två hörn på samma sida av bidelning som varandra har samma grad som kallas en biregular graf .
  • En oriktad, ansluten graf har en eulerisk väg om och bara om den har antingen 0 eller 2 hörn av udda grader. Om den har 0 hörn av udda grader är Eulerian -vägen en Eulerianskrets.
  • En riktad graf är en riktad pseudoforest om och bara om varje toppunkt har högst 1 grader. En funktionell graf är ett specialfall av en pseudoforest där varje toppunkt har utgrader exakt 1.
  • Enligt Brooks sats har alla andra graf G än en klick eller en udda cykel kromatiskt tal högst Δ ( G ), och enligt Vizing's sats har varje graf kromatiskt index högst Δ ( G ) + 1.
  • En k -genererad graf är en graf där varje undergraf har en toppunkt högst k .

Se även

Anteckningar

Referenser