You are using a browser not supported by the Wolfram Cloud
Supported browsers include recent versions of Chrome, Edge, Firefox and Safari.
I understand and wish to continue anyway »
WOLFRAM NOTEBOOK
Lab 3: Internet as a Graph (15 points)
Lab 3: Internet as a Graph (15 points)
NetID: <Please fill in>
Network Representation using Graphs
Network Representation using Graphs
A graph is a way of showing connections between things—say how computers are linked together to form a network.
A very simple graph with 2 connections:
In[]:=
Graph[{a->b,b->c}]
Out[]=
You can get the → by typing - and >, one right after the other from your keyboard.
Let’s add labels to identify who is connected to whom:
In[]:=
Graph[{a->b,b->c},VertexLabels->Automatic]
Out[]=
Let’s add one more edge from c back to a:
In[]:=
Graph[{a->b,b->c,c->a},VertexLabels->Automatic]
Out[]=
The circles/dots are called “vertices” and lines connecting these circles are called "edges".
The vertices (sometimes called “nodes”) represent the computers and the edges represent the connections between the computers.
The vertices (sometimes called “nodes”) represent the computers and the edges represent the connections between the computers.
Directed Graphs
Directed Graphs
Undirected Graphs
Undirected Graphs
Unweighted Graphs
Unweighted Graphs
Weighted Graphs
Weighted Graphs
Problem 1 (3 points)
Edit the following code to create your own graph. Add in as many nodes and edges as you like as well as values for the edge weights. Create an interesting topology.
Graph[{},(*edges*)EdgeWeight{},(*weights*)VertexLabelsAutomatic,EdgeLabels"EdgeWeight"]
Answer
Answer
Cost of a Path through the Graph
Cost of a Path through the Graph
Let' s look at a slightly more complicated graph :
In[]:=
UndirectedGraph{s->a,s->b,a->b,b->d},EdgeWeight{1,3,1,4},
Out[]=
Problem 2 (2 points)
In the graph above, which path is the least-cost path from s to d?
What is that least cost?
(For example, you can say: the least cost path is x -> y -> z, and the least cost is 42.)
What is that least cost?
(For example, you can say: the least cost path is x -> y -> z, and the least cost is 42.)
Answer
Answer
Problem 3 (1 point)
What about the least-hop path from s to d? (Count only hops; you can ignore the link costs)
What is the least number of hops?
What is the least number of hops?
Answer
Answer
Problem 4 (2 points)
Now, let’s look at a more complex example:
In[]:=
g=UndirectedGraph{s->m,s->n,m->n,m->d,n->d},EdgeWeight{5,2,1,2,5},
Out[]=
What is the least-cost path from s to d in the graph above? What is that least cost?
Answer
Answer
More Nodes means More Paths
More Nodes means More Paths
Start simple
Start simple
Let' s look at the same graph as above, but with edge weights removed .
In[]:=
g=UndirectedGraph{s->m,s->n,m->n,m->d,n->d},
Out[]=
Problem 5 (1 point)
How many total paths are there from s to d in the graph above? Can you list all of the paths?
Answer
Answer
Add another node
Add another node
Now, let’s add one more node o to the graph above. This node is connected to all other nodes.
Problem 6 (2 points)
Can you list at least 6 different paths from s to d in the graph now?
Hint: there are 15 possible paths!
Hint: there are 15 possible paths!
Answer
Answer
Finding all the different paths seems like a lot of work, right? Let’s have the computer do this for us:
Highlight those paths on the graph
Hierarchical Networks
Hierarchical Networks
Network of networks
Network of networks
As you have observed, network complexity increases very very quickly as we increase number of nodes in our network.
This is why we often use a "hierarchical" network or a network of networks of networks and so on.
This is why we often use a "hierarchical" network or a network of networks of networks and so on.
Network 1
Here is one network:
Network 2
Here is a second network:
Network 3
Here is a third network.
Hierarchical network of networks:
Here is a hierarchical network connecting the above 3 networks:
Remember connecting UIUC to the Internet from the Lecture slides of 2/10
Remember connecting UIUC to the Internet from the Lecture slides of 2/10
The following is another example of a hierarchical network, with the nodes {s, 1, 2, 3, 4, 5, 6, 7, 8, 9} representing a toy UIUC network (highlighted in orange) :
Let’s ask the computer to find the “shortest path” from s to a destination node d in this network.
Highlight the shortest path on the graph:
Disconnect UIUC from the Internet
Disconnect UIUC from the Internet
Now let' s try to disconnect UIUC' s network from the the rest of the network (which supposedly represents the internet in this example), by removing only one edge.
Let’s delete the edge between 10 and 26:
Can we still find a path from s to d?
There is still a path.
Problem 7 (2 points)
Can you remove one edge from the graph above (newGraph), such that the orange UIUC network gets disconnected from the internet?
Edit the code in the cell below to try this (replace “oneNode” and “anotherNode” with the actual node name/number) .
Edit the code in the cell below to try this (replace “oneNode” and “anotherNode” with the actual node name/number) .
Answer
Answer
Problem 8 (2 points)
Which two nodes could you connect now to make sure that the UIUC network remains connected to the internet, even after removing the edge you deleted in Problem 7?
Answer
Answer
Extra Credit (3 points)
In class you provided examples of hierarchies you have seen or heard about. Similarly think about examples the consist of entities/things/objects/people etc. and connections between them. Create a graph to represent a collection of entities and the connections between them.
Submitting your work
Submitting your work
1
.Ensure you have filled in your NetID at the top of the notebook
2
.Save the notebook as a PDF file (Alternately, "Print to PDF" but please ensure the PDF looks ok and is not garbled)