Sign in
CECS 310 Homework Assignment 4 (Due 12/1/22)
1) (25 pts) (a) How many connected (undirected) graphs can be produced with 4 vertices and 4 edges such that each graph has a unique degree sequence? Assume parallel edges are permitted, but loops are not permitted.
2) (25 pts) Let ∑={a,b} and T be the set of words in ∑* that have no consecutive a’s (i.e. there cannot be 2 or more a’s in a row).
(a) Give a recursive definition for the set T.
(b) Use your recursive definition to show that the string “abbaba” is in T.
(c) Is your recursive definition uniquely determined? Explain why or why not.
(3) (25 pts) (a) Show or explain why there can be multiple critical paths in a scheduling network. (b) Can increasing the weight of a single critical edge in a network ever impact multiple critical paths? Explain why or why not.
(4) (25 pts) Consider graph H below
(a) Create weight matrix W for H.
(b) Apply Dijkstra’s algorithm to find the shortest path from vertex a to vertex g in H. For full credit you must show your work, follow Dijkstra’s algorithm approach explicitly, and indicate both the shortest path and cumulative weight at the end.
