Â¥Ö÷

[ÇóÖú] ÈçºÎÖ¤Ã÷ÕâµÀͼÂÛÌ⣿ 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.    Êղؠ  ·ÖÏí   ¶¥(0)

----------------------------------------------
Three passions, simple but overwhelmingly strong, 
have governed my life: the longing for love, the
search for knowledge, and unbearable pity for the
suffering of mankind.
                            - Bertrand Russell

	µÚ2Â¥

such a easy problem~~~ the only thing you need to do is to find a brance node in one brance set in one brance set, there is at most three node which connects other three different branch set(since \triangle(X)<=3.),call this three node output pick a path connects two output, and pick an other path connect the 3rd output to the previous path. the intersecting node is brance node. retaining these paths and edges between brance set leaves a TX.

	µÚ3Â¥

I think you are reading Dxxxx's book, so i use that book's term~~~ good book&good luck~:)

	µÚ4Â¥

Yep. That's great! Thank you very much! :) PS: Yes, I am reading Reinhard's book. It's really great (though some contents are a little bit too much for me......). ÒÔÏÂÊÇÒýÓÃljbÔÚ2005-3-20 22:00:08µÄ·¢ÑÔ£º such a easy problem~~~ the only thing you need to do is to find a brance node in one brance set in one brance set, there is at most three node which connects other three different branch set(since \triangle(X)<=3.),call this three node output pick a path connects two output, and pick an other path connect the 3rd output to the previous path. the intersecting node is brance node. retaining these paths and edges between brance set leaves a TX.

----------------------------------------------
Three passions, simple but overwhelmingly strong, 
have governed my life: the longing for love, the
search for knowledge, and unbearable pity for the
suffering of mankind.
                            - Bertrand Russell

	µÚ5Â¥

~~~~~~~ some content are not that useful for CSer,such as "extremal graph theory and ramsey theory" I think,although they are really beautiful theory.

	µÚ6Â¥

IC. Thanks for your advice. :) ÒÔÏÂÊÇÒýÓÃljbÔÚ2000-1-1 9:12:08µÄ·¢ÑÔ£º ~~~~~~~ some content are not that useful for CSer,such as "extremal graph theory and ramsey theory" I think,although they are really beautiful theory.

----------------------------------------------
Three passions, simple but overwhelmingly strong, 
have governed my life: the longing for love, the
search for knowledge, and unbearable pity for the
suffering of mankind.
                            - Bertrand Russell