Section 6.1 Graphs and Their Representations
499
8. For each of the following characteristics, draw a graph or explain why such a graph does not exist.
a. Simple graph with seven nodes, each of degree 3
b. Four nodes, two of degree 2 and two of degree 3
c. Three nodes of degree 0, 1, and 3, respectively
d. Complete graph with 4 nodes each of degree 2
9. An acquaintanceship graph is an undirected graph in which the nodes represent people and nodes a and b
are adjacent if a and b are acquainted.
a. The acquaintanceship graph for the IT department and the marketing department of a major corporation
is an unconnected graph. What does this imply?
b. The following figure represents an acquaintanceship graph for residents of an apartment building. Are
Carl and Fletcher acquainted? How many people is SiuYin acquainted with?
Carl
Yvonne
Fletcher
Katrina
SiuYin
Moku
Yuri
c. The length of the shortest path between node a and node b in an acquaintanceship graph is sometimes
called the degree of separation between a and b. What is the degree of separation between Carl and Yuri?
10. The “small world effect” states that the average degree of separation (see Exercise 9) in an acquaintanceship graph of the whole world is 6. In other words, a path of acquaintance relationships from you to any
other person on earth exists with, on the average, a path length of 6 (5 intermediate persons). Experiments
in delivering hard-copy letters and e-mail messages have empirically confirmed this theory.
1
a. What are the potential implications for e-mail traffic if the small world effect holds for computer networks?
b. What are the potential implications for epidemiology if the small world effect holds for physical contact between humans?
11. The small world effect (see Exercise 10) has been found to be true between root words (that is, basic
words found in a thesaurus) in the English language, with an average degree of separation equal to 3. Here
“adjacent words” are those that are listed as synonyms in an English thesaurus. For example, “gate” and
“commotion” are related by 3 degrees of separation, as follows:
gate S door S flap S commotion
Can you think of 3 degrees of separation between the following pairs of words?
a. “star” and “sculpture”
b. “burden” and “influence”
c. “piano” and “significance”
1 But more recent analyses of 721 million Facebook users, a much larger community than was available to earlier studies, suggests that the average
number of intermediaries between persons A and B is 3.74. It’s a small world indeed, at least for Facebook users.
499
8. For each of the following characteristics, draw a graph or explain why such a graph does not exist.
a. Simple graph with seven nodes, each of degree 3
b. Four nodes, two of degree 2 and two of degree 3
c. Three nodes of degree 0, 1, and 3, respectively
d. Complete graph with 4 nodes each of degree 2
9. An acquaintanceship graph is an undirected graph in which the nodes represent people and nodes a and b
are adjacent if a and b are acquainted.
a. The acquaintanceship graph for the IT department and the marketing department of a major corporation
is an unconnected graph. What does this imply?
b. The following figure represents an acquaintanceship graph for residents of an apartment building. Are
Carl and Fletcher acquainted? How many people is SiuYin acquainted with?
Carl
Yvonne
Fletcher
Katrina
SiuYin
Moku
Yuri
c. The length of the shortest path between node a and node b in an acquaintanceship graph is sometimes
called the degree of separation between a and b. What is the degree of separation between Carl and Yuri?
10. The “small world effect” states that the average degree of separation (see Exercise 9) in an acquaintanceship graph of the whole world is 6. In other words, a path of acquaintance relationships from you to any
other person on earth exists with, on the average, a path length of 6 (5 intermediate persons). Experiments
in delivering hard-copy letters and e-mail messages have empirically confirmed this theory.
1
a. What are the potential implications for e-mail traffic if the small world effect holds for computer networks?
b. What are the potential implications for epidemiology if the small world effect holds for physical contact between humans?
11. The small world effect (see Exercise 10) has been found to be true between root words (that is, basic
words found in a thesaurus) in the English language, with an average degree of separation equal to 3. Here
“adjacent words” are those that are listed as synonyms in an English thesaurus. For example, “gate” and
“commotion” are related by 3 degrees of separation, as follows:
gate S door S flap S commotion
Can you think of 3 degrees of separation between the following pairs of words?
a. “star” and “sculpture”
b. “burden” and “influence”
c. “piano” and “significance”
1 But more recent analyses of 721 million Facebook users, a much larger community than was available to earlier studies, suggests that the average
number of intermediaries between persons A and B is 3.74. It’s a small world indeed, at least for Facebook users.