[離散] 一些樹的問題

[Amulart (要衝刺!!!)]

1. Prove that in every tree, any two paths with maximum length have a node in

   common. This is not true if we consider two maximal paths.



2. Find a spanning tree for which (a) the product of the edge-costs is minimal

   (b) the maximum of the edge-costs is minimal  (Some edge-costs are positive)



3.If every node of a planar map has even degree, then the faces can be

  2-colored.



4.Consider any table with 2 rows and n-1 columns; the first row holds 1,2,...,

  n-1; the second row holds arbitrary numbers between 1 and n. Construct a

  graph on nodes labeled 1,...,n by connecting the two nodes in each column of

  our table.

  (a) Prove that if the graph is connected, then it is a tree.

  (b) Prove that every connected component of this graph contains at most one

      cycle.

這些題目想不到解法，希望板上大大能給小弟一些提示，謝謝
--
※ 編輯: Amulart         來自: 140.117.120.229      (06/09 20:49)
推 hcsoso      :1. 反證法, 考慮兩條 paths 的四個頂點的關係
→ hcsoso      :2. 圖是什麼?
→ hcsoso      :3. bipartite graph iff no odd cycles
→ hcsoso      :4. 這個圖的 maximum degree 是?
→ hcsoso      :阿 sorry 4. 不對, 我看錯題目了...
→ hcsoso      :4. (a) 邊的總數
→ hcsoso      :4. (b) 考慮用有向邊, 觀察一個關於 degree 的性質