Subgrafos y Operaciones Elementales
Un grafo $G’ = (V’, E’)$ es un subgrafo de $G = (V, E)$ si $V’ \subseteq V$ y $E’ \subseteq E$.
Subgrafo Inducido: Es aquel que, al elegir un conjunto de vértices $V’$, mantiene todas las aristas originales que conectaban a esos vértices en el grafo $G$. No se pueden «elegir» solo algunas aristas; si los vértices estaban conectados originalmente, deben estarlo en el inducido.
Unión de Grafos ($G_1 \cup G_2$): Es la agrupación de dos grafos. Si son disjuntos (no comparten vértices), el grafo resultante tendrá al menos dos componentes conexas y, por definición, no será conexo.
Modificación de la Estructura: Homeomorfismo
El homeomorfismo estudia la «forma» o topología del grafo, permitiendo que las aristas sean flexibles.
Subdivisión Elemental: Insertar un nuevo vértice $w$ en medio de una arista $\{u, v\}$, transformándola en dos aristas $\{u, w\}$ y $\{w, v\}$. El nuevo vértice siempre tiene grado 2.
Contracción de Arista: El proceso inverso; fusionar dos vértices adyacentes $u$ y $v$ en uno solo. El nuevo nodo hereda todos los vecinos que tenían $u$ y $v$.
Definición de Homeomorfismo: Dos grafos son homeomorfos si ambos pueden obtenerse a partir de un mismo grafo mediante subdivisiones elementales. Es decir, comparten la misma estructura básica aunque uno tenga «más paradas» (vértices de grado 2) en sus caminos.
Ejercicio: Determina si \(K_3\) es homeomorfo a \(K_4\)
Caminos y Distancias (Métricas)
- Un recorrido (en inglés, trail, a veces traducido como rastro)[1] es un camino sin aristas repetidas.
- Un camino cerrado es un camino cuyo vértice inicial y final coinciden.
- Un camino abierto es un camino cuyo vértice inicial y final no coinciden.
- Siguiendo la bibliografía de Juan de Burgos, un camino simple es un camino donde todas sus aristas son distintas; es decir, no pasa dos veces por la misma arista. Así un camino simple puede pasar más de una vez por un mismo vértice. Esta definición difiere en otras bibliografías.
- Un circuito (en inglés, circuit) es un recorrido que además es un camino cerrado.
- Llamamos camino elemental, o trayectoria, a un camino simple en el que todos los vértices, salvo el primero y el último, son distintos.
- Un ciclo (en inglés, cycle) es un camino elemental que además es un camino cerrado.
Distancia $d(u, v)$: La longitud del camino más corto entre $u$ y $v$. Si no existe conexión, la distancia es $\infty$.
Ejemplo de distancia en un grafo
De Klaus Röder – Trabajo propio, CC BY-SA 3.0, Enlace. Grafo que representa los divisores del número 12. La distancia entre 1 y 6 es 2, por los caminos 1-2-6 o 1-3-6. La distancia entre 1 y 12 es 3.
La excentricidad o número de asociación de un vértice en un grafo conexo es la mayor distancia entre ese nodo y cualquier otro del grafo. La excentricidad de cualquier grafo no dirigido conexo o de cualquier grafo dirigido fuertemente conexo de ${\displaystyle n}$ vértices varía entre 1 y ${\displaystyle n-1}$. En cambio, la excentricidad de un grafo dirigido débilmente conexo o unilateralmente conexo puede estar indefinida (esto es, infinita).
El diámetro de un grafo es la mayor excentricidad entre todos los vértices del grafo; este valor puede variar entre 1 (para un grafo completo) y ${\displaystyle n-1}$ (por ejemplo, para un grafo camino). Aunque el diámetro de un grafo disconexo sea infinito, el diámetro de sus componentes conexas será siempre finito.
Dos vértices pueden estar conectados por varios caminos. La longitud de un camino es su número de aristas. Formalmente, dado un grafo \({\displaystyle G=(V,E)}\), la distancia entre dos vértices \({\displaystyle i,j\in V}\) se puede denotar como \({\displaystyle d(i,j)}\). Si los vértices no son accesibles, entonces se asume que \({\displaystyle d(i,j)=\infty }\). Si el grafo es no dirigido, entonces \({\displaystyle d(i,j)=d(j,i)}\); sin embargo, si el grafo es dirigido, la distancia puede diferir dependiendo del sentido de las aristas.
Proposición: De un camino en un grafo siempre se puede obtener una trayectoria.
Las definiciones de caminos anteriores también se aplican a grafos dirigidos, siempre y cuando los caminos respeten la dirección de las aristas entre cada vértice y el siguiente. Sin embargo, si en un grafo dirigido se desea prescindir de la dirección de las aristas y considerar sus caminos como si se tratara de un grafo no dirigido, entonces a los caminos se les conoce como semicaminos, a los recorridos como semirrecorridos, a los ciclos como semiciclos, etc.
Proposición: Sea un grafo \(G(V,E)\), entonces \(G\) es bipartito si y sólo si no contiene ciclos de longitud impar.
Conexión y Componentes
Un grafo \(G\) no dirigido se dice conexo si, para cualquier par de vértices \(u\) y \(v\) en \(G\), existe al menos una trayectoria de \(u\) a \(v\). Esto equivale a decir que es conexo si cada par de vértices está conectado por un camino; es decir, si para cualquier par de vértices \((a, b)\), existe al menos una sucesión de vértices y aristas dentro del grafo desde \(a\) hacia \(b\).
Diremos grafo no orientado(o dirigido) subyacente a un grafo orientado dado, al digrafo que resulta de suprimir en éste la dirección en las aristas, eliminando el orden entre los dos vértices que las componen. El grafo no orientado subyacente tiene el mismo número de aristas que el grafo orientado del que proviene.
En un grafo dirigido, podremos decir:
- Grafo débilmente conexo: todos los pares de vértices están débilmente conectados, es decir, unidos por un «semicamino» (camino que no considera la dirección de las aristas); es decir, el grafo subyacente es conexo.
- Grafo unilateralmente conexo: todos los pares de vértices están unilateralmente conectados; es decir, unidos por un camino que va desde uno hasta el otro.
- Grafo fuertemente conexo: todos los pares de vértices están fuertemente conectados, es decir, unidos por al menos dos caminos, uno que va desde uno hasta el otro, y viceversa.
- Grafo recursivamente conexo: todos los pares de vértices están recursivamente conectados, es decir, están fuertemente conectados y el camino desde el uno hasta el otro usa los mismos vértices y aristas que los del camino inverso.
Un grafo que no es conexo se denomina grafo disconexo o inconexo.
Si consideramos la relación de equivalencia:
\(v\ \Re\ u\) si, y sólo si, \(v\) y \(u\) están conectados,
a cada subgrafo G* de G determinado por el conjunto de vértices de cada clase de equivalencia definida por la relación \(\Re\) en V se llama una componente conexa del grafo G; es decir, un subgrafo inducido de un grafo en que cualesquiera dos vértices están conectados mediante un camino. Un vértice aislado, el grafo trivial o un grafo conexo son en sí mismos componentes.
Para los grafos no dirigidos, se habla sencillamente de componentes o componentes conexos. Sin embargo, para grafos dirigidos, se habla de componente débilmente conexo si no se considera el sentido de las aristas, o bien de componente fuertemente conexo, cuando sí se considera el sentido de las aristas.
Proposición: un grafo G se dice que es conexo si solo tiene una componente conexa.
Toda componente conexa de un grafo G es ella misma un grafo conexo y cada par de componentes conexas distintas de un mismo grafo G no tiene ningún vértice común.
Proposición: Si un grafo G tiene únicamente dos vértices de grado impar, estos dos vértices están conectados y en consecuencia pertenecen a una misma componente conexa de G.
Propiedades: Sea un grafo \(G(V,E)\) conexo, entonces \(|E|\geq|V|-1\)
Conectividad y Robustez (Teorema de Whitney)
Cuando hablamos de conectividad de un grafo nos referimos al mínimo número de elementos (vértices o aristas) que se necesitan para, al ser removidos, dividir al grafo en componentes conexas aisladas. A estos vértices o aristas críticos se les denomina vértices de corte o aristas de corte, respectivamente.
La conectividad de un grafo es una medida de su cohesión o robustez. Intuitivamente, un grafo es cohesivo si posee muchas aristas, si los vértices tienen grados relativamente altos, si tiene muchos caminos cortos entre pares de vértices, o si tiene distancias pequeñas (y por tanto, un diámetro—la mayor distancia entre dos vértices del grafo— pequeño) en relación con su tamaño. Por el contrario, un grafo más «vulnerable» corre el riesgo de volverse inconexo si se le retiran unas pocas aristas o vértices.
La conectividad mide cuántos elementos deben fallar para romper la red.
Conectividad de Vértices $\kappa(G)$: Número mínimo de vértices que hay que eliminar para que el grafo deje de ser conexo (o quede un solo vértice).
Punto de Corte: Un vértice cuya eliminación aumenta el número de componentes conexas ($\kappa(G) = 1$).
Conectividad de Aristas $\lambda(G)$: Número mínimo de aristas que hay que eliminar para desconectar el grafo.
Puente: Una arista cuya eliminación desconecta el grafo ($\lambda(G) = 1$).
Ejercicio: Cuál es el valor de $\kappa(G)$ del siguiente grafo:
De j_ham3 – Trabajo propio, CC BY-SA 3.0, Enlace Pese a ser un grafo conexo, la conectividad de este grafo no dirigido depende de vértices o aristas de corte, que si se retiran, desconectarían al grafo en componentes.
Desigualdad de Whitney: Para cualquier grafo se cumple:
$$\kappa(G) \leq \lambda(G) \leq \delta(G)$$
(Donde $\delta(G)=\mathbf{min}\{\mathbf{gr}(v)|v\in V\}$ ($\mathbf{gr}(v)$ es el grado del vértice $v$) es el grado mínimo del grafo).
Casos Especiales
Grafo Completo ($K_n$): Como todos están conectados con todos, es el más robusto. Para desconectarlo, hay que eliminar casi todos los nodos hasta ejar solo uno. Por tanto, $\kappa(K_n) = n – 1$.
Grafos $k$-conexos: Se dice que un grafo es $k$-conexo si su conectividad $\kappa(G) \geq k$. Esto garantiza que la red soporta al menos $k-1$ allos sin fragmentarse.
Isomorfismo de grafos
Dados dos grafos \(G_1\) y \(G_2\) decimos que son isomorfos si existen dos aplicaciones biyectivas \(\Phi_V\) y \(\Phi_E\), entre sus vértices y sus aristas, de tal forma que si \((u,v)\) es una arista \(\Phi_E(u,v)=(\Phi_V(u),\Phi_V(v))\)
A veces resulta más sencillo identificar cuando no pueden ser isomorfos:
- Si dos grafos no tienen el mismo número de vértices, no pueden ser isomorfos. Lo mismo ocurre con el número de aristas.
- Si dos grafos no tienen la misma cantidad de vértices de un mismo grado, no pueden ser isomorfos
- La conexión se preserva bajo isomorfismo de grafos. Por tanto, si un grafo es conexo y el otro no, no pueden ser isomorfos.
- La existencia de ciclos de una longitud dada se preserva bajo isomorfismo de grafos. Así pues, si un grafo tiene un ciclo de una longitud y el otro no, no pueden ser isomorfos.
No obstante, que dos grafos tengan el mismo número de vértices y de aristas, la misma cantidad de vértices de un mismo grado, la misma cantidad de componentes conexas y la misma cantidad de ciclos de igual longitud, no demuestra que sean isomorfos.
Ejercicio: Determinar si son isomorfos los grafos siguientes
Ejercicio: Determinar si son isomorfos los grafos siguientes
| Ejercicio: Dado el grafo adjunto, ¿cuál es el grado del grafo?
|
