Vértice (teoría de grafos)

En matemáticas, y más concretamente en teoría de grafos, un vértice (vértices en plural) o nodo es la unidad fundamental de la que se forman los grafos: un grafo no dirigido consta de un conjunto de vértices y un conjunto de aristas (pares de vértices no ordenados), 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 se tratan como objetos indivisibles y sin características, aunque pueden tener una estructura adicional según la aplicación de la que surge el gráfico; por ejemplo, una red semántica es un gráfico en el que los vértices representan conceptos o clases de objetos.

Los dos vértices que forman una arista se dice que son los extremos de esta arista, y la arista se dice que 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 grafo, formado por todos los vértices adyacentes a v.

Tipos de vértices

El grado de un vértice, denotado ?(v) en un gráfico, es el número de aristas que le inciden. 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). 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 interior cero, mientras que un vértice receptor es un vértice con grado exterior cero. Un vértice simpliciales aquel cuyos vecinos forman una camarilla: cada dos vecinos son contiguos. Un vértice universal es un vértice que es adyacente a cualquier otro vértice en el 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 pedazos pequeños. Un grafo conectado por k vértices es un grafo en el que al quitar menos de k vértices siempre se deja conectado el grafo restante. Un conjunto independiente es un conjunto de vértices de los cuales dos no son adyacentes, y una cubierta de vértices es un conjunto de vértices que incluye al menos un punto final de cada borde 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 grafo 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 isomorfos solo si la correspondencia entre sus vértices empareja vértices con etiquetas iguales. Un vértice sin etiquetar es aquel que se puede sustituir por cualquier otro vértice basándose únicamente en sus adyacencias en el gráfico y no basándose 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 de los poliedros tienen una estructura adicional (su ubicación geométrica) que es 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.