Teoría de Grafos: Nodos, Aristas y Grados

Definición y notación en la teoría de grafos

• Un grafo GG se define como un par ordenado G=(V,E), donde V es el conjunto de vértices o nodos.
• E es el conjunto de aristas o arcos, que representan conexiones entre pares de vértices.
• Los servidores de una red informática pueden ser representados como vértices, y las conexiones entre ellos como aristas.

Grado de un vértice

• El grado de un vértice se define como el número de aristas que inciden en él.
• En una red social, el grado de un usuario refleja la cantidad de amigos o conexiones directas que posee.

Vértices: aislado y adyacente

• Vértice aislado: No tiene ninguna arista incidente.
• Vértices adyacentes: Dos vértices son adyacentes si están conectados por una arista.
• Dentro de una red Wi-Fi, un dispositivo desconectado representaría un vértice aislado.
• Dos computadoras conectadas a una red son vértices adyacentes.

Trayectoria y Circuito

• Trayectoria: Secuencia de vértices donde cada par consecutivo está conectado por una arista.
• Circuito: Es una trayectoria que comienza y termina en el mismo vértice.
• El recorrido de paquetes de datos entre routers en una red forma una trayectoria y si este paquete regresa al origen se forma un circuito.

Grafos conexos y disconexos

• Grafo conexo: Existe al menos una trayectoria entre cualquier par de vértices.
• Grafo disconexo: Hay al menos un par de vértices que no están conectados entre sí.
• Una red informática en la que todos los dispositivos están conectados es conexa.
• Si existen dispositivos desconectados, esto forma un grafo disconexo.

Subgrafos y grafos cociente

• Subgrafo: Es un grafo formado por un subconjunto de vértices y aristas de otro grafo.
• Grafo cociente: Se obtiene al agrupar vértices de un grafo basándose en una relación de equivalencia.
• Un subgrafo puede representar solo los dispositivos de una red local dentro de una red global.
• Un grafo cociente puede representar grupos de servidores agrupados por ubicación geográfica.

Trayectorias y circuitos de Euler

• Trayectoria de Euler: Recorrido que utiliza cada arista exactamente una vez.
• Circuito de Euler: Es una trayectoria de Euler que comienza y finaliza en el mismo vértice.
• La optimización de conexiones de red para asegurar la visita a cada nodo solo una vez, sin repetir rutas, se considera una trayectoria/circuito de Euler.

Trayectorias y circuitos Hamiltonianos

• Trayectoria Hamiltoniana: Recorrido que visita cada vértice exactamente una vez.
• Circuito Hamiltoniano: Es una trayectoria Hamiltoniana que comienza y termina en el mismo vértice.
• Los algoritmos de optimización para la planificación de rutas de mensajería en redes distribuidas son un ejemplo de aplicación.