MAT668

Lab 2

To print: File -> Print Preview


In [1]:
%pylab inline
import networkx as nx


Populating the interactive namespace from numpy and matplotlib

Q1

Assign your name to a variable called "my_name".
Assign your student id to variable "stud_id".
Use variable "my_name" and "stud_id" to print your name and your student id using "print" function in the following format.

Your Name - Your Student ID

For example:
Ali bin Abu - 2013123456


In [ ]:


Q2

Import APGG, generate an undirected graph G using the "stud_id" variable defined in Q1 and draw it using APGG.draw() function.

Hint: Click on "Cell > Run All" if you get a warning message.


In [ ]:


Q3

List all vertices of graph G and their respective degree.


In [ ]:


Q4

List all edges along with its weight.


In [ ]:


Q5

Determine whether graph G is an Eulerian graph. (NetworkX Reference, pg. 256)


In [ ]:


Q6

Find the shortest path between any two non-adjacent vertices from graph G. (NetworkX Reference, pg. 326)


In [ ]:


Q7

What is the total weight for the path choses in Q6. (NetworkX Reference, pg. 328)


In [ ]:


Q8

Find a maximal cardinality matching in graph G. (NetworkX Reference, pg. 309)


In [ ]:


Q9

Find a minimum spanning tree of the undirected weighted graph G. (NetworkX Reference, pg. 315)


In [ ]:


Q10

Generate an undirected graph K using your friend's student id and check if K is isomorphic with G. (NetworkX Reference, pg. 285)


In [ ]:


Q11

Generate a network L using your student id using APGG.generate_flow() function and draw it.


In [ ]:


Q12

Find a maximum single-commodity flow for network L from 's' to 't'. (NetworkX Reference, pg. 259)


In [ ]:
flow_value, flow_dict =

Print flow_value


In [ ]:

Print flow_dict


In [ ]:


Q13

Compute the value and the node partition of a minimum (s, t)-cut. (NetworkX Reference, pg. 261)


In [ ]:
cut_value, cut_set =

Print cut_set


In [ ]:

Print cut_value


In [ ]:

The End