PARCIAL I GRAFOS

“Algraf Project con ejemplos”

PRESENTADO POR:

SEAN GEATE DE ALBA ACOSTA

PRESENTADO A:

ADÁN GÓMEZ SALGADO

FECHA DE ENTREGA:

21/12/2012

UNIVERSIDAD DE CÓRDOBA

PROGRAMA DE INGENIERÍA DE SISTEMAS

MONTERÍA - CÓRDOBA

2012

ALGRAF PROJECT

Nos encontramos ante una aplicación desarrollada para el departamento de Matemática

Aplicada I de la Escuela Técnica Superior de Ingeniería Informática de Sevilla, con el

objetivo de proporcionar una herramienta que ayude al desarrollo de las prácticas de las

asignaturas dedicadas al estudio de los grafos y la investigación.

La aplicación desarrollada mejora aspectos de la aplicación “Algraf” la cual ha sido punto

de partida de este proyecto, por lo que se mantiene la compatibilidad con versiones

anteriores.

Entre otras funcionalidades, se ha mejorado la interfaz de usuario y la manejabilidad de la

aplicación permitiendo al usuario modificar la visualización de los grafos con las

operaciones de zoom y centrado, así como configurar el tamaño y color de vértices y

aristas.

Además la aplicación permite generar documentación. Por una parte podemos guardar los

grafos como imágenes en distintos formatos *.bmp, *.jpg, *.gif y *.png. También podemos

generar documentación en formato pdf donde nos aparecerá el grafo y el conjunto de

vértices y aristas que lo forman.

Por otra parte, como la aplicación se ha realizado con fines didácticos se han puestos ciertos

contenidos teóricos en presentación de los resultados de la mayoría de los algoritmos para

facilitar al usuario la comprensión del problema que va resolver. Además se incluye un

manual exclusivamente de algorítmica sobre todos los problemas que resuelve la aplicación

con gran variedad de ejemplos.

La aplicación resuelve todos los problemas recogidos en versiones anteriores de “Algraf” y

se han incluido nuevos algoritmos dando solución a gran cantidad de problemas entre los

que podemos destacar:

Problema de rutas o trayectorias.

Problemas de ubicación.

Problemas de compatibilidades o coloración.

Problemas de minimización de costes.

Problemas de emparejamientos.

DESCARGAR E INSTALAR ALGRAF PROJECT

1. Descarga el programa Algraf Project en los enlaces de abajo y luego instalar.

Necesitaras el Paquete redistribuible de Microsoft® .NET Framework versión 1.1

para que el programa trabaje mejor.

Enlace de Algraf: https://forja.rediris.es/docman/view.php/130/100/index.html

Enlace del paquete .NET: http://www.microsoft.com/es-es/download/details.aspx?id=26

2. Ir a la aplicación y ejecútala, debe mostrarse como la siguiente imagen.

3. Clic en aceptar y deberá mostrar la siguiente ventana:

4. Ir a Archivo > Nuevo > Selecciona el tipo de grafo deseado.

5. La aplicación en ejecución se mostrara en la siguiente captura. Para comenzar a

utilizar las herramientas nos desplazamos a la parte superior del programa y listo a

resolver grafos se ha dicho.

A continuación realizaremos algunos ejemplos de operaciones entre grafos no dirigidos.

PARCIAL I GRAFOS

1. Tome 12 vértices de G6 y obtenga un subgrafo conexo que a la vez sea

Subgrafo Generado de G6 y luego determine:

a) Excentricidad de todos sus vértices

b) Su radio

c) Su centro

d) Su diámetro

e) Grado de todos sus vértices

Solución

El subgrafo conexo y generado de 12 vértices es el mismo grafo G6 pero lo llamaremos

subgrafo G6.1

a) La excentricidad de un vértice “Vi” es la longitud mayor del camino más corto entre

dicho vértice y cualquier otro. Para obtener su valor se han calculado longitudes de

todos los caminos mínimos desde "vi" al resto de vértices del grafo y se ha tomado

la longitud mayor.

Para el vértice V1 la excentricidad es la siguiente como se muestra en Algraf:

G6

Y para los demás vértices tenemos la siguiente excentricidad:

E(V2)= 3

E(V3)= 3

E(V4)= 4

E(V5)= 3

E(V6)= 3

E(V7)= 4

E(V8)= 3

E(V9)= 3

E(V10)= 4

E(V11)= 3

E(V12)= 3

b) El radio de un grafo es la excentricidad más pequeña por tanto el Radio G6.1 = 3

G6.1

G6.1

c) Centro: El centro de un grafo G, C (G) es el subgrafo inducido por los vértices que

tienen excentricidad mínima. Por tanto el centro de G6.1 esta formado por los

siguientes vértices que obtuvimos en la respuesta a):

