Activity 14.1.
Draw all possible simple graphs with
Hint.
See Statement 3 of Proposition 14.2.11.
Activities 14.5 Activities
Activity 14.2.
Suppose
Every pair of a subsetand a subcollection defines a subgraph of
Activity 14.3.
Draw a graph where the nodes are students present in today’s class. Draw edges between pairs of students that are in the same group today. Additionally, draw an edge between a member of your group and another student if that pair was in a group together last class.
Activity 14.4.
For each of the following graphs, write out its formal definition as either a (regular) graph, a weigthed graph, or a directed graph, as appropriate.
(a)
(b)
(c)
Activity 14.5.
Consider the website Facebook as a graph where vertices are profiles and edges represent “friendship”.
(a)
Should this graph be a directed graph? Why or why not?
(b)
Is this graph simple? complete? Justify your answers.
(c)
What does the degree of a vertex represent?
(d)
Could this graph have isolated vertices?
(e)
Suppose the following graph is a subgraph of the Facebook graph.
(i)
What is the largest party one of these people could throw where each party-goer is Facebook friends with every other party-goer? Justify your answer.
(ii)
Assume all of the people in this graph live in the same geographic area. Which pair of non-friends are most likely to become friends in the future? Which pair of non-friends are least likely to become friends in the future? Justify your answers.
