2010-01-14

圖論

請問這題該如何解呢 ?



what are the directed graph in which each vertex has at most one outgoing edge?
還有這題要回答什麼呢?

麻煩解答 謝謝

1 則留言:

線代離散助教(wynne) 提到...

1. 考慮圖中的任一個交點, 因為該交點可將平面分成 2k 個區域, 而這 2k 個區域可依序用 1,2,1,2,...,1,2 來著色, 所以最小著色數為 2

2. 此種 graph 稱為 directed pseudoforest