Teoría De Gráficas

[pic]

Teoría de gráficas

[pic]
[pic]

Aplicaciones de ecuaciones lineales y matrices
[pic]

Tanto en el campo de las matemáticas como en el de las ciencia de la computación la teoría de gráficas tiene como finalidad el estudiar las propiedades de las gráficas. En este breve trabajo haremos una exposición de los conceptos básicos que abarca dicha teoría. Primeramente podemos que eldesarrollo de la teoría comenzó con el trabajo de Leohard Euler en 1736 con su trabajo de los puentes de Königsberg. Aunque el trabajo de Euler es considerado como el primer avance de la teoría de gráficas el problema fue resuelto hasta un siglo después por Kenneth Apper y Wolfgang Haken.

Gráficas no dirigidas

Una gráfica no dirigida está conformada por un conjunto de vértices, V, y unconjunto de aristas, E. Cada arista está asociado a un par ordenado de vértices. Si existe una arista E asociada con los vértices V1 y V2 se denota de la siguiente manera:

E=(V1,V2) y diremos que la arista E es incidente a los vértices V1 y V2.


Ejemplo de gráfica no dirigida












Gráficas dirigidas

Una gráfica dirigida, también conocida como digráfica se forma por unconjunto finito de puntos P1,P2..............Pn que reciben el nombre de vértices, V, junto con un conjunto finito de aristas o lados, E, dirigidos. Cada uno de los aristas une un par ordenado de vértices distinto. Dado que ninguno de los vértices de una diagráfica puede estar unido a el mismo por medio de una sola arista dirigida por lo que decimos que no hay lazos.

La gráfica de la izquierdamuestra un lazo, un vértice unido por medio de una sola arista. Una gráfica dirigida NO tiene lazos.





Supondremos que no hay aristas con múltiples direcciones que unan a cualquier par de vértices.

Ejemplo de gráficas dirigidas

G=(V,E) V=vértices E= aristas







Matrix de incidencia
El objetivo de la matriz de incidencia es como su nombre lo indica determinar laincidencia que corresponde a las aristas con los vértices, es decir cómo se conectan los vértices con alguna arista.

Para construir esta matriz de incidencia colocamos en las filas los vértices (representados con las letras: a, b, c, d, y así sucesivamente hasta colocar todos los vértices del grafos dado) y en las columnas las aristas (representados con la letra: e1, e2, e3,….. en)

Ejemplo:Determina la matriz de incidencia del siguiente modelo de grafos









[pic]

[pic]

Esta Matriz de Incidencia nos indica que:

Los vértices a y b son adyacentes por la arista e1
Los vértices a y c son adyacentes por las aristas e2 y e3
Los vértices b y c son adyacentes por la arista e4
El vértice c no es adyacente con otro vértice por la arista e5 es un lazoVértices adyacentes, matriz de adyacencia

Decimos que dos vértices son adyacentes si son los extremos de una arista, es decir, si el par de vértices V es un elemento de E. Si G es una diagráfica que tiene n número vértices , la matriz A(G) de (n x n) es una matriz de adyacencia en la cual se representa por medio de un 1 la existencia de una arista dirigida de V1 a V2 y con un 0 en el caso contrario.En el caso de que la gráfica sea no dirigida y tengamos un lazo entonces se suma un 2 en vez de 1. Debemos tener en cuenta que A(G) no es necesariamente una matriz simétrica pero para un gráfica no dirigida la matriz de adyacencia es simétrica.

Ejemplo


[pic]














Como podemos deducir delo que hemos estudiado anteriormente, la matriz de adyacencia provee toda la información necesaria para la construir la gráfica puesto que nos proporciona el grado del vértice y nos indica como se conectan los vértices. Por otra parte denominamos isomorfos a dos gráficas que tienen la misma adyacencia.

En la realidad la teoría de gráficas es utilizada en muchas casos para determinar los...