tareas

Grafos
Uno de los primeros resultados de la teoría de grafos fue el que obtuvo Leonhard Euler en el siglo XVIII al resolver el problema de los puentes de Konigsberg. El problema consiste en recorrer 7 puentes que conectan 4 porciones de tierra bajo la condición de pasar por cada puente una sola vez.
Euler represento el problema por medio de una figura a la llamó “GRAFO”.
“VÉRTICE”: porcionesde tierra representadas por un punto.
“ARISTAS”: puentes representados por líneas.
“ORDEN DEL VERTICE”: número de líneas que salen o entran a un vértice.
Euler llego a la conclusión de que es imposible obtener un itinerario que salga de un vértice y regrese a él pasando por todas las aristas solamente una vez.

Los grafos son representaciones de las redes, y por medio de ellos se puedeexpresar en forma visual y sencilla una relación entre elementos de distinto tipo. Por medio de la teoría de los grafos, se pueden aprovechar mejor los recursos eliminando conexiones redundantes y reduciendo costos y distancias.

Partes de un grafo…
Un grafo (G) es un diagrama que consta de un conjunto de vértices (V) y un conjunto de lados (L).

Vértices (nodos): se indican por medio de un pequeñocírculo y se les asigna una letra.
Lados (ramas o aristas): son las líneas que unen un vértice con otro y se les asigna una letra, un número o una combinación de ambos.
lados paralelos: son aquellas aristas que tienen relación con un mismo par de vértices.
Lazo: es aquella arista que sale de un vértice y regresa al mismo vértice.
Valencia de un vértice: es el número se lados que salen oentran a un vértice.




Tipos de grafos…
Grafos simples: son aquellos grafos que no tienen lazos ni lados paralelos.








Grafo completo de n vértices (Kn): es el grafo en donde cada vértice está relacionado con todos los demás, son lazos ni lados paralelos. Se indica como Kn, en donde n es el número de vértices del grafo.

Complemento de un grafo (G´): es el grafo que le falta algrafo G, de forma que entre ambos forman un grafo completo de n vértices. Este grafo no tiene lazos ni ramas paralelas.







Grafo bipartido: es el grafo que está compuesto por dos conjuntos de vértices, en donde los elementos del conjunto A se relacionan con los del conjunto B.

Grafo bipartido completo (Kn, m): está compuesto por dos conjuntos de vértices, en el que cada vértice de Aesta unido con todos los vértices de B.
Grafo conexo: es aquel en que para cualquier para de vértices w, x, distintos entre sí, existe un trayecto para ir de w a x.


Caminos y circuitos…
En un grafo se puede recorrer la información de diferente manera, lo cual implica seguir distintas rutas para llegar de un nodo del grafo a otro.
Camino: es una sucesión de lados que van de un vértice x aun vértice w (dichos lados se pueden repetir).
Circuito (ciclo):en un camino del vértice w al vértice w, esto es, un camino que regresa al mismo vértice de donde salió.
Circuito simple de longitud n:es aquel camino del vértice w al vértice w que solamente en la ruta que sigue.
Camino simple de longitud n:es una sucesión de lados que van de un vértice x a un vértice w, en donde los lados quecomponen dicho camino son distintos e iguales a n. esto significa que no se puede pasar dos veces por una misma arista.
Camino de Euler: es aquel que recorre todos los vértices pasando por todas las ramas una sola vez.
Circuito de Euler: es aquel ciclo que recorre todos los vértices pasando por todos los lados solamente una vez.
Circuito de Hamilton: es similar al circuito de Euler, con ladiferencia de que, en lugar de pasar solamente una vez por todos los lados del grafo, en el circuito de Hamilton se pasa por cada vértice solamente una vez.


Árboles
Uno de los principales problemas de los grafos es que no guardan una estructura establecida y que no respetan reglas, ya que la relación entre los nodos puede ser tan compleja como la misma naturaleza. Este es un problema cuando se...