Grafos

República Bolivariana De Venezuela
Ministerio del Poder Popular Para La Educación Universitaria
Instituto Universitario de Tecnología de Maracaibo
PNF en Informática
Sección: 331D




















Prof.: Integrantes:
Mariela Moreno AtencioAdrian CI: 20.945.121
Barrios Marcos CI: 19.999.164
Genes Danny CI: 19.072.731
Primera Orlando CI: 21.752.000Sanchez Richard CI: 15.287.918



Maracaibo, Noviembre de 2013
Introducción:
Hoy en día podemos observar tantas cosas que nos pueden parecer de lo más cotidianas, existen muchos problemas en la vida real que involucran tanto, conjuntos discretos, como relaciones entre ellos. Así, por ejemplo, podría interesar observar de cuantas formas se puede viajar por carretera unaobservando y analizando el camino o esa trayectoria a través de los Grafos y la teoría de Grafos.

En este trabajo se tratará brevemente de explicar lo que son los grafos, sus tipos, y algunas derivaciones de ellos, así como su representación gráfica y en algunos casos, su representación y muchos problemas de tipo combinatorio, que se plantean en la ciencia de la computación, investigaciónde operaciones y ciencias físicas, pueden analizarse a través de las técnicas encontradas en un área relativamente nueva de la matemática, llamada teoría de grafos.














Definición de Grafo
Sea G un grafo. Un circuito que contiene todas las aristas de G recibe el nombre de circuito euleriano.
Lo anterior quiere decir que un circuito euleriano es una trayectoria queempieza y termina en el mismo vértice, pasa por cada vértice al menos una vez y sólo una vez por cada arista.
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 {a, b} o {b, a}, siendo a y b los vértices que une.
Si {a, b} es una arista, a los vértices a y b se les llama susextremos.

Tipos de Aristas
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 el mismo.


Aristas Cíclicas: Arista que parte de un vértice para entrar en el mismo.


Cruce: Son dos aristas que cruzan en un punto.






Vértices
Son los puntoso 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.
Tipos de Vertices
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 elvértice adyacente.





Vértice Aislado: Es un vértice de grado cero.



Vértice Terminal: Es un vértice de grado 1.





Caminos
Se llama Camino a una secuencia de vértices dentro de un grafo tal que exista una arista entre cada vértice y el siguiente. Se dice que dos vértices están conectados si existe un camino que vaya de uno a otro, de lo contrario estarán desconectados.Dos vértices pueden estar conectados por varios caminos.
El número de aristas dentro de un camino es su longitud. Un camino simple es aquel que no repite vértices en su recorrido.
Si un camino empieza y termina en el mismo vértice se le llama ciclo.









Historia de Grafos Eulerianos
Leonhard Paul Euler, conocido como Leonhard Euler, fue un matemático y físico suizo. Se trata del...