Grafos

Solo disponible en BuenasTareas
  • Páginas : 4 (873 palabras )
  • Descarga(s) : 0
  • Publicado : 21 de febrero de 2012
Leer documento completo
Vista previa del texto
Grafos En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos (también llamadas gráficas). Un grafo es unconjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas (dejes en inglés) que pueden ser orientados o no. Típicamente, un grafo se representamediante una serie de puntos (los vértices) conectados por líneas (las aristas) a continuación unos puntos importantes.
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...
tracking img