Scribd
Cargar
14 vistas7 páginas

Grafos

Un grafo es una estructura no lineal que modela relaciones entre objetos, compuesto por vértices y aristas. Las aristas pueden ser dirigidas o no dirigidas, y se utilizan términos como camino, peso y bucle para describir sus características. La matriz de adyacencia y la matriz de pesos son herramientas para representar la conexión y distancia entre los nodos en un grafo.

Cargado por

vegaalejandro412
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 PDF, TXT o lee en línea desde Scribd
14 vistas7 páginas

Grafos

Un grafo es una estructura no lineal que modela relaciones entre objetos, compuesto por vértices y aristas. Las aristas pueden ser dirigidas o no dirigidas, y se utilizan términos como camino, peso y bucle para describir sus características. La matriz de adyacencia y la matriz de pesos son herramientas para representar la conexión y distancia entre los nodos en un grafo.

Cargado por

vegaalejandro412
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 PDF, TXT o lee en línea desde Scribd

Grafos

ESTRUCTURAS DE INFORMACIÓN
Grafos
Un grafo permite modelar relaciones arbitrarias entre objetos.
Un grafo G=(V, A) es un par formado por un conjunto de vértices o Nodos, V, y
un conjunto de Arcos o Aristas, A. Cada arista es el par (u, w), siendo u,w dos
vértices relacionados.
Es una estructura no lineal que representa un conjunto de objetos donde no hay
restricción a la relación entre ellos.
Grafos

Arista / camino

Vértice / Nodo
Si los pares de nodos que
forman las aristas son
Dirigidos ordenados. Se representa
con flecha que indica la
dirección u  w
Grafos
Si las aristas están formadas
por pares de nodos no
No dirigidos
ordenados. Como el ejemplo
anterior u -- w
Términos
• Camino  Secuencia de vértices de un Grafo tal que exista
una arista entre cada vértice y el siguiente. Camino1= (a,b ,c)
camino2= (c,d)
• Vértice  También llamado Nodo.
• Arista  Conexión de un nodo con otro adyacente.
• Peso  distancia que hay de un vértice a otro.
• Bucle  Camino que une un nodo consigo mismo. Comienza y
termina en el mismo nodo.
• Orden  Es el número de nodos (vértices) del grafo.
Matriz de Adyacencia
Arreglo bidimensional, cuentan con un tamaño N.
En este caso si tenemos 5 nodos (vértices) , la matriz
será de 5 X 5
La matriz de adyacencia depende de la cantidad de
nodos.
Donde no existe arista se representa con un cero.
Matriz de pesos
Tiene en cuenta la distancia que existe entre los vértices

También podría gustarte