Vertice (teoria dei grafi) - Vertex (graph theory)

Un grafico con 6 vertici e 7 bordi in cui il numero di vertice 6 all'estrema sinistra è un vertice foglia o un vertice pendente

In matematica , e più specificamente nella teoria dei grafi , un vertice ( vertici plurali ) o nodo è l'unità fondamentale di cui sono formati i grafi: un grafo non orientato è costituito da un insieme di vertici e da un insieme di spigoli (coppie di vertici non ordinate), mentre un grafo orientato è costituito da un insieme di vertici e un insieme di archi (coppie ordinate di vertici). In un diagramma di un grafico, un vertice è solitamente rappresentato da un cerchio con un'etichetta e un bordo è rappresentato da una linea o una freccia che si estende da un vertice all'altro.

Dal punto di vista della teoria dei grafi, i vertici sono trattati come oggetti privi di caratteristiche e indivisibili , sebbene possano avere una struttura aggiuntiva a seconda dell'applicazione da cui nasce il grafo; per esempio, una rete semantica è un grafo in cui i vertici rappresentano concetti o classi di oggetti.

Si dice che i due vertici che formano un bordo siano i punti finali di questo bordo e che il bordo sia incidente ai vertici. Un vertice w si dice adiacente ad un altro vertice v se il grafo contiene un arco ( v , w ). L' intorno di un vertice v è un sottografo indotto del grafo, formato da tutti i vertici adiacenti a  v .

Tipi di vertici

Un piccolo esempio di rete con 8 vertici e 10 bordi.
Esempio di rete con 8 vertici (di cui uno isolato) e 10 spigoli.

Il grado di un vertice, indicato con 𝛿(v) in un grafo, è il numero di archi incidenti ad esso. Un vertice isolato è un vertice di grado zero; cioè, un vertice che non è un punto finale di alcun bordo (l'immagine di esempio illustra un vertice isolato). Un vertice foglia (anche vertice pendente ) è un vertice di grado uno. In un grafo orientato si distingue il grado esterno (numero di archi uscenti), indicato con 𝛿 + (v), dall'ingrado (numero di archi entranti), indicato con 𝛿 (v); un vertice sorgente è un vertice con grado zero, mentre un vertice sink è un vertice con grado zero. Un vertice simpliciale è quello i cui vicini formano una cricca : ogni due vicini sono adiacenti. Un vertice universale è un vertice adiacente a ogni altro vertice nel grafico.

Un vertice tagliato è un vertice la cui rimozione scollegherebbe il grafo rimanente; un separatore di vertici è una raccolta di vertici la cui rimozione scollegherebbe il grafo rimanente in piccoli pezzi. Un grafo connesso a k vertici è un grafo in cui la rimozione di meno di k vertici lascia sempre connesso il grafo rimanente. Un insieme indipendente è un insieme di vertici di cui non due adiacenti, e una copertura dei vertici è un insieme di vertici che include almeno un punto finale di ciascun bordo nel grafico. Lo spazio dei vertici di un grafo è uno spazio vettoriale avente un insieme di vettori di base corrispondenti ai vertici del grafo.

Un grafo è transitivo al vertice se ha simmetrie che mappano qualsiasi vertice su qualsiasi altro vertice. Nel contesto dell'enumerazione dei grafi e dell'isomorfismo dei grafi è importante distinguere tra vertici etichettati e vertici non etichettati . Un vertice etichettato è un vertice associato a informazioni aggiuntive che consentono di distinguerlo dagli altri vertici etichettati; due grafi possono essere considerati isomorfi solo se la corrispondenza tra i loro vertici accoppia vertici con etichette uguali. Un vertice senza etichetta è uno che può essere sostituito con qualsiasi altro vertice in base solo alle sue adiacenze nel grafico e non in base a informazioni aggiuntive.

I vertici nei grafici sono analoghi, ma non uguali ai vertici dei poliedri : lo scheletro di un poliedro forma un grafico, i cui vertici sono i vertici del poliedro, ma i vertici del poliedro hanno una struttura aggiuntiva (la loro posizione geometrica) che è non si presume essere presente nella teoria dei grafi. La figura del vertice di un vertice in un poliedro è analoga all'intorno di un vertice in un grafo.

Guarda anche

Riferimenti

  • Gallo, Giorgio; Pallotino, Stefano (1988). "Algoritmi del percorso più breve". Annali di Ricerca Operativa . 13 (1): 1-79. doi : 10.1007/BF02288320 .
  • Berge, Claude , Théorie des graphes et ses application . Collection Universitaire de Mathématiques, II Dunod, Parigi 1958, viii+277 pp. (edizione inglese, Wiley 1961; Methuen & Co, New York 1962; russo, Mosca 1961; spagnolo, Messico 1962; rumeno, Bucarest 1969; cinese, Shanghai 1963 ; Seconda tiratura della prima edizione inglese del 1962. Dover, New York 2001)
  • Chartrand, Gary (1985). Introduzione alla teoria dei grafi . New York: Dover. ISBN 0-486-24775-9.
  • Biggs, Norman; Lloyd, EH; Wilson, Robin J. (1986). Teoria dei grafi, 1736-1936 . Oxford [Oxfordshire]: Clarendon Press. ISBN 0-19-853916-9.
  • Harary, Frank (1969). Teoria dei grafi . Lettura, Mass.: Addison-Wesley Publishing. ISBN 0-201-41033-8.
  • Harary, Frank; Palmer, Edgar M. (1973). Enumerazione grafica . New York, stampa accademica. ISBN 0-12-324245-2.

link esterno