Grafos

1. INSTITUTO UNIVERSITARIO TÉCNOLOGICO “ANTONIO JOSÉ DE SUCRE” Barquisimeto – Estado Lara ÁLGEBRA I Bachiller: Geraldine Cadevilla C.I: 17625053 Escuela: Informática

2. INSTITUTO UNIVERSITARIO TÉCNOLOGICO “ANTONIO JOSÉ DE SUCRE” Barquisimeto – Estado Lara GRAFOS Barquisimeto, 30 de enero de 2012.

3. Grafos Def . 1: Un grafo “G” está formado por un conjunto de vértices v es distinto vacío v = {v1,v2,……… vn } y un conjunto “A” de aristas o lados, en donde a cada arista se le asigna un par no ordenado ( u,v ) con u,v en V tal que A = {a1, a2,…. an } Notación: G = [ V ,A] Representación Geométrica: Def . 2: Dado un grafo G = [ V ,A] se tiene lo siguiente: a u v

4. La multiplicidad del par ( u,v ) se define como el número de aristas entre “u” y “v”. Notación m( u,v ). Una arista “a” es un lazo si existe v en V tal que a = ( v,v ). Dos aristas a y b son paralelas si existen u,v en V tal que: a = ( u,v ) = b. Una arista a en A incide en un vértice “v”, si “v” es extremo de “a”. El grado de un vértice v en V, denotado por g(v), representa el número de aristas que inciden en “v”. Dos vértices “u” y “v” son adyacentes si y solo si existe una arista a en A con extremos “u” y “v”. Ges un grafo nulo si a es igual a vacío.

5. En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de las gráficas ) estudia las propiedades de los grafos (también llamadas gráficas ). Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas que pueden ser orientados o no. Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).

6. Representación Matricial de Grafos:

7. Matriz de Adyacencia y Matriz de Incidencia: Dado un grafo G = [ V ,A] en donde v = {v1,v2,……… vn } y A = {a1, a2,…. an } se define: a) Matriz de adyacencia , como la matriz cuadrada nxn cuya componente con fila “i” y columna “j” la representa el número m( vi,vj ). b) Matriz de incidencia , como la matriz de orden mxn cuya componente con fila “i” columna “j” se define como la incidencia de la arista ai con respecto al vértice vj .

8. Grafos Eulerianos y Grafos Hamiltonianos :

9. Grafos Eulerianos : un grafo G = [V,A] conexo es euleriano si y solo si existe un ciclo en G que recorre todas las aristas. Si existe una cadena simple que recorra todas las aristas de G, diremos que el grafo es Semi-euleriano . Grafos Hamiltonianos : un grafo G = [V,A] conexo entonces G es hamiltoniano si existe un ciclo elemental que recorre todos los vértices. G es Semi-hamiltoniano si existe una cadena elemental que recorre todos los vértices.

10. Un ciclo es una sucesión de aristas adyacentes, donde no se recorre dos veces la misma arista, y donde se regresa al punto inicial. Un ciclo hamiltoniano tiene además que recorrer todos los vértices exactamente una vez (excepto el vértice del que parte y al cual llega). Por ejemplo, en un museo grande, lo idóneo sería recorrer todas las salas una sola vez, esto es buscar un ciclo hamiltoniano en el grafo que representa el museo (los vértices son las salas, y las aristas los corredores o puertas entre ellas). Se habla también de camino hamiltoniano si no se impone regresar al punto de partida, como en un museo con una única puerta de entrada. Por ejemplo, un caballo puede recorrer todas las casillas de un tablero de ajedrez sin pasar dos veces por la misma: es un camino hamiltoniano . Ejemplo de un ciclo hamiltoniano en el grafo del dodecaedro.

11. Árboles: Un grafo G1 = [V1,A1] es un subgrafo de G = [V,A] si y solo si V1 es subconjunto de V y tambiés A1 es subconjunto de A. un grafo T = [V,A] es un árbol si no posee ciclos y es conexo. S i T es un grafo con n mayor igual a 2, entonces: T es un árbol si y solo si T es conexo y todas sus aristas son puentes. Si T es un árbol con n vértices entonces n es mayor igual a 2 entonces T tiene n-1 aristas.

12. Un subgrafo H de un grafo conexo Gse denomina “árbol generador” si se cumplen las siguientes condiciones: 1) H es un árbol. 2) H posee todos los vértices de G.

13. Aplicaciones: Gracias a la teoría de grafos se pueden resolver diversos problemas como por ejemplo la síntesis de circuitos secuenciales, contadores o sistemas de apertura. Se utiliza para diferentes áreas por ejemplo, Dibujo computacional, en toda las áreas de Ingeniería. Los grafos se utilizan también para modelar trayectos como el de una línea de autobús a través de las calles de una ciudad, en el que podemos obtener caminos óptimos para el trayecto aplicando diversos algoritmos como puede ser el algoritmo de Floyd. Para la administración de proyectos, utilizamos técnicas como PERT en las que se modelan los mismos utilizando grafos y optimizando los tiempos para concretar los mismos.

14. La teoría de grafos también ha servido de inspiración para las ciencias sociales, en especial para desarrollar un concepto no metafórico de red social que sustituye los nodos por los actores sociales y verifica la posición, centralidad e importancia de cada actor dentro de la red. Esta medida permite cuantificar y abstraer relaciones complejas, de manera que la estructura social puede representarse gráficamente. Por ejemplo, una red social puede representar la estructura de poder dentro de una sociedad al identificar los vínculos (aristas), su dirección e intensidad y da idea de la manera en que el poder se transmite y a quiénes. Los grafos son importantes en el estudio de la biología y hábitat. El vértice representa un hábitat y las aristas representa los senderos de los animales o las migraciones. Con esta información, los científicos pueden entender cómo esto puede cambiar o afectar a las especies en su hábitat.