Scribd
Cargar
71 vistas11 páginas

GRAFOS

Un grafo representa un conjunto de nodos y las relaciones entre ellos mediante aristas. Casi cualquier problema puede representarse como un grafo. Un grafo se define como G=(V,E), donde V son los vértices o nodos y E son las aristas que conectan los vértices. El grado de un vértice es el número de aristas que lo conectan a otros vértices.

Cargado por

Tik Tok
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PPTX, PDF, TXT o lee en línea desde Scribd
71 vistas11 páginas

GRAFOS

Un grafo representa un conjunto de nodos y las relaciones entre ellos mediante aristas. Casi cualquier problema puede representarse como un grafo. Un grafo se define como G=(V,E), donde V son los vértices o nodos y E son las aristas que conectan los vértices. El grado de un vértice es el número de aristas que lo conectan a otros vértices.

Cargado por

Tik Tok
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PPTX, PDF, TXT o lee en línea desde Scribd

GRAFOS

Son un tipo abstracto de datos, consisten


en un conjunto de nodos y un conjunto de
aristas que establecen relaciones entre los
nodos.
Qué representan los grafos?
•Redes de computadoras
•Carreteras que unen ciudades
•Aerolíneas de vuelo
•Actividades de un proyecto
•Circuitos
•Mapas
•…

Prácticamente cualquier problema puede


representarse mediante un grafo.
Un grafo G=(V,E).
Donde V son los vértices (nodos)
V={V1,V2,V3,…}

V={1,4,5,7,9}

Donde E son los arcos y/o aristas


E={ViVj, VmVn,…}

E={(1,4), (4,9), (9,7), (7,5), (5,1),


(4,1), (9,4), (7,9), (5,7), (1,5)}
Grado de un grafo?
Es la sumatoria de los grados de los vértices
Grado de un vértice o nodo?
Es el número de aristas que utiliza para
conectar a otros vértices

Entonces:
Grado del Grafo=GradoD+GradoH+GradoE+GradoF+GradoC
Grado del Grafo= 3 + 3 + 4 + 3 + 3 = 16
Trayectorias en grafos
Un camino x desde V1 hasta V2,
es una secuencia finita de vértices
que empieza en V1 y termina en V2
Longitud es igual a la cantidad de
los arcos o aristas que lo forman.

Un camino cerrado es un camino que


inicia y termina en el mismo vértice.
Como condición no puede pasar
sobre la misma arista dos veces.
Grafo simple
No tiene arcos ni bucles

Multígrafo
Tiene arcos múltiples
paralelos o lazos
Grafo regular
Todos los vértices tienen
el mismo grado.
Ej: x=3, y=3, z=3, u=3

Grafo completo
Tiene un arista entre
cualquier par de vértices
Grafo incompleto
Contrario al completo, en este
grafo ausentan las aristas en
algunos pares de vértices.

Grafo bipartito
Significa que tiene dos partes.
Sus vértices se unen bajo las
siguientes condiciones:
•V1 y V2 son conjuntos disjuntos
•No existen aristas uniendo vértices
del mismo conjunto.
Grafo dirigido
Solo se puede recorrer la
información en el sentido dirigido.
E={(E,H), (H,E), (E,C), (C,D), (D,F)}

Grafo no dirigido
Se puede recorrer por las
aristas en ambos sentidos.
E={(1,4), (4,9), (9,7), (7,5), (5,1),
(4,1), (9,4), (7,9), (5,7), (1,5)}
Grafo ponderado
En éste, sus aristas contienen
datos (etiquetas). Una etiqueta
puede ser un nombre, costo ó
un valor de cualquier tipo de
dato. A el número asociado al
arco se le denomina factor de
peso.

Suposición: Si los vértices fueran ciudades, entonces los


números serían ponderaciones que podrían indicar los
kilómetros que existen de una ciudad a otra.
Por ejemplo: de la ciudad A a la ciudad H hay 10
kilómetros de distancia.
Grafo conexo
Un grafo conexo se caracteriza por que
todos sus vértices tienen una relación o
forma de comunicarse entre si

Conexo No Conexo

También podría gustarte