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]…