Vértice (teoría de grafos)

En la teoría de grafos, un vértice es la unidad fundamental que forma los gráficos: un gráfico no dirigido consta de muchos vértices y muchas aristas (pares de vértices no ordenados), mientras que un gráfico dirigido consta de muchos vértices y muchos arcos (pares de vértices ordenados). En los dibujos que representan un gráfico, un vértice generalmente se indica con un círculo con una etiqueta, un borde con una línea y un arco con una flecha que conecta los vértices.

Desde el punto de vista de la teoría de grafos, los vértices se tratan como objetos indivisibles sin características, aunque pueden representar alguna estructura según el problema del que se originó el gráfico. Por ejemplo , una red semántica  es un gráfico en el que los vértices representan el concepto de una clase de objetos.

Los dos vértices que forman una arista se llaman vértices extremos de la 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 ). Una vecindad de un vértice v es un subgrafo generado formado por todos los vértices adyacentes a v .

Tipos de vértices

El grado de un vértice en un grafo es el número de aristas que le inciden. Un vértice se dice aislado si su grado es cero. Es decir, es un vértice que no es el final de ninguna arista. Un vértice se llama hoja (o colgante ) si tiene un grado de uno. Un gráfico dirigido distingue entre el grado de salida (el número de arcos de salida) y el grado de entrada (el número de aristas de entrada). La fuente se llama vértice con grado de entrada cero, y el vértice con grado de salida cero se llama sumidero .

Una bisagra es un vértice cuya eliminación conduce a un aumento en los componentes conectados del gráfico. Un separador de vértices es un conjunto de vértices, cuya eliminación conduce a un aumento en los componentes conectados del gráfico. Un grafo con vértice k conectado  es aquel en el que al eliminar menos de k vértices siempre se deja el grafo conectado. 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 vértice final de cualquier borde del gráfico. El espacio vectorial de vértices de un grafo es un espacio vectorial que tiene como base los vectores correspondientes a los vértices del grafo (sobre el campo de números {0, 1}) [1] [2] .

Se dice que un grafo es transitivo de vértice si tiene simetrías que llevan 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 información adicional asociada con un vértice que lo distingue de otros vértices etiquetados. Dos gráficos pueden considerarse isomorfos solo si el isomorfismo lleva vértices a vértices con las mismas etiquetas. Los vértices no etiquetados se pueden traducir a otros vértices basándose únicamente en la adyacencia y sin usar información adicional.

Los vértices de un gráfico son similares a los vértices de un politopo , pero no son lo mismo: el esqueleto de un politopo forma un gráfico cuyos vértices son los vértices del politopo, pero los vértices del politopo tienen un adicional estructura (ubicación geométrica) que se ignora en la teoría de grafos. La figura del vértice de un poliedro es similar a la vecindad de un vértice de un gráfico.

Véase también

Notas

  1. ↑ M. Swami, K. Tulasimaran. Grafos, redes y algoritmos. - Moscú: Mir, 1984. - S. 62-76. Capítulo 4
  2. ↑ Reinhard Distel. Teoría de grafos. - Novosibirsk: Editorial del Instituto de Matemáticas, 2002. - P. 35.

Enlaces

  Ir al elemento de Wikidata  diccionarios y enciclopedias