Write a function incident_edges that finds all edges from agraph G that are incident with a subgraph T

In [63]:

def incident_edges(G,T): ”’ return the set of all edges from graph G that are incident with tree T”’ # initialize an empty set incidentEdges incidentEdges=set() # for every vertex v in T check all edges e in G. for v in T.vertex_set: for e in G.edge_set: if v in e: incidentEdges.add(e) # if v is an endpoint of e, add e to incidentEdges # return indicent edges that are not already edges in T return (incidentEdges-T.edge_set)

Test incident_edges using test1.txt and test1sub.txt. If yourfunction is correct, you should see {(2, 4), (3, 4), (3, 5), (4,5)}

In [64]:

G = Weighted_Graph(‘test1.txt’)T = Graph(‘test1sub.txt’)incident_edges(G,T)

Out[64]:

{(2, 4), (3, 4), (3, 5), (4, 5)}

Finding valid edges.

**Problem 2**: Write a function valid edges thattakes a Graph G and a subgraph T, and returns all edges e in Gwhere + T+e is a tree. (Hint: first find all edges incident with T and then find the ones that can be added to T to make atree).

In [ ]:

def valid_edges(G,T): ”’ return the set of all edges e from G where T+e is a tree and e is not already an edge of T”’ # get a set incident of all edges in G incident with T i = incidentEdges # initialize an empty set valid valid=set() # check all edges e in incident. if T+e is a tree, add e to valid # Hint: test e using a copy of T for e in i.edge_set: if T+e=True for a in e # return all of the valid edges …

Test valid_edges using test1.txt and test1sub.txt. If yourfunction is correct, you should see {(2, 4), (3, 4), (4, 5)}

In [ ]:

Finding the minimum valid edge

We now need to find the valid edge with the smallest weight. Itmay make your code more readable to create a function weight thattakes a graph G and an edge e and returns the weight of theedge.

**Problem 3**: Complete the function weightbelow.

In [ ]:

def weight(e,G): ”’ return the weight of an edge in a weighted graph G ”’ …

**Problem 4**: Now write a function that takes agraph G and a subgraph T, checks all valid edges (the edges thatcan be added to T to produce a tree) and returns the one with theminimum weight.

In [ ]:

def min_valid_edge(G,T): ”’ return the edge e from graph G with minimum weight where T+e is a tree ”’ # get a set all edges e in G where T+e is a tree … # initialize min_edge to be a random edge in valid … # check all valid edges e. if the weight of e is less than the weight of min_edge, update minEdge = e … # return min_edge …

Test min_valid_edge using test1.txt and test1sub.txt. If yourfunction is correct, you should see (3, 4)

In [ ]:

Prim’s algorithm

**Problem 5**: Finally, write a function that takesas input a graph G and executes Prim’s algorithm to find aminimum-weight spanning tree.

In [ ]:

def prim(G): ”’ Use Prim’s algorithm to find a MST for the graph G ”’ # Initialize tree T with a single vertex and no edges v = next(iter(…)) … # while the vertex set of T is smaller than the vertex set of G, # (i.e. while the vertex set of T is a proper subset of the # vertex set of G), find the edge e with minimum weight so that # T+e is a tree. Then update T = T+e ”’ … # return T …

Use Prim’s Algorithm

**Problem 6**: Yay! You’ve implemented Prim’salgorithm! Now use it to find a minimal-weight spanning tree forthe graph in the file test1.txt. Use the method draw_subgraph todraw the graph with it’s minimal-weight spanning tree.

In [ ]:

**Problem 7**: Repeat the previous exercise usingthe graph in the file test2.txt

In [1]:

Out[1]:

Ellipsis

## Expert Answer

Answer to Write a function incident_edges that finds all edges from a graph G that are incident with a subgraph T In [63]…