Introducción

El grafo out.contiguous-usa representa 48 estados de EEUU que comparten frontera (eliminando Alaska y Hawaii, que no están conectadas a ningún otro estado) e incluyendo el distrito de Columbia. Dos estados comparten frontera si existe una arista que los une.

library(igraph)
library(magrittr)
library(knitr)
library(dplyr)
library(nnet)
  1. Carga el grafo en memoria. Las funciones read_table y graph.data.frame facilitan la tarea de cargar grafos en un formato aceptado por igraph. Busca en la documentación de igraph y R su descripción y uso.
usa_states <- read.table('./out.contiguous-usa', sep=' ', comment.char='%') %>%
                graph_from_data_frame(directed=FALSE)
  1. Muestra el grafo por pantalla e indica qué tipo de grafo es. ¿Qué estructura de datos consideras más eficiente para almacenar la información de este grafo?
plot(usa_states, layout=layout.kamada.kawai)

is.connected(usa_states)
## [1] TRUE
is.directed(usa_states)
## [1] FALSE
is.weighted(usa_states)
## [1] FALSE

Se trata de un grafo no dirigido, no conexo y no ponderado.

Una lista de adyacencias es una opción interesante. Una matriz de adyacencias contendría demasiados ceros y supondría un gasto en memoria innecesario.

  1. Averigua con cuántos estados comparte frontera cada uno de los estados del grafo.
states_degree <- degree(usa_states)

hist(states_degree)

kable(data.frame(states_degree), col.names=c('Estado y Nº de Estados vecinos'))
Estado y Nº de Estados vecinos
1 4
6 6
11 4
12 3
17 6
21 3
25 2
28 3
2 2
3 5
33 6
38 6
34 5
41 4
18 4
42 7
7 3
22 5
26 5
48 1
43 3
35 4
8 8
4 4
39 4
31 4
49 3
19 6
46 3
29 3
13 4
14 5
23 5
44 5
9 6
16 4
30 6
36 6
5 8
15 5
27 6
10 4
20 6
24 2
32 2
37 4
40 2
45 5
47 3
  1. Si el conjunto de estados 5, 8, 27, 33, 34, 42 se independizara, ¿podrían sus habitantes viajar por todo el conjunto de los estados independientes sin necesidad de entrar a EEUU?
is_connected(usa_states)
## [1] TRUE
independent_states <- induced_subgraph(usa_states, c('5', '8', '27', '33', '34', '42'))

is_connected(independent_states)
## [1] TRUE
plot(independent_states)

Como el conjunto de estados original se formaba una componente conexa, por lo tanto, para que este conjunto de estados independientes pueda ser viajado completamente sin necesidad de volver a EEUU (conjunto de estados que no se han independizado), basta con que este conjunto de estados independientes sea conexo.

Como vemos gracias a la función is_connected y al gráfico, se puede apreciar que se puede visitar el conjunto de estados independientes sin necesidad de entrar a EEUU.

  1. ¿Qué estado elegirías para poner una empresa de exportación a estados cercanos?
cat('Estados con más fronteras con otros estados\n')
## Estados con más fronteras con otros estados
states_degree[which.is.max(states_degree)]
## 8 
## 8
cat('\n')
cat('Estado más importante según el concepto de Eigen Centrality, además de su valor Eigen Centrality \n')
## Estado más importante según el concepto de Eigen Centrality, además de su valor Eigen Centrality
eigen <- eigen_centrality(usa_states)$vector
eigen[which.is.max(eigen)]
## 8 
## 1

Eligiría el estado número 8, porque además de ser uno de los que más fronteras tiene con otros estados junto con el 5, es el más importante según Eigen Centrality (estado más importante en función del número de vecinos y la importancia de los mismos).

  1. ¿Cuántos estados podemos agrupar de manera que todos compartan frontera entre sí? ¿En cuántos casos se produce esta situación en el grafo? Pon un ejemplo.
