Recorrido de Grafos

Grado de un Vértice

El grado de un vértice es el número de aristas o conexiones que tiene un nodo con otros nodos.

\[\delta(v) = \text{número de aristas incidentes en } v\]

Existe una propiedad matemática que establece que la suma de los grados de todos los vértices de un grafo es igual al doble del número de aristas del grafo:

\[\sum \delta(v) = 2 |E|\]

Caminos

Un camino es una secuencia de vértices conectados por aristas, que permite ir de un nodo a otro a través de las conexiones del grafo.

NOTA

Si en un grafo hay más de dos vértices con grado impar, es imposible recorrer cada una de las aristas sin repetir nodos.

Caminos, Cadenas y Ciclos

  • Cadena: Es una sucesión de vértices y aristas donde las aristas pueden repetirse, pero no necesariamente los vértices.

  • Camino: Es una sucesión de vértices y aristas donde no se repite ningún vértice ni arista.

  • Ciclo: Es un recorrido que comienza y termina en el mismo vértice, sin repetir aristas.

  • Cadena Cerrada: Es un ciclo en el cual se pueden repetir vértices, pero no aristas.

Conectividad en Grafos

  • Grafo Conexo: Un grafo es conexo si existe al menos un camino entre cada par de vértices. En otras palabras, todos los nodos están interconectados.

  • Grafo No Conexo: Un grafo es no conexo si existe al menos un par de vértices entre los cuales no hay camino. Es decir, el grafo está dividido en componentes desconectados.

Referencias




    Enjoy Reading This Article?

    Here are some more articles you might like to read next:

  • Introducción a los Comandos
  • Interfaces de Usuario en los Sistemas Operativos
  • Introducción a Linux
  • Introducción a los Sistemas Operativos
  • Vim CheatSet
  • Sistemas Numéricos