算法代写 | CSE 21 HW 6

这个作业是完成图相关的数据结构和算法
CSE 21 HW 6

(1) Consider the complete bipartite graph Kn,m on n and m vertices.
(a) For which values of n and m does Kn,m contain an Eulerian circuit?
(b) Choose positive values of n and m such that n + m ≥ 6, and Kn,m contains an Eulerian circuit.
Label the vertices of Kn,m and give an Eulerian circuit for it.
(2) The line graph of a graph G = (V, E) is the graph L(G) = (E, F) whose vertex set is E and whose
edge set is
F = {{e, f} ⊂ E : e ∩ f 6= ∅}
(a) Draw L(C4) and L(K4)
(b) How many edges does L(G) have in terms of the degrees d(v) : v ∈ V (G) of the vertices of G?
(c) Prove that if G is connected and k-regular then L(G) is Eulerian
(d) Prove that if G is Eulerian then L(G) is also Eulerian
(e) If the line graph of a graph G is Eulerian, must G be Eulerian?
(3) Below are the distances (in miles) of certain routes between the five cities: Fresno, Los Angeles,
Sacramento, San Diego, and San Francisco.