同构子图问题
令 G 为图，δ(G) 为顶点的最小度数。用伪代码描述一个算法，对于给定的具有 k<= δ(G) 边的树 T，应该构建（在多项式时间内）G 的子图 H，以便 H 与 T 同构。
我该如何开始？
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 ?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
好吧，您肯定需要从图的一个节点开始，该节点的邻居数至少与树根的子节点数一样多。
答案在某种程度上取决于你的教授所说的 k <= delta(G) 边的含义。如果他的意思是我认为他的意思，即树中的边数与“峰值”节点的邻居数一样多或更少，那就大大简化了事情。一方面，它暗示您需要找到一个峰值节点。如果他所说的“峰值”是指比其任何邻居具有更高度数的节点，则您可以通过从一个节点开始然后选择度数更高的邻居来发现这样的节点，并根据需要重复。
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.
这里的主要问题是多项式时间，但为了给您一个入门机会，您应该从树的根和图的节点开始（我相信找到节点是主要挑战之一），然后从那个地方开始应该建立你的树。
请注意，任何 DFS 或 BFS 类型的算法都无法解决问题，因为它们不是多项式
希望我可以提供帮助！
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!
通过知道 T 具有 δ(G) 最大边，我可以从 G 中的任何节点开始，并通过选择任何节点在 G 中构建 T，因为我总是有足够的边和顶点。复杂度为 O(n)。
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).