Please enable JavaScript.
Coggle requires JavaScript to display documents.
Teoría de Grafos image, image, image, image, image, image, image, image,…
Teoría de Grafos
Elementos, Características
y Componentes
Vértices
Puntos o nodos
Poseen un
grado
Par o
impar
Aislados o
Terminales
Pueden ser
adyacentes
Tipos de Grafos
Dirigidos
Aristas con
dirección
Arcos diferentes
No dirigidos
Arcos iguales
Direccion no
especifica
De cadena
Combina dirigidos
y no dirigidos
Simple
Completo
Bipartito
Pesado
Aristas
Líneas
de unión
Opcionalmente
dirigidas
Adyacentes, paraleas
ciclicas
Caminos
Sucesión finita
de aristas
De punto a punto
Representación de
los grafos
Matematica
Listas y
Matrices
Adyacencia
Vertices adyacentes
entre si
Para listas:
Cantidad total
n*n vertices
para matriz
Almacena valores
booleanos
0 si no conecta
a vertice
1 si conecta a
vertice
Incidencia
Representada por
[arista, vertice]
1 si conecta
con arista
0 si no conecta
con arista
Computacional
Sigue forma
matemática
Listas y
Matrices
Depende del
software
Lenguaje de
Programación
Estructura de
codigo
Entorno gráfico
Almacenamiento de
grafos
Consumo de memoria
Algoritmos de recorrido
y búsqueda
Conjunto de
instrucciones
Para encontrar
nodos
El camino más
corto
Propuesto por
Dijkstra
Arcos asociados
a pesos
Toma el camino
cuya suma sea
menor
De un punto
a otro
A lo ancho
Visita vertices
en orden
creciente
Cambia de vertice activo
Solo si no
es vacio
En profundidad
Visita vertices en
orden
decreciente
Avanza al vecino
menor
Similar a
"a lo ancho"
