parcial de grafos no dirigidos utilizando el programa algraf

PARCIAL I GRAFOS UNICORDOBA-LORICA

MAYRA MONTIEL Y NELA LOPEZ

PARCIAL I GRAFOS NO DIRIGIDOS EN ALGRAF

NELA LOPEZ MARTINEZ

MAYRA MONTIEL PASTRANA

PROFESOR:

ADAN GOMEZ

FACULTAD DE INGENIERIA DE SISTEMAS Y TELECOMUNICACIONES

UNIVERSIDAD DE CORDOBA

AREA:GRAFOS

LORICA-CORDOBA

2012



PARCIAL I GRAFOS

Primero que todo damos los paso de cómo entrar a este programa para resolver

los puntos del primer parcial de grafos.

Instalamos el programa a trabajar en este caso se llama algraf.

Luego le damos en la opcion archivo nuevo ; como podemos ver a continuacion

Luego le damos según la clase de grafos que se vaya a trabajar en este caso

grafos simples y le damos aceptar. Si el damso en la opcion de grafos etiquetados

las operaciones serian a sacar nos resultaria de otra forma por eso lo trabajamos

en simples utilizamos etiquetado solo para ponerles nombre a las aristas y para

hacer las respectivas operaciones lo trabajos como grafos simples .



Despues empezamos a crear nuestros grafos añadiendo los respectivos vertices

y aristas como se puede observa a continuacion

Y a su lado se pueden ver varias opciones como eliminar un grafo, una arista

como mover el grafo y otras cosas mas.



En la barra superor se encuentarn una serie de opciones a trabajar en este caso

las que utilizaremos seria la siguiente:

Donde se puede observar que se cuenta con opciones como sacar el radio,

diametro, centro, distancia y excentricidad las cuales son las que utilizaremos para

resolver el parcial

Aquí vemos como podemos ir añadiendo vertices y aristas utilizando el grafo

etiquetado para poner los nombres a estas.

Ahora si a lo que vinimos:



PRIMER PARCIAL DE GRAFOS

(OPERACIONES CON GRAFOS NO DIRIGIDOS)

1.

Obtener:

G1 U G2=?

Radio (G1 U G2)

Diametro (G1 G2)

A continuacion presentaremos la union de estos dos subgrafo

G1 G2



Radio (G1 U G2)=?

Se dice que

RADIO DE UN GRAFO. El radio de un grafo G es la excentricidad más pequeña de cualquiera de sus vértices. La excentricidad de un vértice "v" es la longitud mayor del camino más corto entre dicho vértice y cualquier otro. Se ha calculado la excentricidad de cada vértice y se ha tomado el menor valor. El valor del radio es 2.

Como podemos observar en el siguiente pantallazo:

G1 U G2



Ahora hacemos la intersección de estos dos subgrafos G1 y G2 para poder

hallarle su diámetro.

Diametro (G1 ∩ G2)



Donde se puede decir que :

DIAMETRO DE UN GRAFO. El diámetro de un grafo G es la excentricidad más grande de cualquiera de sus vértices. La excentricidad de un vértice "v" es la longitud mayor del camino más corto entre dicho vértice y cualquier otro. Se ha calculado la excentricidad de cada vértice y se ha tomado el mayor valor. El valor del diámetro es 2.

Como podemos ver a continuación que este es así:

G1 ∩ G2



2.

G3 G4



HALLAR :

G3⊕G4=?

Excentricidad de todos sus vértices de G3⊕G4

Centro (G3⊕G4)

Entonces tenemos el subgrafo obtenido de la SUMA ANILLO DE G3⊕G4

Le quisimos hacer las operaciones y como podrá comprobar el programa algraf

nos da como respuesta esto

G3⊕G4



Como este es un subgrafo no conexo ya que se encuentra un vértice aislado

como vemos el vértice V10; por lo tanto no se puede crear ni excentricidad ni

centro; Pero mas sin embargo le vamos hallar las operaciones que piden a la

componente conexa mas grande del grafo, en este caso seria este el subgrafo.



