Vertex (grafteori)

I grafteori er et toppunkt den grundlæggende enhed, der udgør grafer - en urettet graf består af mange toppunkter og mange kanter (uordnede par af toppunkter), mens en rettet graf består af mange toppunkter og mange buer (ordnede par af toppunkter). I tegninger, der repræsenterer en graf, er et toppunkt normalt angivet med en cirkel med en etiket, en kant med en linje og en bue med en pil, der forbinder hjørnerne.

Fra et grafteoretisk synspunkt behandles toppunkter som kendetegnsløse udelelige objekter, selvom de kan repræsentere en vis struktur afhængigt af det problem, som grafen stammer fra. For eksempel er et semantisk netværk  en graf, hvor hjørner repræsenterer begrebet en klasse af objekter.

De to spidser, der danner en kant, kaldes endehjørner af kanten, og kanten siges at falde sammen med spidserne. Et toppunkt w siges at være ved siden af ​​et andet toppunkt v , hvis grafen indeholder en kant ( v , w ). Et kvarter til et toppunkt v er en genereret undergraf dannet af alle hjørner, der støder op til v .

Vertex typer

Graden af ​​et toppunkt i en graf er antallet af kanter, der falder ind på den. Et toppunkt kaldes isoleret , hvis dets grad er nul. Det vil sige, at det er et toppunkt, der ikke er enden af ​​nogen kant. Et toppunkt kaldes et blad (eller hængende ), hvis det har en grad på en. En rettet graf skelner mellem ud-graden (antallet af udgående buer) og in-graden (antallet af indgående kanter). Kilden kaldes toppunktet med nul in-grad, og toppunktet med nul ud-grad kaldes sink .

Et hængsel er et toppunkt, hvis fjernelse fører til en stigning i de forbundne komponenter i grafen. En toppunktseparator er et sæt af hjørner, hvis fjernelse fører til en stigning i de forbundne komponenter i grafen. En vertex k-forbundet graf  er en, hvor fjernelse af færre end k toppunkter altid efterlader grafen forbundet. Et uafhængigt sæt er et sæt af toppunkter, hvoraf ikke to støder op til hinanden, og et toppunktsdæksel er et sæt toppunkter, der omfatter mindst et endepunkt på en hvilken som helst kant af grafen. Vektorrummet for knudepunkter i en graf er et vektorrum, der har som basis de vektorer, der svarer til grafens knudepunkter (over feltet med tallene {0, 1}) [1] [2] .

En graf siges at være vertex-transitiv , hvis den har symmetrier, der fører et hvilket som helst toppunkt til et hvilket som helst andet toppunkt. I forbindelse med grafoptælling og grafisomorfi er det vigtigt at skelne mellem mærkede hjørner og umærkede hjørner . Et mærket toppunkt er yderligere information forbundet med et toppunkt, der adskiller det fra andre mærkede toppunkter. To grafer kan kun betragtes som isomorfe, hvis isomorfien tager toppunkter til toppunkter med de samme etiketter. Umærkede hjørner kan derefter oversættes til andre knudepunkter kun baseret på tilgrænsende og uden brug af yderligere information.

En grafs toppunkter ligner toppunkterne på en polytop , men de er ikke ens - skelettet af en polytop danner en graf, hvis toppunkter er toppunkterne på polytopen, men toppunkterne på polytopen har en ekstra struktur (geometrisk placering), der ignoreres i grafteori. Et polyeders toppunkt svarer til naboskabet til et grafvertex.

Se også

Noter

  1. ↑ M. Swami, K. Tulasimaran. Grafer, netværk og algoritmer. - Moskva: Mir, 1984. - S. 62-76. kapitel 4
  2. ↑ Reinhard Distel. Grafteori. - Novosibirsk: Matematisk Instituts Publishing House, 2002. - S. 35.

Links

  Gå til Wikidata-elementet  Ordbøger og encyklopædier