Vertex (grafteori)
I grafteorin är en vertex den grundläggande enheten som utgör grafer - en oriktad graf består av många hörn och många kanter (oordnade par av hörn), medan en riktad graf består av många hörn och många bågar (ordnade par av hörn). I ritningar som representerar en graf indikeras en vertex vanligtvis med en cirkel med en etikett, en kant med en linje och en båge med en pil som förbinder hörnen.
Ur grafteoretisk synvinkel behandlas hörn som särdragslösa odelbara objekt, även om de kan representera en viss struktur beroende på vilket problem grafen härstammar från. Till exempel är ett semantiskt nätverk en graf där hörn representerar konceptet för en klass av objekt.
De två hörn som bildar en kant kallas ändpunkten på kanten, och kanten sägs falla in mot hörnen. En vertex w sägs ligga intill en annan vertex v om grafen innehåller en kant ( v , w ). En grannskap av en vertex v är en genererad subgraf som bildas av alla hörn intill v .
Vertextyper
Graden av en vertex i en graf är antalet kanter som faller in på den. En vertex kallas isolerad om dess grad är noll. Det vill säga, det är en vertex som inte är slutet på någon kant. En vertex kallas ett löv (eller hängande ) om det har en grad av ett. En riktad graf skiljer mellan ut-graden (antalet utgående bågar) och in-graden (antalet inkommande kanter). Källan kallas vertex med noll in-grad, och vertex med noll ut-grad kallas sjunka .
Ett gångjärn är en vertex vars borttagning leder till en ökning av de anslutna komponenterna i grafen. En vertexseparator är en uppsättning hörn, vars borttagning leder till en ökning av de anslutna komponenterna i grafen. En vertex k-ansluten graf är en där borttagning av färre än k hörn alltid lämnar grafen ansluten. En oberoende uppsättning är en uppsättning av hörn varav inte två är intilliggande, och ett vertextäcke är en uppsättning av hörn som inkluderar minst en ändpunkt av valfri kant på grafen. Vektorutrymmet för hörn i en graf är ett vektorrum som har som bas de vektorer som motsvarar grafens hörn (över fältet med siffror {0, 1}) [1] [2] .
En graf sägs vara vertextransitiv om den har symmetrier som tar vilken vertex som helst till vilken annan vertex som helst. I samband med grafuppräkning och grafisomorfism är det viktigt att skilja mellan märkta hörn och omärkta hörn . En märkt vertex är ytterligare information associerad med en vertex som skiljer den från andra märkta hörn. Två grafer kan betraktas som isomorfa endast om isomorfismen tar hörn till hörn med samma etiketter. Omärkta hörn kan sedan översättas till andra hörn baserat endast på närhet och utan att använda ytterligare information.
En grafs hörn liknar hörnen på en polytop , men de är inte desamma - skelettet av en polytop bildar en graf vars hörn är vinkeln på polytopen, men polytopens hörn har en extra struktur (geometrisk plats) som ignoreras i grafteorin. Hörnetsfiguren för en polyeder liknar grannskapet till en grafvertex.
Se även
Anteckningar
- ↑ M. Swami, K. Tulasimaran. Grafer, nätverk och algoritmer. - Moskva: Mir, 1984. - S. 62-76. kapitel 4
- ↑ Reinhard Distel. Grafteori. - Novosibirsk: Publishing House of the Institute of Mathematics, 2002. - S. 35.
Länkar
- Giorgio Gallo, Stefano Pallotino. Shortest path algorithms (engelska) // Annals of Operations Research. - 1988. - Vol. 13 , iss. 1 . - S. 1-79 . - doi : 10.1007/BF02288320 .
- K. Berge Grafteori och dess tillämpning. - Moscow: Foreign Literature Publishing House, 1962.
- Gary Chartrand. Inledande grafteori . - New York: Dover, 1985. - ISBN 0-486-24775-9 .
- Norman Biggs, EH Lloyd, Robin J. Wilson. Grafteori, 1736-1936. - Oxford [Oxfordshire]: Clarendon Press, 1986. - ISBN 0-19-853916-9 .
- Frank Harary . grafteori. - Reading, Mass.: Addison-Wesley Publishing, 1969. - ISBN 0-201-41033-8 .
- Frank Harary , Edgar M. Palmer,. Grafisk uppräkning. - New York: Academic Press, 1973. - ISBN 0-12-324245-2 .
- Weisstein, Eric W. Graph Vertex (engelska) på Wolfram MathWorld- webbplatsen .
 Ordböcker och uppslagsverk |
|---|