Social Media Mining: An Introduction

P1: WQS Trim: 6.125in×9.25in Top: 0.5in Gutter: 0.75in
CUUS2079-02 CUUS2079-Zafarani 978 1 107 01885 3 January 13, 2014 16:38

2.5 Special Graphs 27

v 10 v 13

v 11 v^12

v 7

v 5

v 8 v 9

v 4

v 3

v 1 v 2

v 6

Figure 2.11. A Forest Containing Three Trees.

2.5.1 Trees and Forests

Trees are special cases of undirected graphs. Atreeis a graph structure that

has no cycle in it. In a tree, there is exactly one path between any pair of

nodes. A graph consisting of set of disconnected trees is called aforest.A

forest is shown in Figure2.11.

In a tree where we have|V|nodes, we have|E|=|V|−1 edges. This

can be proved by contradiction (see Exercises).

2.5.2 Special Subgraphs

Some subgraphs are frequently used because of their properties. Two such

subgraphs are discussed here.

1. Spanning Tree.For any connected graph, thespanning treeis a
   subgraph and a tree that includes all the nodes of the graph. Obviously,
   when the original graph is not a tree, then its spanning tree includes
   all the nodes, but not all the edges. There may exist multiple spanning
   trees for a graph. For a weighted graph and one of its spanning trees,
   the weight of that spanning tree is the summation of the edge weights
   in the tree. Among the many spanning trees found for a weighted
   graph, the one with the minimum weight is called theminimum
   spanning tree(MST).
   For example, consider a set of cities, where roads need to be built to
   connect them. We know the distance between each pair of cities. We