Caminos y Grafos

CAMINOS
Un Camino es una secuencia de arista
que comienza en un vértice del grafo y
recorre ciertas aristas del grafo siempre
conectando
pares
de
vértices
adyacentes.

CAMINO SIMPLEA,d,c,f,e es un camino Simple de longitud
4, ya que {a,d}, {d,c}, {c,f}, {f,e} son aristas.
Sin embargo d,e,c,a no es un camino,
ya que {e,c} no es una arista.
d

e

f

CONEXIÓN EN GRAFOS NODIRIGIDOS
Se dice que un grafo dirigido es conexo si
hay un camino entre cada par de vértices
distintos del grafo
Hay un camino simple entre cada par de
vértices distintos de un grafo no dirigidoconexo

CONEXIÓN EN GRAFOS NO
DIRIGIDOS
G1: es un grafo conexo ya
que entre cada, par de
vértices hay un camino

G2: NO es un grafo conexo ya
que “a” NOSE CONECTA CON
“d”

COMPONENTESCONEXAS
Cuando un grafo no es conexo, es la unión de dos o mas
subgrafos conexos que no tienen ningún vértice en común.

VERTICES Y ARISTAS DE
CORTE

Eliminar un vértice de corte en un
grafoconexo produce un subgrafo
que no es conexo.
Eliminar una arista produce un grafo
con mas componentes conexas que el
grafo anterior.

CONEXIÓN EN GRAFOS
DIRIGIDOS
FUERTEMENTE

CONEXO: si hayun camino
de a a b y de b a a para cualesquiera dos
vértices A y B del grafo
Para

que un grafo sea fuertemente conexo tiene
que haber una secuencia de aristas dirigidas desde
cualquiervértice del grafo a cualquier otro vértice, un
grafo dirigido puede no ser fuertemente conexo pero
estar formado por una sola pieza.

DEBILMENTE

CONEXO: si hay un camino

entre cada dos vérticesUn

grafo es débilmente conexo si, y solo si, hay
siempre un camino entre dos vértices cuando se ignoran
las direcciones de las aristas, claramente cualquier
grafo dirigido fuertemente conexotambién es
débilmente conexo.

CAMINOS E ISOMORFISMO
Los

caminos y circuitos son muy
útiles a la hora de determinar si dos
grafos son o No son isomorfos.
Para

determinar que dos...