Árboles y grafos

TEORÍA DE GRAFOS Y ARBOLES

¿Qué es un grafo?

Un grafo G consiste en un conjunto no vacío de vértices o nodos V y un conjunto de arcos o aristas E  G = (V,E). Grafo del griego grafos: dibujo e imagen.

Teoría de grafos 

Los grafos son estructuras discretas que aparecen ubicua mente en cada disciplina donde se requiere modelar algo, en general los grafos son mapas conceptuales que ayudan a representar el conocimiento.  Los grafos tiene muchas aplicaciones en problemas de ingeniería, computación, biología, física, urbanismo, comunicaciones, economía, redes sociales, entre muchas otras.

Aplicación de los grafos 

Aplicaciones de los grafos:  Internet y los protocolos de comunicaciones (TCP/IP, SMTP, FTP, routers, etc.)

 Diseño de redes de comunicaciones y transporte (redes computacionales, carreteras, aguas, electricidad, telecomunicaciones, aviación, satélites, aero-espacial, flotas de vehículos, etc.) 

Estructura de datos algoritmos computacionales navegador GPS (Google Maps.) Economía (bolsa, transacciones económicas, modelos de mercado, etc.)

Redes sociales (Facebook, Skype, MSN) Política y marketing, seguridad y prevención del terrorismo, inteligencia militar

propiedades 

Adyacencia: Dos aristas son adyacentes si tienen un vértice en común, y dos vértices son adyacentes si una arista los une.

Incidencia: Una arista es incidente a un vértice si ésta lo une a otro.

Ponderación: Corresponde a una función que asocia a cada arista un valor (costo, peso, longitud, etc.), para aumentar la expresividad del modelo.

Etiquetado: Distinción que se hace a los vértices y/o aristas mediante una marca que los hace unívocamente distinguibles del resto. 

Ejemplos

Arboles 

En ciencias de la computación y en informática, un árbol es un tipo abstracto de datos amplia mente usado que imita la estructura jerárquica de un árbol, con un valor en la raíz y subárboles con un nodo padre, representado como un conjunto de nodos enlazados.

Aplicación de los arboles 

La estructura de árbol, independientemente de si se trata de árboles binarios, AVL o B, se usa principalmente para guardar la información organizada de tal manera que sea posible tener un rápido acceso a ella. La diferencia principal que permite decidir qué tipo de árbol usar depende de la forma en que está estructurada la información, pero sobre todo del volumen de la misma ya que cuando es posible manipular la información en memoria principal, los árboles binarios y AVL son recomendables.

propiedades de los arboles 

Todo árbol es a su vez un grafo con un conjunto numerable de vértices es un grafo plano. 

Todo grafo conexo G admite un árbol de expansión, que es un árbol que contiene cada vértice de G y cuyas aristas son aristas de G.

Ejemplos: