Vértice (Teoría de Grafos)
En la teoría de grafos, un vértice es un nodo o punto fundamental de un grafo, conectado a otros vértices mediante aristas.
Definition
En un grafo, un vértice (plural: vértices) es uno de los puntos; los vértices representan objetos o ubicaciones, y las aristas entre ellos representan conexiones, los "sustantivos" de la teoría de grafos mientras que las aristas son los "verbos." Formalmente, un vértice $v$ en el grafo $G = (V, E)$ es un elemento del conjunto de vértices $V$; el grado $\deg(v)$ es el número de aristas incidentes a $v$ (en grafos dirigidos, el grado de entrada y el grado de salida se cuentan por separado), y el Lema del Apretón de Manos establece que la suma de todos los grados es igual a $2|E|$. En la teoría espectral de grafos, la matriz de adyacencia $A$ tiene $A_{ij} = 1$ si $\{i,j\}$ es una arista; sus valores propios (el espectro de $G$) codifican propiedades estructurales, y el segundo valor propio más pequeño del Laplaciano $L = D - A$ es la conectividad algebraica, que mide qué tan bien conectado está el grafo.
Example
En un grafo de mapa, cada ciudad es un vértice; en una red social, cada persona es un vértice. En un grafo con vértices $\{A,B,C,D\}$ y aristas $\{AB,AC,BC,BD\}$: $\deg(A)=2$, $\deg(B)=3$, $\deg(C)=2$, $\deg(D)=1$, sumando $8 = 2 \times 4$ aristas. Para el grafo completo $K_n$, cada vértice tiene grado $n-1$, y su matriz de adyacencia tiene valores propios $n-1$ (una vez) y $-1$ ($n-1$ veces), dando conectividad algebraica $n$, reflejando conectividad máxima.
Key Insight
Los vértices son las cosas que se estudian, y el Lema del Apretón de Manos implica que el número de vértices de grado impar siempre es par, una restricción de paridad usada en muchas demostraciones. El vector propio de Fiedler (correspondiente al segundo valor propio más pequeño del Laplaciano) proporciona una partición óptima del grafo, usada en la agrupación espectral y los algoritmos de dibujo de grafos.