Problema de Grafos Comparados. Práctica Resuelta.

por Feb 12, 2016Sin categoría1 Comentario

A partir de los siguientes grafos conteste a las siguientes preguntas:

  1. Realice la matriz de conectividad de ambos grafos y calcule el índice Beta, número Ciclomático e índice AlfaIndique que grafo tiene mayor conectividad.
  2. Realice la matriz de accesibilidad de ambos grafos y calcule el número asociado de konning y el índice Shimbel e indica que punto de cada grafo tiene una mejor accesibilidad, y cual es el punto más accesible comparando ambos grafos.

Grafo 1 (Menorca)
teoría de grafos práctica
Grafo 2 (La Palma)

RESPUESTA 1


GRAFO 1

Matriz de Accesibilidad Grafo 1 (Menorca)

Número de Nodos: 7

Número de Arcos: 7

Matriz de Accesibilidad: de la matriz se desprende que los puntos más accesibles son F, M y Ma

Índice Beta: 7/7= 1, el índice beta indica que el grafo tiene al menos un circuito, aunque su conectividad es baja.

Número Ciclomático: 7-(7-1)=1 este número también nos indica que el número de circuitos es de 1 formado por los nodos (M, Ma y Fe)

Índice Alfa: [7-(7-1)]/[2*7-5]= 0.090 lo que nos dice que la red de transporte de Menorca tiene sólamente el 9% de conectividad desarrollada.

GRAFO 2

Matriz de Accesibilidad Grafo 2 (La Palma)

Número de Nodos: 13

Número de Arcos: 14

Matriz de Accesibilidad: de la matriz se desprende que los puntos más accesibles son C y F

Índice Beta: 14/13= 1,07 el índice beta nos indica que la conectividad es baja.

Número Ciclomático: 14-(13-1)=2 este número también nos indica que el número de circuitos es de 2 que son los formados por los nodos (C,F,G,H,I,J) y el circuito formado por los nodos (J,I,L)

Índice Alfa: [14-(13-1)]/[2*13-5]= 0.095 lo que nos dice que la red de transporte de Menorca tiene sólamente el 9,5% de conectividad desarrollada.

Aunque sea por un porcentaje muy pequeño, el grafo 2 correspondiente a la isla de La Palma tiene un grado de conectividad mayor que la red de transportes de Menorca.

RESPUESTA 2


GRAFO 1

Matriz de Accesibilidad Grafo 1 (Menorca)

El punto más accesible del Grafo 1 es el nodo M

El índice de dispersión del grafo es la suma de los índices de todos los vértices = 79

GRAFO 2

Matriz de Accesibilidad Grafo 2 (La Palma)

Los puntos más accesible del Grafo 2 es el nodo C y el nodo J.

El índice de dispersión del grafo es la suma de los índices de todos los vértices = 415

RESPUESTAS

A partir de los índices de dispersión podemos decir que la red de transporte de Menorca es mucho más concentrada que la de la isla de La Palma, que es bastante más dispersa.

Para poder calcular comparar los puntos más accesibles de diferentes gráficos es necesario aplica el Índice Omega que se calcula a través de la siguiente fórmula:

                          ( Índice Shimbel del nodo)-(Índice Shimbel más bajo)

Índice Omega :——————————————————————

                          (Índice Shimbel más alto)-(Índice Shimbel más bajo)

Índice Omega Grafo 1: (9-9)/(16-9)= 0.14

Índice Omega Grafo 2: (24-24)/(43-24)= 0.05


Por tanto el nodo M, del Grafo 1, es más accesible que los nodo C y J del grafo 2

1 Comentario

  1. El indice alfa del grafo 1 a mi me da 11% pese a que evidentemente parece que tenga menos conectividad que el grafo dos, que de indice alfa da 9,5%.
    [7-(7-1)]/[2*7-5]=0,11 11%