En matemáticas discretas , y más específicamente en teoría de grafos , un vértice (plural vértices ) o nodo es la unidad fundamental de la que se forman los grafos: un grafo no dirigido consiste en un conjunto de vértices y un conjunto de aristas (pares desordenados de vértices), mientras que un grafo dirigido consiste en un conjunto de vértices y un conjunto de arcos (pares ordenados de vértices). En un diagrama de un grafo, un vértice suele representarse mediante un círculo con una etiqueta, y una arista se representa mediante una línea o flecha que se extiende de un vértice a otro.
Desde el punto de vista de la teoría de grafos, los vértices se tratan como objetos sin características e indivisibles , aunque pueden tener una estructura adicional dependiendo de la aplicación de la que surge 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 puntos finales de esta arista, y se dice que la arista es incidente a los vértices. Se dice que un vértice w es 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 punto final 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 de origen 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 uno cuyos vecinos forman 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 cortado es un vértice cuya eliminación desconectaría el grafo restante; un separador de vértices es una colección de vértices cuya eliminación desconectaría el grafo restante en pequeños fragmentos. Un grafo conexo por k vértices es un grafo en el que la eliminación de menos de k vértices siempre deja conectado el grafo restante. Un conjunto independiente es un conjunto de vértices de los cuales ninguno de los dos son adyacentes, y una cubierta de vértices es un conjunto de vértices que incluye al menos un punto final 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 de vértices si tiene simetrías que asignan cualquier vértice a cualquier otro vértice. En el contexto de la enumeración de grafos y el isomorfismo de grafos, es importante distinguir entre vértices etiquetados y vértices no etiquetados . Un vértice etiquetado es un vértice que está asociado con información adicional que le permite distinguirse 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 uno que puede sustituir a cualquier otro vértice basándose solo en sus adyacencias en el grafo y no en ninguna información adicional.
Los vértices de los grafos son análogos a los vértices de los poliedros , pero no iguales : el esqueleto de un poliedro forma un grafo, cuyos vértices son los vértices del poliedro, pero los vértices del poliedro tienen una estructura adicional (su ubicación geométrica) que no se supone que esté presente en la teoría de grafos. La figura de vértice de un vértice en un poliedro es análoga a la vecindad de un vértice en un grafo.