E(V2)= E(V3)=E(V5)=E(V6)= E(V8)=E(V9)=E(V11)= E(V12)= 3

d) Diámetro: El diámetro de un grafo G es la excentricidad más grande de cualquiera

de sus vértices. (Diámetro = 4).

e) Grado de todos sus vértices: El grado de un vértice es el número de aristas que

inciden en el vértice. Y para los vértices del grafo G6 tenemos los siguientes grados.

G6.1

Grad(V1)= Grad(V4)=Grad(V7)= Grad(V10)=2

Grad(V2)= Grad(V3)= Grad(V5)= Grad(V6)= Grad(V8)= Grad(V9)= Grad(V11)=

Grad(V12)=4

2. Tome 9 vértices de G5 de tal forma que obtenga un subgrafo conexo que a la

vez sea máximal y regular. Para que después:

a) Determine la excentricidad de todos sus vértices

b) Determine su diámetro

c) Determine su radio

d) Determine su centro.

Solución

No podemos obtener a simple respuesta un subgrafo conexo de 9 vértices, que a la vez

sea máximal y regular ya que si quitamos cualquier vértice de G5 algunos vértices

quedaran con diferentes grados lo cual provocara que no se obtenga un subgrafo

máximal.

Pero podemos obtener lo que piden los enunciados usando 10 vértices el grafo G5:

a) Determine la excentricidad de todos sus vértices

G5

E(V1)= E(V2)= E(V3)= E(V4)= E(V5)= E(V6)= E(V7)= E(V8)= E(V9)= E(V10)= 2

b) El diámetro es 2

c) El radio es 2

d) Todos los vértices de G5 son centro ya que tienen la misma excentricidad

3. Tome 16 vértices de G7 y cree un subgrafo generador y conexo de G7 que a la

vez sea máximal de G7 para luego:

a) Obtener el grado de todos sus vértices

b) Hallar la distancia de cada vértice con respecto a todos sus demás compañeros

vértices

c) Excentricidad de todos los vértices

d) Centro del subgrafo

G7

a) Obtener el grado de todos sus vértices:

Grad(V1)= Grad(V5)=Grad(V12)= Grad(V16)=2

Grad(V2)= Grad(V3)=Grad(V4)= Grad(V6)= Grad(V7)= Grad(V8)=Grad(V9)=

Grad(V10)= Grad(V11)= Grad(V13)=Grad(V14)= Grad(V15)=3

b) Hallar la distancia de cada vértice con respecto a todos sus demás compañeros

vértices

Distancia de un vértice.

La distancia del vértice d(vi) en el grafo G, es la suma de las distancias mínimas a

todos los vértices del grafo.

d(v1) = d(v5)= d(v12) = d(v16) = 41

d(v2) = d(v4)= d(v6)= d(v7) = d(v10) = d(v11) = d(v13) = d(v15) =38

d(v3)= d(v8) = d(v9) = d(v14) = 39

c) Excentricidad de todos los vértices

E

(

V

1

)

=

E

(V5)=E(V12)= E(V16)= 5

E(V2)= E(V3)= E(V4)= E(V6)= E(V7)= E(V8)= E(V9)= E(V10)= E(V11)= 4

d) Centro del subgrafo: Son centro los siguientes vértices:

E(V2)= E(V3)= E(V4)= E(V6)= E(V7)= E(V8)= E(V9)= E(V10)= E(V11)= 4

4. Para los siguientes grafos determine.

G3 G4

a) G3 ∪ G4=?

b) Excentricidad de todos los vértices de G4

c) Centro de G3

Solución

a) G3 ∪ G4 = G4

b) Excentricidad de todos los vértices:

La excentricidad es la misma para todos los vértices

E(V1)= E(V2)= E(V3)= E(V4)= E(V5)= E(V6)= E(V7)= E(V8)= E(V9)= E(V10)=2

c) Centro de G3 son todos los vértices del grafo G3.

5. Para los siguientes grafos determine:

G1 G2

a) G1 ⊕ G2= ?

b) Radio (G1 ⊕ G2)= ?

c) Diametro (G1 ∩ G2) = ?

Solución

a) G1 ⊕ G2

G1 ⊕ G2

b) Radio (G1 ⊕ G2) es 3

c) Diámetro (G1 ∩ G2) : Hallamos la intersección (G1 ∩ G2)

El diámetro de (G1 ∩ G2) es 2 ya que los vértices tienen esa misma excentricidad 2

REFERENCIAS WEB

Algraf Project Aplicación para tratamiento de grafos [en línea]. [Fecha de consulta:

20 Diciembre 2012]. Disponible en:

https://forja.rediris.es/docman/view.php/130/100/index.html

Microsoft .NET Framework Version 1.1. Download Center [en línea]. [Fecha de

consulta: 20 Diciembre 2012].Disponible en:

http://www.microsoft.com/es-es/download/details.aspx?id=26