Vértice (teoría de grafos)

En teoría de grafos, un vértice o nodo es la unidad fundamental de la que están formados los grafos. Un grafo no dirigido está formado por un conjunto de vértices y un conjunto de aristas (pares no ordenados de vértices), mientras que un grafo dirigido está compuesto por un conjunto de vértices y un conjunto de arcos (pares ordenados de vértices). En este contexto, los vértices son tratados como objetos indivisibles y sin propiedades, aunque puedan tener una estructura adicional dependiendo de la aplicación por la cual se usa el grafo; por ejemplo, una red semántica es un grafo en donde los vértices representan conceptos o clases de objetos.

Los dos vértices que conforman una arista se llaman puntos finales ("endpoints", en inglés), y esa arista se dice que es incidente a los vértices. Un vértice w es adyacente a otro vértice v si el grafo contiene una arista (v,w) que los une. La vecindad de un vértice v es un grafo inducido del grafo, formado por todos los vértices adyacentes a v.

Vértices y grados

Artículo principal: Grado (teoría de grafos)

El grado de un vértice en un grafo es el número de aristas incidentes a él. Un vértice aislado es un vértice con grado cero; esto es, un vértice que no es punto final de ninguna arista. Un vértice hoja es un vértice con grado uno. En un grafo dirigido, se puede distinguir entre grado de salida ("outdegree", número de aristas que salen del vértice) y grado de entrada ("indegree", número de aristas que llegan al vértice); un vértice fuente es un vértice con grado de entrada cero, mientras que un sumidero es un vértice con grado de salida cero.

Conexiones de vértices

Un vértice de corte es un vértice que al removerlo desconecta al grafo restante. Un conjunto independiente es un conjunto de vértices tal que ninguno es adyacente a otro, y una cobertura de vértices es un conjunto de vértices que incluye los puntos finales de cada arista en un grafo.

Vértices etiquetados

En el contexto de enumeración e isomorfismo de grafos, es importante distinguir entre vértices etiquetados y vértices no etiquetados. Los vértices etiquetados son aquellos que están asociados con información extra mediante etiquetas, que los hace distinguibles entre sí; dos grafos son isomorfos solo si existe una correspondencia entre sus pares de vértices con igual etiqueta. Un vértice no etiquetado es uno que puede ser sustituido por cualquier otro vértice basado solo en sus adyacencias en el grafo, y no en información adicional a este.

Vecindad de un vértice

La vecindad de un vértice x, denotado como $N(x)\,$ está dado por todos los vértices adyacentes a x.

Referencias

Berge, Claude, Théorie des graphes et ses applications. Collection Universitaire de Mathématiques, II Dunod, París 1958, viii+277 pp. (Edición inglesa, Wiley 1961; Methuen & Co, Nueva York 1962; Rusia, Moscú 1961; España, México 1962; Rumania, Bucarest 1969; China, Shanghái 1963; Segunda impresión de la primera edición inglesa de 1962. Dover, New York 2001)
Chartrand, Gary, Introductory Graph Theory, Dover. ISBN 0-486-24775-9.
Biggs, N.; Lloyd, E. & Wilson, R. Graph Theory, 1736-1936 Oxford University Press, 1986
Harary, Frank, Graph Theory, Addison-Wesley, Reading, MA, 1969.
Harary, Frank, y Palmer, Edgar M., Graphical Enumeration (1973), Academic Press, Nueva York, NY.

Véase también

Datos: Q1304193