En matemáticas discretas , y más concretamente en teoría de grafos , un vértice (plural vértices ) 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 de vértices desordenados), mientras que un grafo dirigido consta de un conjunto de vértices y un conjunto de arcos (pares ordenados de vértices). En el diagrama de un gráfico, un vértice generalmente se representa mediante un círculo con una etiqueta y un borde 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 son tratados como objetos sin rasgos distintivos e indivisibles , aunque pueden tener estructura adicional dependiendo de la aplicación de la que surge el grafo; por ejemplo, una red semántica es un gráfico en el que los vértices representan conceptos o clases de objetos.
Se dice que los dos vértices que forman una arista son los puntos finales de esta arista, y se dice que la arista es incidente con los vértices. Se dice que un vértice w es adyacente a otro vértice v si el gráfico contiene una arista ( v , w ). La vecindad de un vértice v es un subgrafo inducido del gráfico, formado por todos los vértices adyacentes a v .
El grado de un vértice, denotado 𝛿(v) en una gráfica, es el número de aristas incidentes en él. Un vértice aislado es un vértice de grado cero; es decir, un vértice que no es un punto final de ningún borde (la imagen de ejemplo ilustra un vértice aislado). [1] Un vértice de hoja (también vértice colgante ) es un vértice de grado uno. En un gráfico dirigido, se puede distinguir el grado exterior (número de aristas salientes), denotado 𝛿 + (v), del grado interior (número de aristas entrantes), denotado 𝛿 − (v); un vértice fuente es un vértice con grado cero, mientras que un vértice sumidero es un vértice con grado cero. Un vértice simplicial es aquel cuyos vecinos forman una camarilla : cada dos vecinos son adyacentes. Un vértice universal es un vértice adyacente a todos los demás vértices del gráfico.
Un vértice cortado es un vértice cuya eliminación desconectaría el gráfico restante; un separador de vértices es una colección de vértices cuya eliminación desconectaría el gráfico restante en pequeños pedazos. Un gráfico conectado con k-vértices es un gráfico en el que al eliminar menos de k vértices siempre se deja el gráfico restante conectado. Un conjunto independiente es un conjunto de vértices de los cuales no hay dos adyacentes, y una cobertura de vértices es un conjunto de vértices que incluye al menos un punto final de cada arista en el gráfico. El espacio de vértices de un gráfico es un espacio vectorial que tiene un conjunto de vectores base correspondientes a los vértices del gráfico.
Un gráfico es transitivo de vértice si tiene simetrías que asignan cualquier vértice a cualquier otro vértice. En el contexto de la enumeración de gráficos y el isomorfismo de gráficos , es importante distinguir entre vértices etiquetados y vértices no etiquetados . Un vértice etiquetado es un vértice asociado con información adicional que permite distinguirlo de otros vértices etiquetados; Dos gráficos pueden considerarse isomórficos solo si la correspondencia entre sus vértices empareja vértices con etiquetas iguales. Un vértice sin etiquetar es aquel que puede sustituirse por cualquier otro vértice basándose únicamente en sus adyacencias en el gráfico y no en ninguna información adicional.
Los vértices en los gráficos son análogos, pero no iguales, a los vértices de los poliedros : el esqueleto de un poliedro forma un gráfico, cuyos vértices son los vértices del poliedro, pero los vértices del poliedro tienen una estructura adicional (su ubicación geométrica), es decir. No se supone que esté presente en la teoría de grafos. La figura del vértice de un vértice en un poliedro es análoga a la vecindad de un vértice en un gráfico.
