Graph Theory Question

Social networks such as Facebook and LinkedIn can be represented using graphs in which vertices represent people and edges are drawn between two vertices when those people are "friends."The table below shows a friendship table, where an X shows that two people are friends

A B C D E F G H I

A X X X X

B X X

C X

D X X

E X X

F X X

G X

H X

a.Draw graph of this friendship table

b.Find the shortest path from A to D.The length of this path is often called the "degrees of separation" of the two people.

c.Extension:Split into groups.Each group will pick 10 or more movies, and look up their major actors (www.imdb.com is a good source).Draw graph with each actor as a vertex, and edges connecting two actors in the same movie (note the movie name on the edge).Find interesting paths between actors, and quiz the other groups to see if they can guess the connections.