Grafos

martes, 26 de julio de 2011 1 comentarios
GRAFOS 
Un grafo está formado por un conjunto de nodos(o vértices) y un conjunto de arcos. Cada 
arco en un grafo se especifica por un par de nodos.  

  

arco
nodo
Si los pares de nodos en los arcos dirigidos, el grafo se denomina grafo directo, dirigido o 
dígrafo. 

TERMINOLOGÍA 
 
*.-Al número de nodos del grafo se le llama orden del grafo. 
*.-Un grafo nulo es un grafo de orden 0 (cero). 
*.-Dos nodos son adyacentes si hay un arco que los une. 
*.-En un grafo dirigido, si A es adyacente de B, no necesariamente B es adyacente de A  
*.-Camino es una secuencia de uno o mas arcos que conectan dos nodos.  
*.-Un grafo se denomina conectado cuando existe siempre un camino que une dos   
     nodos cualesquiera y desconectado en caso contrario. 
*.-Un grafo es completo cuando cada nodo esta conectado con todos y cada uno de los   
     nodos restantes. 
*.-El camino de un nodo así mismo se llama ciclo
*.-Un grafo sin ciclos es un árbol.  
*.-El entregado de un nodo indica el número de arcos que llegan a se nodo. 
*.-El fuera de grado de un nodo indica el número de arcos que salen de él. 
*.-Un grafo de N vértices o nodos es un árbol si cumple las siguientes condiciones 
     a) Tiene N-1 arcos                    
     b) Existe una trayectoria entre cada par de nodos. 
     c) Esta mínimamente conectado.

GRAFOS Y SUS APLICACIONES 

INTRODUCCIÓN  
Este capítulo profundiza en otra estructura de datos no lineal: el grafo. Como hemos hecho 
con otras estructuras de datos. Discutiremos la representación de los grafos en memoria y 
presentaremos varias operaciones y algoritmos sobre ellos. En particular discutiremos la 
búsqueda en anchura y la búsqueda en profundidad para nuestros grafos. También se 
repasaran ciertas aplicaciones de los grafos, incluyendo la ordenación topológica.  

TERMINOLOGÍA DE TEORÍA DE GRAFOS  
  
Esta sección recoge alguna de la terminología  principal asociada con la teoría de grafos 
por tanto advertimos al lector de que nuestras definiciones pueden ser ligeramente 
diferentes de las definiciones usadas en otros textos de estructuras de datos y teoría de 
grafos.
  
GRAFOS Y MULTIGRAFOS  
Un grafo G consiste en dos cosas:  
 (1) Un conjunto V de elementos llamados nodos (o puntos o vértices)  
 (2) Un conjunto E de aristas tales que cada arista e de E esta identificada por un único    
       (desordenado) par [u,v] de nodos de V, denotado por e-[v,u]. 
A veces denotamos un grafo escribiendo G=(V,E) 
Suponga que e =[u,v]. entonces los nodos u y v se llaman extremos de e, y u y v se dice 
que son nodos adyacentes o vecinos. El grado de un nodo u, escrito grad(u), es el número 
de artistas que contienen a  u.si grad(u)= 0, o sea, si u no pertenece a ninguna arista--- 
entonces se dice que u es un nodo aislado.  
Un camino P de longitud n desde un nodo u se define como la secuencia de n +1 nodos. 

1 comentarios:

Publicar un comentario

Deja tu Comentario.

 

©Copyright 2011 trinisoft | TNB