Ejercicios Graphs, Paths & Components

Ejercicios básicos de Grafos.

Ejercicio - Número de Nodos y Enlaces

(resuelva en código propio y usando la librería NetworkX (python) o iGraph (R))

Cuente el número de nodos y enlaces con los siguientes links (asumiendo que el grafo puede ser dirigido Y no dirigido):



In [53]:

    
edges = set([(1, 2), (3, 1), (3, 2), (2, 4)])



In [66]:

    
import networkx as nx
G=nx.Graph() #Se crea un grafo vacio y no dirigido
G.add_edges_from(edges)
G2=nx.DiGraph() #Se crea un grafo vacio y no dirigido
G2.add_edges_from(edges)
numNodes = G.number_of_nodes()
numEdges = G.number_of_edges() # el grafo se creo no dirigido, la respuesta sera 4, pero son 4 con dos direciones
print("Grafo no dirigido")
print("La tupla (1,2) es no dirigida: ", G.has_edge(1,2))# dice si la tupla tiene un enlace dirigido (false) o no dirigido (true)
print("Es dirigido: ", G.is_directed())# dice si el grafo es dirigido o no dirigido
print("Numero de nodos: "+str(numNodes))
print("Numero de enlaces(no dirigido): "+str(numEdges))# imprime 4 enlaces no dirigidos
print("")
print("Grafo Dirigido")
print("Numero de nodos: "+str(G2.number_of_nodes()))
print("Numero de enlaces(dirigido): "+str(G2.number_of_edges()))# imprime 4 enlaces dirigidos
print(G[3])









    



Grafo no dirigido
La tupla (1,2) es no dirigida:  True
Es dirigido:  False
Numero de nodos: 4
Numero de enlaces(no dirigido): 4

Grafo Dirigido
Numero de nodos: 4
Numero de enlaces(dirigido): 4
{2: {}, 1: {}}

Ejercicio - Matriz de Adyacencia

(resuelva en código propio y usando la librería NetworkX (python) o iGraph (R))

Cree la matriz de adyacencia del grafo del ejercicio anterior (para dirigido y no-dirigido)



In [58]:

    
A = nx.adjacency_matrix(G)
print("Grafo no dirigido")
print(A.todense())
print("")
A2 = nx.adjacency_matrix(G2)
print("Grafo dirigido")
print(A2.todense())









    



Grafo no dirigido
[[0 1 1 0]
 [1 0 1 1]
 [1 1 0 0]
 [0 1 0 0]]

Grafo dirigido
[[0 1 0 0]
 [0 0 0 1]
 [1 1 0 0]
 [0 0 0 0]]

Ejercicio - Sparseness

Calcule la proporción entre número de links existentes en 3 redes reales (http://snap.stanford.edu/data/index.html) contra el número de links posibles.



In [ ]:

En la matriz de adyacencia de cada uno de las redes elegidas, cuantos ceros hay?



In [ ]:

Ejercicio - Redes Bipartitas

Defina una red bipartita y genere ambas proyecciones, explique qué son los nodos y links tanto de la red original como de las proyeccciones



In [ ]:

Ejercicio - Paths

Cree un grafo de 5 nodos con 5 enlaces. Elija dos nodos cualquiera e imprima:

5 Paths diferentes entre los nodos
El camino mas corto entre los nodos
El diámetro de la red
Un self-avoiding path



In [ ]:

Ejercicio - Componentes

Baje una red real (http://snap.stanford.edu/data/index.html) y lea el archivo



In [ ]:

Utilizando NetworkX o iGraph descubra el número de componentes



In [ ]:

Implemente el algorithmo Breadth First para encontrar el número de componentes (revise que el resultado es el mismo que utilizando la librería)



In [ ]:

Ejercicio - Degree distribution

(resuelva en código propio y usando la librería NetworkX (python) o iGraph (R))

Haga un plot con la distribución de grados de la red real



In [4]:

Calcule el grado promedio



In [ ]:

Ejercicio - Diámetro



In [7]:

    
N = 5

Cree un grafo de N nodos con el máximo diámetro posible



In [ ]:

Cree un grafo de N nodos con el mínimo diámetro posible



In [ ]:

Cree un grafo de N nodos que sea un ciclo simple



In [ ]:

Ejercicio - Pregunta "real"

Una aerolínea tiene las siguientes rutas desde las ciudades a las que sirve (cada par tiene servicio en ambas direcciones).



In [8]:

    
routemap =  [('St. Louis', 'Miami'), 
             ('St. Louis', 'San Diego'), 
             ('St. Louis', 'Chicago'), 
             ('San Diego', 'Chicago'), 
             ('San Diego', 'San Francisco'), 
             ('San Diego', 'Minneapolis'), 
             ('San Diego', 'Boston'), 
             ('San Diego', 'Portland'), 
             ('San Diego', 'Seattle'), 
             ('Tulsa', 'New York'), 
             ('Tulsa', 'Dallas'), 
             ('Phoenix', 'Cleveland'), 
             ('Phoenix', 'Denver'), 
             ('Phoenix', 'Dallas'), 
             ('Chicago', 'New York'), 
             ('Chicago', 'Los Angeles'), 
             ('Miami', 'New York'), 
             ('Miami', 'Philadelphia'), 
             ('Miami', 'Denver'), 
             ('Boston', 'Atlanta'), 
             ('Dallas', 'Cleveland'), 
             ('Dallas', 'Albuquerque'), 
             ('Philadelphia', 'Atlanta'), 
             ('Denver', 'Minneapolis'), 
             ('Denver', 'Cleveland'), 
             ('Albuquerque', 'Atlanta'), 
             ('Minneapolis', 'Portland'), 
             ('Los Angeles', 'Seattle'), 
             ('San Francisco', 'Portland'), 
             ('San Francisco', 'Seattle'), 
             ('San Francisco', 'Cleveland'), 
             ('Seattle', 'Portland')]

Cuál es el máximo número de intercambios que tendría que hacer un pasajero en un solo viaje entre dos ciudades servidas? (suponiendo rutas óptimas)



In [ ]:

Si usted necesitara viajar mucho en esta aerolínea, cual sería el lugar óptimo para vivir? (i.e. minimizar el número de intercambios para llegar a cualquier ciudad)



In [ ]:

Visualize la red



In [ ]: