Grafos



Un grafo es un objeto matemático que se utiliza para representar circuitos, redes, etc. Los grafos son muy utilizados en computación, ya que permiten resolver problemas muy complejos.
Imaginemos que disponemos de una serie de ciudades y de carreteras que las unen. De cada ciudad saldrán varias carreteras, por lo que para ir de una ciudad a otra se podrán tomar diversos caminos. Cada carretera tendrá un coste asociado (por ejemplo, la longitud de la misma). Gracias a la representación por grafos podremos elegir el camino más corto que conecta dos ciudades, determinar si es posible llegar de una ciudad a otra, si desde cualquier ciudad existe un camino que llegue a cualquier otra, etc.

Consta de vértices (o nodos) y aristas. Los vértices son objetos que contienen información y las aristas son conexiones entre vértices. Para representarlos, se suelen utilizar puntos para los vértices y líneas para las conexiones, aunque hay que recordar siempre que la definición de un grafo no depende de su representación.
Un camino entre dos vértices es una lista de vértices en la que dos elementos sucesivos están conectados por una arista del grafo.El grafo será conexo si existe un camino desde cualquier nodo del grafo hasta cualquier otro. Si no es conexo constará de varias componentes conexas.
Fuente:
https://image.slidesharecdn.com/teoriadegrafos-120519092421-phpapp01/95/teoria-de-grafos-9-728.jpg?cb=1416524540
Un camino simple es un camino desde un nodo a otro en el que ningún nodo se repite. Si el camino simple tiene como primer y último elemento al mismo nodo se denomina ciclo.
Según el número de aristas que contiene, un grafo es completo si cuenta con todas las aristas posibles, disperso si tiene relativamente pocas aristas y denso si le faltan pocas para ser completo.
Las aristas son la mayor parte de las veces bidireccionales, es decir, si una arista conecta dos nodos A y B se puede recorrer tanto en sentido hacia B como en sentido hacia A: estos son llamados grafos no dirigidos. Sin embargo, en ocasiones tenemos que las uniones son unidireccionales. Estas uniones se suelen dibujar con una flecha y definen un grafo dirigido. Cuando las aristas llevan un coste asociado (un entero al que se denomina peso) el grafo es ponderado. Una red es un grafo dirigido y ponderado.

Fuente:
http://www.algoritmia.net/articles.php?id=18

Comentarios

Publicar un comentario

Entradas populares de este blog

Arboles Binarios

Imagen
En esta entrada hablare sobre los arboles binarios su definición de hijo, padre, hoja y raíz y mostrare como insertar nodos en una lista dinámica para crear un árbol binario. ¿Qué es un  árbol? Es una estructura de datos no lineal, debido a que cada elemento apunta a 1 o varios elementos del mismo tipo. El elemento que apunta se le conoce como padre y al elemento apuntado como hija. Todos los elementos a excepción de la raíz tiene un padre. ¿Que es un árbol binario? Es la estructura no lineal en la cual los elementos que contenga solo apunta de 1 a 2 elementos, conocidos como hijo izquierdo e hijo derecho.   Fuente: http://aniei.org.mx/paginas/uam/CursoPoo/Recursos/Imagen22.gif Recorridos de un árbol  Es la manera recursiva como pasaremos por cada nodo del árbol, existes tres formas: Enorden: Si visitamos primero hijo izquierdo, luego el padre y finalmente el hijo derecho Preorden: Primero el padre, luego el hijo izquierdo y finalmente el hijo ...
Leer más

Estructuras dinámicas lineales

Imagen
En este blog se explicara conceptos de variables dinámicas y punteros, con el motivo de tener un claro conocimiento sobre las estructuras dinámicas lineales. Estructuras dinámicas lineales Se dice que una estructura de datos es dinámica en el momento que se construye se utilizan variables dinámicas, variables cuya creación y eliminación se lleva acabo en tiempo de ejecución. La estructura dinámica mas sencilla son las listas simplemente enlazada, las cuales consisten en una simple secuencia de variables enlazadas mediante punteros. Una lista es una secuencia de elementos del mismo tipo, los elementos de dichas listas se les conoce como nodo, los cuales entre ellos existen una relación que permite pasar de una nodo a otro solo si este existe, la lista vacía es un tipo especial de lista, como su nombre lo indica es una lista que no contiene ningún dato. Un nodo contiene dos zonas de datos bien definidos, en una se almacena los datos, mientras en la otra un punte...
Leer más

Teoría de grafos y Biología Molecular

Este blog trata sobre algunos puntos importantes recibidos en la charla impartida en el Tecnológico de Costa Rica, hablaremos de conceptos que resaltan del tema Existen varios tipos de rutas para recorrer un grafo Ruta en un grafo: Secuencia de nodos tales que cada nodo Tiene un arco al siguiente nodo  Ruta simple: Rutas sin nodos repetidos  Ciclo en un grado: Ruta donde el primer nodo es igual al último nodo  Ciclo simple: Ciclo donde ningún modo se repite efecto el primero y el último  Ruta Hamilton: Simple que visita todos los nodos del grafo  Ciclo hamiltodiano: Ciclo simple que visité todos los modos del grado, existe un jugué de los años 80 que utilizaba este ciclo  Secuencias en biología molecular Las proteínas y los ácidos nucleicos se pueden modelar como hileras Frederick Sanger Bioquímico inglés, demostró que las proteínas tienen estructuras específicas. Gano un premio nobel en química 1958 y 1980. Único ganador de Dos premios ...
Leer más