关键词 > CS5970/6970

CS 5970/6970: Graph Algorithms Homework 1 2022

发布时间：2022-08-22

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CS 5970/6970: Graph Algorithms

August 18, 2022

Homework 1

Make sure you have python3 (mac’s ship with python2 on the PATH, but python2 is depricated) installed. Get the networkx package via pip or conda etc.

Question 1. List as many properties of the following graphs as you can and the categories of graphs each of the following graphs belong to. (5 points each)

Question 2. Create the adjacency matrix for the last two graphs from question 1 (5 points each).

Question 3. On the following graph ﬁnd a walk b 二 d that is not a trail. (5 points)

c d

Question 4. On the following graph ﬁnd a trail b 二 d that is not a path. (5 points)

Question 5. On the following graph ﬁnd a path b 二 d. (5 points)

c d

Question 6. On the following graph ﬁnd a trail b 二 d that is not a path. (5 points)

Question 7. Given the following simple maze, convert the maze into a graph. (5 points)

Question 8. Implement depth ﬁrst search in the maze function in homework1.py. (20 points)

Question 9. All possible chess games can be thought of as a tree of chess moves starting at the initial position with then all legal moves from each position as children of each other position. In the function checkmate, implement breadth ﬁrst search on the given move tree and root node to ﬁnd the fastest possible checkmate. The output should be the sequence of moves. Eg e2e4 e7e5 .. .. The graph stores a text representation of the game at every node as well as the move to get to that position and the text representation of the board at the previous position (the parent node). (25 points)