A crab graph is an undirected graph of the following form: there are three speci

Question

A crab graph is an undirected graph of the following form: there are three special vertices called the sting, the tail and the body with degrees 1, 2 and n-2 respectively. As shown below, the sting is only connected to the tail, the tail is connected to the body (as well as the sting), and the body is connected to all the vertices other than the sting. The remaining vertices in the graph have arbitrary connections among one another, but are not connected to the sting or the tail.

Suppose that we are given an arbitrary graph represented using an adjacency matrix. Describe carefully an algorithm that makes only O(n) probes into this matrix, and determine whether or not the input graph is a crab graph

Explanation / Answer

A crab is an undirected graph which has two kinds of vertices: 1 head, and K feet , and exactly K edges which join the head to each of the legs.( 1 <= K <= T, where T is given)

Given an undirected graph, you have to find in it some vertex-disjoint subgraphs where each one is a crab . The goal is to select those crabs in such a way that the total number of vertices covered by them is maximized.

Note: two graphs are vertex-disjoint if they do not have any vertex in common.

solving the above problem by vertex cover approach results in exponnetial tim algorithm but this can be solved by maximising flows usng ford fuckerson algorithm Above problem can be solved using Ford Fulkerson.

Ford Fulkerson Algorithm to find max flow in the given Graph

Repeat the above 4 steps till no augmenting path possible.

Chose one possible path and identify the edge with the smallest capacity. Record this number Substract this number from each number on that path. This is the new capacity for each arc long the path. Chose another route and repeat step 1 once again record the smallest capacity. Repeat untill all possible path are exhausted. Add the smallest capacities of all routes. This is the minimum carrying capacity of the network

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.