The isomorphic subgraph problem

Let G be a graph and δ(G) the minimum degree of a vertex. Describe an algorithm in pseudocode that, for a given tree 开发者_如何学编程T with k<= δ(G) edges, should be build (in polinomial time) a sub-graph H of G so that H is isomorphic with T.

How do I even start ?

---

Well, you definitely need to start at a node of your graph that has at least as many neighbors as the root of your tree has children.

The answer depends a little bit on precisely what your professor means by k <= delta(G) edges. If he means what I think he means, that there are as many or fewer edges in the tree than there are neighbors of a 'peak' node, that simplifies things quite a bit. For one thing, it hints that you need to find a peak node. If he means by 'peak' a node that has a higher degree than any of it's neighbors, you might be able to discover a node like that by starting at a node and then choosing a neighbor of higher degree, repeat as needed.

---

The main issue here is the polynomial time, but to give you a starter, you should start on the root of your tree and in a node of your graph( i believe finding the node is one of the major challenges) and from that place you should build your tree.

Notice that any DFS or BFS type algorithms won't do the trick, because they're not polynomial

Hope I can help!

---

By knowing that T has δ(G) maximum edges I can start from any node in G , and build T in G by choosing any node because I will have always enough edges and vertexes. Complexity is O(n).