largest.cliques(usa_states)
## [[1]]
## + 3/49 vertices, named:
## [1] 47 22 23
## 
## [[2]]
## + 3/49 vertices, named:
## [1] 47 22 46
## 
## [[3]]
## + 3/49 vertices, named:
## [1] 45 30 44
## 
## [[4]]
## + 3/49 vertices, named:
## [1] 45 30 26
## 
## [[5]]
## + 3/49 vertices, named:
## [1] 45 26 27
## 
## [[6]]
## + 3/49 vertices, named:
## [1] 45 42 27
## 
## [[7]]
## + 3/49 vertices, named:
## [1] 45 42 44
## 
## [[8]]
## + 3/49 vertices, named:
## [1] 40 38 16
## 
## [[9]]
## + 3/49 vertices, named:
## [1] 37 33 35
## 
## [[10]]
## + 3/49 vertices, named:
## [1] 37 33 34
## 
## [[11]]
## + 3/49 vertices, named:
## [1] 32 3  31
## 
## [[12]]
## + 3/49 vertices, named:
## [1] 24 21 22
## 
## [[13]]
## + 3/49 vertices, named:
## [1] 20 36 19
## 
## [[14]]
## + 3/49 vertices, named:
## [1] 20 36 39
## 
## [[15]]
## + 3/49 vertices, named:
## [1] 20 39 38
## 
## [[16]]
## + 3/49 vertices, named:
## [1] 20 38 15
## 
## [[17]]
## + 3/49 vertices, named:
## [1] 20 17 15
## 
## [[18]]
## + 3/49 vertices, named:
## [1] 20 17 19
## 
## [[19]]
## + 3/49 vertices, named:
## [1] 10 13 9 
## 
## [[20]]
## + 3/49 vertices, named:
## [1] 10 6  9 
## 
## [[21]]
## + 3/49 vertices, named:
## [1] 10 6  7 
## 
## [[22]]
## + 3/49 vertices, named:
## [1] 27 5  31
## 
## [[23]]
## + 3/49 vertices, named:
## [1] 27 5  42
## 
## [[24]]
## + 3/49 vertices, named:
## [1] 27 26 25
## 
## [[25]]
## + 3/49 vertices, named:
## [1] 15 14 38
## 
## [[26]]
## + 3/49 vertices, named:
## [1] 15 14 11
## 
## [[27]]
## + 3/49 vertices, named:
## [1] 36 49 39
## 
## [[28]]
## + 3/49 vertices, named:
## [1] 36 49 35
## 
## [[29]]
## + 3/49 vertices, named:
## [1] 36 33 19
## 
## [[30]]
## + 3/49 vertices, named:
## [1] 36 33 35
## 
## [[31]]
## + 3/49 vertices, named:
## [1] 30 23 29
## 
## [[32]]
## + 3/49 vertices, named:
## [1] 30 28 29
## 
## [[33]]
## + 3/49 vertices, named:
## [1] 30 28 26
## 
## [[34]]
## + 3/49 vertices, named:
## [1] 16 14 38
## 
## [[35]]
## + 3/49 vertices, named:
## [1] 16 14 12
## 
## [[36]]
## + 3/49 vertices, named:
## [1] 44 41 43
## 
## [[37]]
## + 3/49 vertices, named:
## [1] 44 41 42
## 
## [[38]]
## + 3/49 vertices, named:
## [1] 23 21 22
## 
## [[39]]
## + 3/49 vertices, named:
## [1] 14 11 12
## 
## [[40]]
## + 3/49 vertices, named:
## [1] 13 17 9 
## 
## [[41]]
## + 3/49 vertices, named:
## [1] 31 3  5 
## 
## [[42]]
## + 3/49 vertices, named:
## [1] 4 6 5
## 
## [[43]]
## + 3/49 vertices, named:
## [1] 4 6 7
## 
## [[44]]
## + 3/49 vertices, named:
## [1] 4 1 5
## 
## [[45]]
## + 3/49 vertices, named:
## [1] 8  19 18
## 
## [[46]]
## + 3/49 vertices, named:
## [1] 8  19 33
## 
## [[47]]
## + 3/49 vertices, named:
## [1] 8  42 5 
## 
## [[48]]
## + 3/49 vertices, named:
## [1] 8  42 34
## 
## [[49]]
## + 3/49 vertices, named:
## [1] 8  18 9 
## 
## [[50]]
## + 3/49 vertices, named:
## [1] 8  34 33
## 
## [[51]]
## + 3/49 vertices, named:
## [1] 8 6 5
## 
## [[52]]
## + 3/49 vertices, named:
## [1] 8 6 9
## 
## [[53]]
## + 3/49 vertices, named:
## [1] 41 34 42
## 
## [[54]]
## + 3/49 vertices, named:
## [1] 3 1 5
## 
## [[55]]
## + 3/49 vertices, named:
## [1] 3 1 2
## 
## [[56]]
## + 3/49 vertices, named:
## [1] 17 18 9 
## 
## [[57]]
## + 3/49 vertices, named:
## [1] 17 18 19

Esto se produce en hasta 57 ocasiones. Un ejemplo: 34, 41 y 42.

  1. ¿Cuál es el máximo número de estados que es necesario atravesar para ir de un estado a otro?
diameter(usa_states)
## [1] 11
  1. ¿Cuál es el camino más corto para ir del estado 40 al estado 13? ¿Existe un único camino?
all_shortest_paths(usa_states,'40','13')$res
## [[1]]
## + 5/49 vertices, named:
## [1] 40 38 15 17 13
## 
## [[2]]
## + 5/49 vertices, named:
## [1] 40 38 20 17 13
## 
## [[3]]
## + 5/49 vertices, named:
## [1] 40 16 14 11 13
## 
## [[4]]
## + 5/49 vertices, named:
## [1] 40 38 14 11 13
## 
## [[5]]
## + 5/49 vertices, named:
## [1] 40 38 15 11 13
## 
## [[6]]
## + 5/49 vertices, named:
## [1] 40 16 12 11 13

Existen hasta 6 caminos cortos por los que hay que atravesar 5 estados.

  1. Representa la matriz de adyacencia de este grafo. ¿Es simétrica? ¿Por qué?
adjacency_matrix <- as_adj(usa_states)

adjacency_matrix %>%
  as.matrix() %>%
  isSymmetric()
## [1] TRUE

La matriz de adyacencia de este grafo sí es simétrica porque se trata de un grafo no ponderado y no dirigido.

  1. Añade los estados de Hawaii (49) y Alaska (50). ¿En qué tipo de grafo se ha convertido?
usa_states <- usa_states + vertex('49', '50')

is.connected(usa_states)
## [1] FALSE
plot(usa_states)

El grafo se ha convertido en una componente no conexa porque los estados añadidos no comparten frontera con ningún estado.