grafos

UNIVERSIDAD ESTATAL A DISTANCIA

ESCUELA CIENCIAS EXACTAS Y NATURALES

CÁTEDRA DE MATEMÁTICA BÁSICA

Fundamentos de la matemática


CÓDIGO: 009





Ensayo: grafos y sus aplicaciones






Estudiante:
Mariela Vargas Rodríguez


Cédula:
3 377 493


Centro Universitario:
Siquirres



Fecha: 31/10/2013





III CUATRIMESTRE 2013


Grafos y susaplicaciones
Para comprender este tema es necesario una breve explicación o definición de que es un grafo. Un grafo es un dibujo o imagen; en otros términos matemáticos es una grafica formada por un conjunto de vértices unidos por enlaces llamados aristas, lo cual permite el estudio de las interrelaciones entre unidades que interactúan unas con otras.
La manera de representar un grafo es por medio de unconjunto de puntos a los que se denominan vértices unidos por líneas llamadas aristas.
Para nadie es novedad observar en la vida cotidiana: carreteras, líneas telefónicas, líneas de televisión por cable, el transporte colectivo metro, circuitos eléctricos de las casas, automóviles, y tantas cosas mas.
Concepto: Un grafo, G, es un par ordenado de V y A, donde V es el conjunto de vértices onodos del grafo y A es un conjunto de pares de vértices, a estos también se les llama arcos o ejes del grafo. Un vértice puede tener 0 o más aristas, pero toda arista debe unir exactamente a dos vértices. Los grafos representan conjuntos de objetos que no tienen restricción de relación entre ellos. Un grafo puede representar varias cosas de la realidad cotidiana, tales como mapas de carreteras, víasférreas, circuitos eléctricos.
Aristas: Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos. Si la arista carece de dirección se denota indistintamente.
Aristas Adyacentes: Se dice que dos aristas son adyacentes si convergen en el mismo vértice.
• Aristas Paralelas: Se dice que dos aristas son paralelas si vértice inicial y el final son elmismo.
•Aristas Cíclicas: Arista que parte de un vértice para entrar en el mismo.
•Cruce: Son dos aristas que cruzan en un punto.
Ahora el siguiente paso es explicar cada uno de sus contenidos y como se presentan.
Vértices: Son los puntos o nodos con los que esta conformado un grafo. Llamaremos grado de un vértice al número de aristas de las que es extremo. Se dice que un vértice es `par' o`impar' según lo sea su grado.
Los hay en diferentes formas.
Vértices Adyacentes: si tenemos un par de vértices de un grafo (U, V) y si tenemos un arista que los une, entonces U y V son vértices adyacentes y se dice que U es el vértice inicial y V el vértice adyacente.
•Vértice Aislado: Es un vértice de grado cero.
•Vértice Terminal: Es un vértice de grado 1.
Durante la historia en la aplicaciónde los grafos se dieron varias reseñas por ejemplo al mencionar:
El juego del dodecaedro:
Breve historia: Se dice que el matemático irlandés William Hamilton (1805{1865) en el año 1857 invento un juego que consistía en buscar un recorrido que diera la vuelta al mundo, representado por un dodecaedro, visitando cada ciudad, correspondiente a un vértice del dodecaedro, una sola vez. Solamente sepodía desplazar de una ciudad a otra si los vértices correspondientes del dodecaedro estaban unidos por una arista.
El problema de decisión consistente en determinar si un grafo es ha miltoniano (contiene un ciclo que pasa una sola vez por cada vértice) es un problema de la clase NP-completo. Explicar brevemente y de una manera informal la clasicacion de los problemas de decisión en las clases P(problemas para los cuales se conoce un algoritmo de coste polinomico que los resuelve) y la clase NP (problemas para los cuales la verificación de la solución, una vez dada, puede hacerse en tiempo polinomico aunque la búsqueda de la misma pueda suponer un coste exponencial). Claramente la clase P esta contenida en la clase NP pero no se sabe si dicha inclusión es estricta aunque la creencia...