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

50 Graph Essentials

v 1

(^559)
7
7
8
9
6
15
11
8
v 2
v 3
v 4 v 5
v 6
v 7
Figure 2.29. Weighted Graph.

10. Compute the minimal spanning tree using Prim’s algorithm in the graph
    provided in Figure2.30.

v 5

v 2

v 1

v 3

v 4

9

v 7

v 6

v 9

v 8

15

9

9

8

11

7

8

7

5 5

7

8

5

6

Figure 2.30. Weighted Graph.

11. Compute the maximum flow in Figure2.31.

v 4

v 2

v 1 v 6

t

3

3

2

2

3

2

1

1

1

2

2

5

5

4

v 3

s v 5

Figure 2.31. Flow Graph.

12. Given a flow network, you are allowed to change one edge’s capacity.
    Can this increase the flow? How can we find the correct edge to change?


13. How many bridges are in a bipartite graph? Provide details.