 [求助] 如何证明这道图论题？
Definition 1: Let G = <V,E> be a graph. If X is another graph and {V_x | x∈V(X)} is a partition of V into connected subsets such that, for any two vertices x,y∈X, there is a V_x-V_y edge (i.e. an edge (i,j) where i∈V_x and j∈V_y) in G if and only if (x,y)∈ E(X), we call G "an MX" and write "G = MX". If G=MX is a subgraph of another graph Y, we call X "a minor of Y". Definition 2: If we replace the edges of X with independent paths between their ends (so that none of these paths has an inner vertex on another path or in X), we call the graph G obtained "a subdivision of X" and write "G = TX". If G=TX is the subgraph of another graph Y, then X is "a topological minor of Y". Problem: show that, if Δ(X) ≤ 3, then every MX contains a TX; thus, every minor with maximum degree at most 3 of a graph is also its topological minor.
|
[返回] W3CHINA.ORG讨论区 - 语义网·描述逻辑·本体·RDF·OWL →
计算机理论与工程 → 『 理论计算机科学 』 → [求助] 如何证明这道图论题？
(订阅本版)
2005/3/20 9:19:00
顶端 
such a easy problem~~~the only thing you need to..(455字) － ljb，2005年3月20日
新浪微博
