Vértice (teoría de grafos)

En matemáticas discretas , y más específicamente en teoría de grafos , un vértice ( o nodo) es la unidad fundamental a partir de la cual se forman los grafos: un grafo no dirigido consta de un conjunto de vértices y un conjunto de aristas (pares no ordenados de vértices), mientras que un grafo dirigido consta de un conjunto de vértices y un conjunto de arcos (pares ordenados de vértices). En un diagrama de grafo, un vértice se representa generalmente mediante un círculo con una etiqueta, y una arista mediante una línea o flecha que va de un vértice a otro.

Desde el punto de vista de la teoría de grafos, los vértices se tratan como objetos indivisibles y sin características distintivas , aunque pueden tener una estructura adicional dependiendo de la aplicación de la que surja el grafo; por ejemplo, una red semántica es un grafo en el que los vértices representan conceptos o clases de objetos.

Los dos vértices que forman una arista se denominan extremos de dicha arista, y se dice que la arista es incidente a los vértices. Un vértice w se considera adyacente a otro vértice v si el grafo contiene una arista ( v , w ). La vecindad de un vértice v es un subgrafo inducido del grafo, formado por todos los vértices adyacentes a v . 

El grado de un vértice, denotado 𝛿(v) en un grafo, es el número de aristas incidentes a él. Un vértice aislado es un vértice con grado cero; es decir, un vértice que no es un extremo de ninguna arista (la imagen de ejemplo ilustra un vértice aislado). ^{[ 1 ]} Un vértice hoja (también vértice colgante ) es un vértice con grado uno. En un grafo dirigido, se puede distinguir el grado de salida (número de aristas salientes), denotado 𝛿 ⁺ (v), del grado de entrada (número de aristas entrantes), denotado 𝛿 ⁻ (v); un vértice fuente es un vértice con grado de entrada cero, mientras que un vértice sumidero es un vértice con grado de salida cero. Un vértice simplicial es aquel cuyo vecindario cerrado forma una camarilla : cada dos vecinos son adyacentes. Un vértice universal es un vértice que es adyacente a todos los demás vértices del grafo.

Un vértice de corte es un vértice cuya eliminación desconectaría el grafo restante; un separador de vértices es un conjunto de vértices cuya eliminación desconectaría el grafo restante en pequeños fragmentos. Un grafo k-conexo es un grafo en el que la eliminación de menos de k vértices siempre deja el grafo restante conectado. Un conjunto independiente es un conjunto de vértices cuyos vértices no son adyacentes entre sí, y una cobertura de vértices es un conjunto de vértices que incluye al menos un extremo de cada arista del grafo. El espacio de vértices de un grafo es un espacio vectorial que tiene un conjunto de vectores base que corresponden a los vértices del grafo.

Un grafo es transitivo en cuanto a vértices si posee simetrías que mapean cualquier vértice a cualquier otro. En el contexto de la enumeración e isomorfismo de grafos , es importante distinguir entre vértices etiquetados y no etiquetados . Un vértice etiquetado es aquel que se asocia con información adicional que permite distinguirlo de otros vértices etiquetados; dos grafos pueden considerarse isomorfos solo si la correspondencia entre sus vértices empareja vértices con etiquetas iguales. Un vértice no etiquetado es aquel que puede sustituirse por cualquier otro vértice basándose únicamente en sus adyacencias en el grafo y no en ninguna información adicional.

Los vértices en los grafos son análogos, pero no idénticos, a los vértices de los poliedros : el esqueleto de un poliedro forma un grafo, cuyos vértices son los mismos que los del poliedro, pero los vértices de los poliedros poseen una estructura adicional (su ubicación geométrica) que no se considera presente en la teoría de grafos. La figura de un vértice en un poliedro es análoga a la vecindad de un vértice en un grafo.

• Nodo (informática)
• teoría de grafos
• Glosario de teoría de grafos

• Gallo, Giorgio; Pallotino, Stefano (1988). "Algoritmos de ruta más corta". Annals of Operations Research . 13 (1): 1– 79. doi : 10.1007/BF02288320 . S2CID 62752810 . 
• Berge, Claude , Théorie des graphes et ses apps . Collection Universitaire de Mathématiques, II Dunod, París 1958, viii+277 págs. (Edición en inglés, Wiley 1961; Methuen & Co, Nueva York 1962; Ruso, Moscú 1961; Español, México 1962; Rumano, Bucarest 1969; Chino, Shanghai 1963; Segunda impresión de la primera edición en inglés de 1962. Dover, Nueva York 2001)
• Chartrand, Gary (1985). Introducción a la teoría de grafos . Nueva York: Dover. ISBN 0-486-24775-9.
• Biggs, Norman ; Lloyd, EH; Wilson, Robin J. (1986). Teoría de grafos, 1736-1936 . Oxford [Oxfordshire]: Clarendon Press. ISBN 0-19-853916-9.
• Harary, Frank (1969). Teoría de grafos . Reading, Mass.: Addison-Wesley Publishing. ISBN 0-201-41033-8.
• Harary, Frank; Palmer, Edgar M. (1973). Enumeración gráfica . Nueva York, Academic Press. ISBN 0-12-324245-2.

• Weisstein, Eric W. "Vértice de grafo" . MathWorld .