GRAFOS

Page 1

GRAFOS

GRAFOS

EN UN CAMINO NO DIRIGIDO O SIN DIRECION NO NECESARIAMENTE ES UN UNA SUCECION DE VERTICES Y ARISTAS

CAMINO CERRADO ES AQUE Q VUELVE AL ORIGEN

EN UN CAMINO ES SIMPLE O TIENE DIRECCION SE CUENTAS LAS ARISTAS

TEOREMAS

10.2 SI NO SE REPITE INA ARISTA EN EL CAMINO ES UN RECORRIDO

10.3 UN CIRCUTO ES DONDE EL RECORRIDO ES CERRADO OSEA VUELVE AL MISMO LUGAR DE RIGEN EL INICIO Y FIN ES EL MISMO VERTICE

10.4CUANDO NO SE REPITE NINGUN VERTICE SE DIE CAMINO SIMPLE

10.5CUANDO ES CERRADO SE DICE CAMINO CERRADO TAMBIEN

ISOMOSFISMOS DE GRAFOS

SON SUB GRAFOS DE UN GRAFO

CUANDO UNA VERTICE NO CONECTA SE DICE Q ES UN GRAFO NULO

ISOMORFISMO = ES CUANDO LA CANTIDAD DE VERTICES Y ARISTAS SON IGUALES

RA SABER SI SON ISOMORFOS DE DOS GRAFOS SE DEBE SACAR LA MARIS DE INCIDENCIA Y SI ESTAS MATRICES SON IGUALES ENTONCES SON ISOMORFOS

ESTUDIAR AL GRAFO NULO EXAMEN

RECORRIDOS Y CIRCUTOS EURELEANOS

ES CUANDO SI RECORRE TODAS LAS ARISTAS ES UN RECORRIDO EURELEANO Y SI ES RECORRIDO ES RECORRIDO EURELEANO

GRAFOS INDUCIDO

UN GRAFO INDUSIDO ES CUANDO UN SUBGADO Y APRTE DEBE ESTAR TODO CONECTADO OSEA TODOS LOS VERTICES DEBEN ESTAR UNIDOS COMO EL GRAFO PRINCIPAL

GRAFOS COMPLEMENTARIOS Y ISOMORFOS

SUS CONECCIONES SON IGUALES ADEMAS SU MATRIS DE INSIDENCIA ES LA MISMA

GRADO DE UN VERTICE

GRADO ES SEGUN LA CONECION Q TIENE CADA VERTICE ES DISTINTO EN NO DIRIGIDOS ES CAUNTEAS CONECONES TIENE Y EN DIRIGIDOS ES CUANTAS CONECCIONES DE SALIDA Y ENTRADA TENDRA EL VERTICE Y SE ANOTA GRADO DE SALIDA Y GRADO DE ENTRADA

GRADO DE UN GRAFO

SACAMOS LOS GRADOS DE TODOS LOS VERTICES DE UN GRADO Y EL GRADO MAYOR DE ESOS VERTICES SERA EL GRADO DEL GRAFO

GRAFO COMPLE,EULER,RUEDA

EXISTE UN CAMINO Q CONECTA DOS VERTICES OSEA EXTREMOS OSEA UN CAMINO DONDE LOS VERTICES SE CONECTAN MEDIANTE UN CAMINO

RECORRIDOS Y CIRCUTOS EUANOS

ES SI Y SOLO SI TODO SUS VERTICES SON PARES

CAMINOS Y CICLOS HMILTONIANOS

SE DEBE PASAR SOLO UNA VEZ POR TODOS LOS VERTISES NO INTERESA LAS ARISTAS

CICLO HAMILTONIANO ES PASAR POR TODOS LOS VERTICES

CPMLETO,EULER,HAMILTONIANO