Vértice (teoría de grafos)
En matemáticas , y más específicamente en teoría de grafos , un vértice ( vértices plurales ) o nodo es la unidad fundamental de la que se forman los gráficos: un grafo no dirigido consiste en 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 un diagrama de un gráfico, un vértice generalmente se representa mediante un círculo con una etiqueta, y un borde se representa con 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 rasgos distintivos , 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 gráfico en el que los vértices representan conceptos o clases de objetos.
Se dice que los dos vértices que forman un borde son los puntos finales de este borde, y se dice que el borde es incidente a los vértices. Se dice que un vértice w es adyacente a otro vértice v si la gráfica 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 a é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] El vértice de una hoja (también vértice colgante ) es un vértice de grado uno. En un gráfico dirigido, se puede distinguir el grado de salida (número de bordes de salida), denotado 𝛿 + (v), del grado de grado (número de bordes de entrada), denotado 𝛿 - (v); un vértice fuente es un vértice con grado cero, mientras que un vértice sumidero es un vértice sin grado cero. Un vértice simpliciales 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 partes pequeñas. Un gráfico conectado con k vértices es un gráfico en el que eliminar menos de k vértices siempre deja conectado el gráfico restante. 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 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 que se corresponden con los vértices del gráfico.
Una gráfica es transitiva por vértice si tiene simetrías que mapean 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 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 base a ninguna información adicional.
