xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

程序代写案例-MAST30011

时间：2021-04-14

MAST30011 Graph Theory 2021

ASSIGNMENT 1

Due 13:00pm Friday 16 April 2021

1. In the following graph,

(a) give an example of a longest trail,

(b) give an example of a longest cycle,

(c) give an example of a longest path, and

(d) list all induced subgraphs which are paths of length 4.

a b

c

def

h

2. Two of the following graphs F , G and H are isomorphic to each other. For the two

graphs which are isomorphic, give an isomorphism between them and prove that

it is indeed an isomorphism. For the other graph, show that it is not isomorphic

to the two which are isomorphic.

3. Prove that if G is a graph with no cycles of even length, then every cycle in G is

an induced subgraph of G.

4. Let G be the following weighted graph, where the number next to each edge is the

weight of the edge.

1

ax d

bh

1

5

9

4

2

4

1

7

c

2

y

z

1

6

Apply Dijkstra’s algorithm to find the distance from a to all other vertices of G.

State what the labels of vertices are when each new vertex is chosen to be added

to the set S. Finally, draw a tree determining shortest paths from a to all other

vertices of G.

5. Suppose that G ∼= G and that n = |V (G)| = 4k + 1 for some integer k ≥ 1

(where G is the complement of G). Suppose that the degree sequence of G is

d1 ≥ d2 ≥ · · · ≥ dn.

(a) Prove that di + dn−i+1 = n− 1 for each i = 1, 2, . . . , n.

(b) Use (a) to prove that G has at least one vertex with degree (n− 1)/2.

6. Use the original version of Kruskal’s algorithm to find a minimum spanning tree of

the following weighted graph. List the edges of the minimum spanning tree found

in the order the algorithm adds them to the tree, and compute the weight of this

minimum spanning tree.

a b c

d

e f

g

1 4

13 5 6 7

11

5

86

13

1

2

学霸联盟

ASSIGNMENT 1

Due 13:00pm Friday 16 April 2021

1. In the following graph,

(a) give an example of a longest trail,

(b) give an example of a longest cycle,

(c) give an example of a longest path, and

(d) list all induced subgraphs which are paths of length 4.

a b

c

def

h

2. Two of the following graphs F , G and H are isomorphic to each other. For the two

graphs which are isomorphic, give an isomorphism between them and prove that

it is indeed an isomorphism. For the other graph, show that it is not isomorphic

to the two which are isomorphic.

3. Prove that if G is a graph with no cycles of even length, then every cycle in G is

an induced subgraph of G.

4. Let G be the following weighted graph, where the number next to each edge is the

weight of the edge.

1

ax d

bh

1

5

9

4

2

4

1

7

c

2

y

z

1

6

Apply Dijkstra’s algorithm to find the distance from a to all other vertices of G.

State what the labels of vertices are when each new vertex is chosen to be added

to the set S. Finally, draw a tree determining shortest paths from a to all other

vertices of G.

5. Suppose that G ∼= G and that n = |V (G)| = 4k + 1 for some integer k ≥ 1

(where G is the complement of G). Suppose that the degree sequence of G is

d1 ≥ d2 ≥ · · · ≥ dn.

(a) Prove that di + dn−i+1 = n− 1 for each i = 1, 2, . . . , n.

(b) Use (a) to prove that G has at least one vertex with degree (n− 1)/2.

6. Use the original version of Kruskal’s algorithm to find a minimum spanning tree of

the following weighted graph. List the edges of the minimum spanning tree found

in the order the algorithm adds them to the tree, and compute the weight of this

minimum spanning tree.

a b c

d

e f

g

1 4

13 5 6 7

11

5

86

13

1

2

学霸联盟