Procedemos a hallar la Excentricidad de todos sus vértices de G3⊕G4

Resultado de la excentricidad de v1= 3

Y asi hacemos con los demas vertices del subgrafo donde nos quedan que:



V1….E(V1)=3

V2…E(V2)=3

V3…E(V3)=3

V4…E(V4)=3

V5…E(V5)=3

V6…E(V6)=2

V7…E(V7)=3

V8…E(V8)=2

V9…E(V9)=2

DONDE

E(V1)=E(V2)=E(V3)=E(V4)=E(V5)=E(V7)=3

E(V6)=E(V8)=E(V9)=2

Ahora hallamos el Centro de (G3⊕G4)

CENTRO DE UN GRAFO. El centro de un grafo G, C(G) es el subgrafo inducido por los vértices que tienen excentricidad mínima. La excentricidad de un vértice "v" es la longitud mayor del camino más corto entre dicho vértice y cualquier otro. El centro esta formado por las aristas: Arista(v6, v8, 1). Arista(v6, v9, 1). Arista(v8, v9, 1).



3. Tome 7 vertices de G5 de tal forma que obtenga un subgrafo conexo que a la

vez sea maximal y luego:

1. determine la excentricidad de todos sus vertices

2. determine su diametro.

3. determine su radio

4. determine su centro.



Primero que todo definamos lo que es un subgrafo conexo y un subgrafo

maximal.

subgrafo conexo se dice conexo si, para cualquier par de vértices a y b en

G, existe al menos una trayectoria (una sucesión de vértices adyacentes

que no repita vértices) de a y b.

Un sugbrafo maximal es aquel que tiene la mayor cantidad de aristas que

relaciones con vertices de V’.

Tomando un subgrafo con 7 vertices tenemos :

G5

G5



Ahora determinamos la excentricidad de todos sus vertices:

1. EXCENTRICIDAD DE UN VERTICE. La excentricidad de "v1" 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 "v1" al resto de vértices del grafo y se ha tomado la longitud mayor.

Quedando como resultado que E(V1)= 3



Y asi hacemso con los demas vertices V2,V3,V4,V5….etc.

Como veamos a continuación el resultado de cada excentricidad de los vértices es

el siguiente:

V1….E(V1)=3

V2….E(V2)=3

V4….E(V4)=2

V6….E(V6)=2

V8….E(V8)=2

V9….E(V9)=3

V10..E(10)=3

Quedando entonces que :



E(V1)=E(V2)=E(V9)=E(V10)3

E(V2)=E(V4)=E(V6)=E(V8)=2

2. DIAMETRO DE UN GRAFO. El diámetro de un grafo G es la excentricidad más grande de cualquiera de sus vértices. La excentricidad de un vértice "v" es la longitud mayor del camino más corto entre dicho vértice y cualquier otro. Se ha calculado la excentricidad de cada vértice y se ha tomado el mayor valor. Resultando como diámetro de este subgrafo =3



3. RADIO DE UN GRAFO. El radio de un grafo G es la excentricidad más pequeña de cualquiera de sus vértices. La excentricidad de un vértice "v" es la longitud mayor del camino más corto entre dicho vértice y cualquier otro. Se ha calculado la excentricidad de cada vértice y se ha tomado el menor valor. Resultando como radio de este subgrafo el valor de =2

4. CENTRO DE UN GRAFO. El centro de un grafo G, C(G) es el subgrafo inducido por los vértices que tienen excentricidad mínima.



La excentricidad de un vértice "v" es la longitud mayor del camino más corto entre dicho vértice y cualquier otro. El centro esta formado por las aristas: Arista(v4, v6, 1). Arista(v6, v8, 1).



+++

4.

Tome 10 vertices de G6 y obtenga un subgrafo conexo que a la vez sea subgrafo

generador de G6 y luego determine:

1. Excentricidad de todos sus vertices

2. Su radio

3. Su centro

4. Su diametro



En este punto no se puede tomar solo 10 vértices ya que según las definiciones de

