CONTENIDO

DEFINICION DE GRAFOS

SUBGRAFOS

GRADO DE UN VERTICE

CAMINOS, CICLOS

REPRESENTACION DE LAS GRAFICAS

RUTA MAS CORTA

GRAFO

UN GRAFO ES UNA PAREJA DE CONJUNTOS (V, E)

DONDE:

V ES DISTINTO DE VACIO

E ES UN CONJUNTO DE PARES DE V

TERMINOLOGIA

BASICA

GRAFOS NO DIRIGIDOS

LOS ELEMENTOS DE (V) SE LLAMAN VERTICES O NODOS.

LOS PARES DE (E) SON NO ORDENADOS, SE LLAMAN ARISTAS

SE REPRESENTAN CON PUNTOS Y LINEAS

EJEMPLO

V5

V4

V2

V1

V3

V = {V1,V2,V3,V4,V5}

E =

{(V1,V1),(V1,V2),(V1,V5),(V2,V3),

(V2,V4),(V2,V5),(V3,V4),(V4,V5)}

PARES NO ORDENADOS DE

VERTICES

GRAFO NO DIRIGIDO

TERMINOLOGIA

BASICA

GRAFOS DIRIGIDOS

LOS ELEMENTOS DE (V) SE LLAMAN VERTICES O NODOS.

LOS PARES DE (E) SON ORDENADOS, SE LLAMAN ARCOS

SE REPRESENTAN CON PUNTOS Y FLECHAS

GRAFO DIRIGIDO

EJEMPLO

V2

V1

V4

V3

V5 V = {V1,V2,V3,V4,V5}

E =

{(V1,V2),(V2,V3),(V3,V1),(V3,V4),

(V4,V3),(V4,V4),(V4,V5),(V5,V1)}

PARES ORDENADOS DE

VERTICES

MAS NOTACION

GRAFOS NO DIRIGIDOS

SI (Vi, Vj) REPRESENTAN UNA ARISTA

Vi Y Vj SON EXTREMOS DE (Vi,Vj)

Vi Y Vj SON ADYACENTES

(Vi, Vj) ES INCIDENTE EN Vi Y Vj

SI Vi = Vj, (Vi,Vj) SE LLAMA BUCLE O LAZO

UN GRAFO SIN BUCLES O LAZOS SE LLAMA SIMPLE

EJEMPLO

V5

V4

V2

V1

V3

GRAFO NO DIRIGIDO

SI (Vi, Vj) REPRESENTAN UNA ARISTA

Vi Y Vj SON EXTREMOS DE (Vi,Vj)

Vi Y Vj SON ADYACENTES

(Vi, Vj) ES INCIDENTE EN Vi Y Vj

SI Vi = Vj, (Vi,Vj) SE LLAMA BUCLE O

LAZO

UN GRAFO SIN BUCLES O LAZOS SE

LLAMA SIMPLE

MAS NOTACION

GRAFOS DIRIGIDOS

SI (Vi, Vj) REPRESENTAN UN ARCO

Vi ES EL EXTREMO INICIAL DE (Vi,Vj)

Vj ES EL EXTREMO FINAL DE (Vi,Vj)

SI Vi = Vj, (Vi,Vj) SE LLAMA BUCLE O LAZO

GRAFO DIRIGIDO

EJEMPLO

V2

V1

V4

V3

V5

SI (Vi, Vj) REPRESENTAN UN ARCO

Vi ES EL EXTREMO INICIAL DE (Vi,Vj)

Vj ES EL EXTREMO FINAL DE (Vi,Vj)

SI Vi = Vj, (Vi,Vj) SE LLAMA BUCLE O LAZO

MAS NOTACION

GRAFO COMPLETO

ES AQUEL GRAFO CON n VERTICES

EXISTE UNA ARISTA ENTRE CADA PAR DE VERTICES

V4

V2

V1

V3

MAS NOTACION

GRAFO DE SIMILITUD O SUBGRAFO

SON AQUELLOS GRAFOS DE LOS QUE SE PUEDEN DERIVAR

SUBGRAFOS

V4

V2

V1

V3

V4

V3

V2

GRADO DE UN VERTICE

V1 = 2 V6 = 0

V2 = 3 V7 = 2

V3 = 4

V4 = 3

V5 = 2

V4

V2

V1

V3

V5

EL GRADO DE UN VERTICE

COMPRENDEN AL NUMERO DE ARISTAS QUE

INCIDEN EN EL VERTICE

V6 V7

CAMINO O

TRAYECTORIA

ES EL RECORRIDO DESDE UN Vo HASTA UN Vn

V4

V2

V1

V3

V5

V6

V1,V2,V3,V4,V5,V6

V1,V3,V2,V4,V5,V6

V1,V2,V3,V5,V4,V6

CICLOS

CICLO DE EULER

CICLO DE HAMILTON

CICLOS

CICLO DE EULER

RECORRE TODAS LAS ARISTAS DEL GRAFO SIN

REPETIRLAS

V4

V2

V1

V3

V5

V6

V1,V2,V3,V4,V2,V5,V4,V6,V5,V3,V1

CICLOS

CICLO DE HAMILTON

RECORRER TODOS LOS VERTICES SIN

REPETIRLOS EXCEPTO EL Vi y EL Vf QUE SON EL

MISMO

V4

V2

V1

V3

V5

V6

V1,V2,V4,V6,V5,V3,V1

V1,V2,V5,V6,V4,V4,V3,V1

TERMINOLOGIA

BASICA

REPRESENTACION DE GRAFICAS

MATRIZ DE ADYACENCIA

MATRIZ DE INCIDENCIA

TERMINOLOGIA

BASICA

MATRIZ DE ADYACENCIA

V2

V1

V3

V1 V2 V3

V

1 2 1 1V

2 1 0 2

V

3 1 2 0

TERMINOLOGIA

BASICA

MATRIZ DE INCIDENCIA

V1

V2

V3

e1

e3e2

e4

e5

e1 e2 e3 e4 e5

V1 1 1 1 0 0

V2 1 0 0 1 0

V3 0 1 1 1 1

RUTA MAS CORTA

LOS MÉTODOS QUE VAMOS A VER SON:

ALGORITMO DE DIJKSTRA

ALGORITMO DE FLOYD-WARSHALL