Question

Give a linear-time algorithm that takes as input a tree and determines whether it has a perfect matching: a set of edges that touches each node exactly once.

A feedback edge set of an undirected graph G(V,E) is a subset of edges$\mathbf{E}\mathbf{\text{'}}\underline{\underline{\mathbf{\subset }}}\mathbf{}\mathbf{E}$that intersects every cycle of the graph. Thus, removing the edges will render the graph acyclic.

Give an efficient algorithm for the following problem:

Input: Undirected graph G(V,E) with positive edge weights ${\mathbf{w}}_{\mathbf{e}}$.

Output: A feedback edge set $\mathbf{E}\mathbf{\text{'}}\underline{\underline{\mathbf{\subset }}}\mathbf{}\mathbf{E}$minimum total weight $\mathbf{\sum }_{\mathbf{e}\mathbf{\in }\mathbf{E}\mathbf{\text{'}}}{\mathbf{w}}_{\mathbf{e}}$.

Short answer

A linear-time algorithm that takes as input a tree and it has a perfect matching a set of edges that touches each node exactly once is shown below with assumptions.

The algorithm for the given problem is stated in the steps.

Step-by-step solution

Perfect matching.

An Undirected graph with positive edge weights which shows a feedback edge set of minimum total weight is proved by perfect matching.

Algorithm

All the edges which are able to connect to a leaf node, the leaf node is a node that is present in the lower level or no other node or vertex is connected to that vertex is called a leaf node. And then add this to the solution, and remove the touched edges from the graph. If, at the end of this process, any remaining nodes are left untouched, then there exists no perfect matching.

The graph is a tree, and there must be the existence of leaf nodes, nodes with one edge and no children. In order for this node to be included in the perfect matching, that edge is must to be exist in the final solution.AnUndirected graph with positive edge weights which shows a feedback edge set of minimum total weight.In the sequence for a graph, the first step is to find the connected components. Anedge set of an undirected graph contain number of vertices and edges is a subset of edges that intersects every cycle of the graph. Thus, removing the edge will render the graph acyclic.

Or every edge in the graph is connects two vertices, they belong to at most one of the connected components. Then, only the perfect matching is found for each connected component.

And the algorithm is linear in time that is: O (V+E) .

For each leaf in the tree:

1. Add edge from leaf to its parent to the solution.
2. Delete edge from leaf to its parent.
3. Delete all edges from the parent to any other vertices.
4. Delete leaf and parent from the tree.
5. Perfect matching is found for each connected component.

If the tree is empty then only the perfect matching is possible either there is no perfect matching.

And the tree must be following some conditions they are as follows:

• A tree is an undirected, connected, and acyclic graph.
• A linear-time algorithm on a graph.
• the tree should be empty then only the perfect matching is possible
• the tree must have an even number of nodes, otherwise there is no perfect matching.

If we remove all vertices in this manner, then found a perfect matching.

Notice that, while the removal may disconnect the graph, it will remain acyclic and this is what matters. Disconnecting the graph essentially splits the tree into multiple trees, so the iteration continues to make sense even in this case.

Now, this problem shows up in the chapter about greedy algorithms, so this approach seems like a natural fit.

Here for the algorithm as input an undirected graph G(V,E) with positive edge weights $w_e$. Is given and here show a feedback edge set localid="1658913888603" $\mathrm{E}\text{'}\notin \mathrm{E}$of minimum total weight $\sum _{\mathbf{e}\mathbf{\in }\mathbf{E}\mathbf{\text{'}}}{\mathrm{W}}_{\mathrm{e}}$.

proof of the algorithm is given as:

Let a feedback edge set always exists in graph G, and suppose that it contains an edge with positive edge weights $w_{\mathit{e}}$. now, show that there exists a feedback edge set or not containing weight at most the weight.

Let$C_e{C}_e$denote the set of cycles in the graph such that, $C\cap F=\left\{e\right\}C\cap F=\left\{e\right\}$

(i.e. cycles with not any other edge from weight$\sum _{\mathbf{e}\mathbf{\in }\mathbf{E}\mathbf{\text{'}}}{\mathrm{w}}_{\mathrm{e}}$).

Assume,

$\left|Ce\right|=1\left|Ce\right|=1:$if it is zero,

Then the back edge is a feedback edge set $E\text{'}\notin E$ with weight at most the weight$\sum _{\mathrm{e}\in \mathrm{W}\mathbf{E}\mathbf{\text{'}}}{\mathrm{w}}_{\mathrm{e}}$, if it is at least twenty-two, then let,

$C_1,C_2\in C_e{C}_1,C_2\in C_e,C_1\ne C_2{C}_1\ne C_2.C_1∆C_2{C}_1∆C_2$

is a cycle (or a family of disjoint cycles) not containing back edges, and by definition of $C_e{C}_e$not containing any edge from forward edge, which is a contradiction because $\sum _{\mathbf{e}\mathbf{\in }\mathbf{E}\mathbf{\text{'}}}{\mathrm{w}}_{\mathrm{e}}$is a feedback edge set $\mathrm{E}\text{'}\notin \mathrm{E}$. The cycle in $C_e{C}_e$must contain an edge. that,

$w(e\text{'})\le w\left(e\right)w(e\text{'})\le w\left(e\right)$after Iterating this argument, we can show that there exists a MWFES without edges.

Finally, each fundamental cycle must be covered by an edge from the feedback edge set , so a feedback edge set$\mathrm{E}\text{'}\notin \mathrm{E}$ without edges must contain all the edges. that there exists a feedback edge set or not containing weight at most the weight.