Vertex (grafteori) - Vertex (graph theory)

En graf med 6 hjørner og 7 kanter, hvor toppunktet 6 yderst til venstre er et bladpunkt eller et vedhængende toppunkt

I matematik , og mere specifikt i grafteori , et toppunkt (plural toppunkter ) eller knudepunkt er den grundlæggende enhed i hvilke grafer dannes: et ikke-orienteret graf består af et sæt af knudepunkter og et sæt kanter (ikke ordnede par af knuder), mens en rettet graf består af et sæt hjørner og et sæt buer (ordnede par hjørner). I et diagram over en graf er et toppunkt normalt repræsenteret af en cirkel med en etiket, og en kant repræsenteres af en linje eller pil, der strækker sig fra et toppunkt til et andet.

Set fra grafteoriens synspunkt behandles hjørner som egenskabsløse og udelelige objekter , selvom de kan have yderligere struktur afhængigt af den applikation, hvorfra grafen stammer; for eksempel er et semantisk netværk en graf, hvor hjørnerne repræsenterer begreber eller klasser af objekter.

De to hjørner, der danner en kant, siges at være endepunkterne for denne kant, og det siges, at kanten falder ind i hjørnerne. Et toppunkt w siges at være ved siden af ​​et andet toppunkt v, hvis grafen indeholder en kant ( v , w ). Det område for en knude v er en induceret undergraf af grafen, der dannes af alle vertices støder op til  v .

Typer af hjørner

Et lille eksempelnetværk med 8 hjørner og 10 kanter.
Eksempelnetværk med 8 hjørner (hvoraf det ene er isoleret) og 10 kanter.

Den grad for en knude, betegnet δ (v) i en graf er antallet af kanter hændelsen til det. Et isoleret toppunkt er et toppunkt med grad nul; det vil sige et toppunkt, der ikke er et endepunkt for en kant (eksempelbilledet illustrerer et isoleret toppunkt). Et bladpunkt (også vedhængende toppunkt ) er et toppunkt med grad et. I en rettet graf kan man skelne mellemgraden (antal udgående kanter), angivet 𝛿 + (v), fra indeklassen (antal indgående kanter), betegnet 𝛿 - (v); en kilde toppunkt er et toppunkt med indegree nul, mens en vask toppunkt er et toppunkt med outdegree nul. Et simpelt toppunkt er et, hvis naboer danner en klik : hver anden nabo er tilstødende. Et universelt toppunkt er et toppunkt, der støder op til hvert andet toppunkt i grafen.

Et skåret toppunkt er et toppunkt, hvis fjernelse ville afbryde den resterende graf; en toppunkts separator er en samling af hjørner, hvis fjernelse ville afbryde den resterende graf i små stykker. En k-vertex-forbundet graf er en graf, hvor fjernelse af færre end k- hjørner altid efterlader den resterende graf forbundet. Et uafhængigt sæt er et sæt hjørner, hvoraf to ikke er tilstødende, og et toppunktdæksel er et sæt hjørner, der indeholder mindst et slutpunkt for hver kant i grafen. Den vertex plads af en graf er et vektorrum har et sæt af basisvektorer svarer med grafens toppunkter.

En graf er vertex-transitiv, hvis den har symmetrier, der knytter et hjørne til et andet toppunkt. I forbindelse med grafopregning og grafisomorfisme er det vigtigt at skelne mellem mærkede hjørner og umærkede hjørner . Et mærket toppunkt er et toppunkt, der er forbundet med ekstra information, der gør det muligt at skelne det fra andre mærkede hjørner; to grafer kan kun betragtes som isomorfe, hvis korrespondancen mellem deres hjørner parrer hjørner med lige mærker. Et umærket toppunkt er et, der kan erstattes af et andet toppunkt, kun baseret på dets adjakenser i grafen og ikke baseret på yderligere oplysninger.

Hjørner i grafer er analoge med, men ikke det samme som, hjørner af polyeder : skelettet af et polyhedron danner en graf, hvis hjørner er polyhedrons hjørner, men polyederhoder har yderligere struktur (deres geometriske placering), der er antages ikke at være til stede i grafteorien. Den vertex figur for en knude i et polyeder er analog til nabolaget for en knude i en graf.

Se også

Referencer

  • Gallo, Giorgio; Pallotino, Stefano (1988). "Korteste sti -algoritmer". Annals of Operations Research . 13 (1): 1–79. doi : 10.1007/BF02288320 .
  • Berge, Claude , Théorie des graphes et ses applikationer . Collection Universitaire de Mathématiques, II Dunod, Paris 1958, viii+277 s. (Engelsk udgave, Wiley 1961; Methuen & Co, New York 1962; russisk, Moskva 1961; spansk, Mexico 1962; Roumanian, Bukarest 1969; kinesisk, Shanghai 1963 ; Anden udskrivning af den første engelske udgave fra 1962. Dover, New York 2001)
  • Chartrand, Gary (1985). Indledende grafteori . New York: Dover. ISBN 0-486-24775-9.
  • Biggs, Norman; Lloyd, EH; Wilson, Robin J. (1986). Grafteori, 1736-1936 . Oxford [Oxfordshire]: Clarendon Press. ISBN 0-19-853916-9.
  • Harary, Frank (1969). Grafteori . Reading, Mass .: Addison-Wesley Publishing. ISBN 0-201-41033-8.
  • Harary, Frank; Palmer, Edgar M. (1973). Grafisk optælling . New York, Academic Press. ISBN 0-12-324245-2.

eksterne links