HOMEWORK PROBLEMS #3
3-1 Consider the following graph.
Find:
• adjacency, incidence and Laplacian matrices
• all cut sets
• complementary graph
• line graph
• average closeness of the graph
• density of the graph
• node connectivity
• edge connectivity
• closeness of node 5
• all graph-theoretic centres
3-2 Consider the following graph. In the lecture, the cyclic coefficient of Node 5 was calculated. Now, find (a) the girth of Node 5; (b) the cyclic coefficients of Nodes 1, 2, 3, 4, 6 and that of the whole graph.
3-3 Let be the distance between two nodes in a connected graph , where denotes the set of nodes in . Now:
• the centrality of a node is defined by
• the radius of is defined by
• the diameter of is defined by
• a node is called a graph-theoretic centre of if
For the graph shown below, find:
• radius of
• diameter of
• all graph-theoretic centres of
3-4 Consider a computer network in a lab, as shown by the following figure, where each node is a computer (Router or PC) and the numbers indicate the costs of cables (optical fibers) needed if the computers are connected.
8
8
9
11
11
13
4
12
8
7
7
A
B
10
9
9
11
11
13
4
12
8
7
7
A
B
10
9
(a) Design a best possible cost-effective Personal Area Network (PAN) by connecting all nodes together, so that every computer can communicate with every other one while the total cost of cables (optical fibers) is the lowest. Explain your design steps.
(b) Find the cable with lowest cost from A to B