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 29

5

4

5

2

8

1

8

6

(^43)
10
v (^557)
v 1
v 6 v 8
v 7
v 3
v 2
v 4
Figure 2.13. Steiner Tree. [Steiner tree forV′={v 2 ,v 4 ,v 7 }].
an edge. Hence,

|E|=

(

|V|

2

)

. (2.17)

Complete graphs withnnodes are often denoted asKn.K 1 ,K 2 ,K 3 , and

K 4 are shown in Figure2.14.

2.5.4 Planar Graphs

A graph that can be drawn in such a way that no two edges cross each other

(other than the endpoints) is calledplanar. A graph that is not planar is

denoted asnonplanar. Figure2.15shows an example of a planar graph and

a nonplanar graph.

2.5.5 Bipartite Graphs

A bipartite graphG(V,E) is a graph where the node set can be partitioned

into two sets such that, for all edges, one endpoint is in one set and the other

endpoint is in the other set. In other words, edges connect nodes in these

two sets, but there exist no edges between nodes that belong to the same

v 1

v 1

v 1

v 1

v 2

v 2

v 2 v 3 v 4 v 3

Figure 2.14. Complete GraphsKifor 1≤i≤4.