Grafos
1) Un conjunto finito V de elementos llamados vértices (Nodos, Puntos).2) Un conjunto E de aristas tales que cada arista e ε E esta identificada por un único par (desordenado) [u,v] de nodos de V denotado como e = [u,v].
3) Un grafo se denota como G = (V, E).
4)NODOS VECINOS O ADYACENTES: Dos nodos son vecinos si existe una arista que los una.
5) E = (u, v) los vértices u, v son vecinos.
6) EL GRADO DE UN NODO U: es el número de aristas que contienena u.
7) NODO AISLADO: Son aquellos nodos que tienen grado 0.
8) GRAFO ETIQUETADO: Es un grafo donde cada arista tiene un valor asignado.
Ejemplo de grafos:
Miami
Las Vegas
Los ÁngelesPortland
Chicago
New York
Las aristas no están ordenadas lo que significa que:
( Los Ángeles, Chicago) = ( Chicago, Los Ángeles)
( u1, v2) = (u2, v1)
Grado (Los Ángeles) = 2
Grado(Chicago) = 3
Grado de Portland = 0
* Grafodirigido
Un grafo dirigido es una estructura de datos no lineal que consta de:
* Un conjunto finito de elementos llamados vértices.
* Un conjunto Ede aristas con orientación (flechas) que conectan a 2 nodos.
Miami
Los Ángeles
Portland
Chicago
New York
Terminología:
Un camino P de longitud n desde UhastaV es una secuencia de n+1 nodosescrita como: P (V0,V1,…,Vn).
Donde:
* U = V0
* Vi es adyacente a Vi-1 para toda i = 1, 2, …, n
* V = Vn
Bucle: Conexión de un vértice consigo mismo.
Camino Cerrado: Es un...
Regístrate para leer el documento completo.