grafos no cumplen con esto porque decimos que un subgrafo conexo se dice

conexo si, para cualquier par de vértices a y b en G, existe al menos una

trayectoria (una sucesión de vértices adyacentes que no repita vértices) de a y b. y

un subgrafo generador es aquel que contiene el mismo numero de vértices.

Por lo tanto aremos estas operaciones con todos los vértices del grafo quedando

un subgrafo generador de G6 asi:

G6



Empezamos hallándole la excentricidad de todos sus vértices

Excentricidad de v1

Resultado de este es E(V1)=4



Y ASI PASARIA CON EL RESTO DE LOS VERTICES DEL GRAFO

E(V1)=4 E(V5)=4 E(V10)=4

E(V2)=4 E(V7)=6 E(V11)=4

E(V3)=5 E(V8)=5 E(V12)=5

E(V4)=6 E(V9)=4 E(V13)=5

ES DECIR

E(V1)=E(V2)=E(V5)=E(V9)=E(V10)=E(V11)=4

E(V3)=E(V8)=E(V12)=E(V13)=5

E(V4)=E(V7)=6



2. RADIO DE UN GRAFO.

El radio de un grafo G es la excentricidad más pequeña de cualquiera de sus vértices. La excentricidad de un vértice "v" es la longitud mayor del camino más corto entre dicho vértice y cualquier otro. Se ha calculado la excentricidad de cada vértice y se ha tomado el menor valor. El valor del radio es 4.



3. CENTRO DE UN GRAFO.

El centro de un grafo G, C(G) es el subgrafo inducido por los vértices que tienen excentricidad mínima. La excentricidad de un vértice "v" es la longitud mayor del camino más corto entre dicho vértice y cualquier otro. El centro esta formado por las aristas: Arista(v1, v2, 1). Arista(v1, v5, 1). Arista(v9, v10, 1). Arista(v10, v11, 1).



4. DIAMETRO DE UN GRAFO. El diámetro de un grafo G es la excentricidad más grande de cualquiera de sus vértices. La excentricidad de un vértice "v" es la longitud mayor del camino más corto entre dicho vértice y cualquier otro. Se ha calculado la excentricidad de cada vértice y se ha tomado el mayor valor. Dando como resultado que el diámetro de este es =6



5. Tome 10 vértices de G7 y obtenga un subgrafo conexo que a la vez sea un

subgrafo inducido de G7 y luego determine:

1. Su centro

2. Su radio

3. Su diámetro.

subgrafo conexo se dice conexo si, para cualquier par de vértices a y b en G,

existe al menos una trayectoria (una sucesión de vértices adyacentes que no

repita vértices) de a y b. y un subgrafo inducido si A’ consta de todas las aristas

(v, w) en A, tal que v y w están en V’, entonces G’(V’, A’) es un grafo inducido de G

Entonces tomamos un subgrafo de G7

G7



1. CENTRO DE UN GRAFO. El centro de un grafo G, C(G) es el subgrafo inducido por los vértices que tienen excentricidad mínima. La excentricidad de un vértice "v" es la longitud mayor del camino más corto entre dicho vértice y cualquier otro. El centro esta formado por las aristas: Arista(v3, v11).

V

3

3



2. RADIO DE UN GRAFO. El radio de un grafo G es la excentricidad más pequeña de cualquiera de sus vértices. La excentricidad de un vértice "v" es la longitud mayor del camino más corto entre dicho vértice y cualquier otro. Se ha calculado la excentricidad de cada vértice y se ha tomado el menor valor. El valor del radio es 3.



3. DIAMETRO DE UN GRAFO. El diámetro de un grafo G es la excentricidad más grande de cualquiera de sus vértices. La excentricidad de un vértice "v" es la longitud mayor del camino más corto entre dicho vértice y cualquier otro. Se ha calculado la excentricidad de cada vértice y se ha tomado el mayor valor. El valor del diámetro es 5.

parcial de grafos no dirigidos utilizando el programa algraf

Documents