Grafos

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.