組合數學研討會
主講者: | 顏華菲教授 (Texas A&M University) |
講題: | Parking Functions, Graph Search, and the Tutte Polynomial |
時間: | 2011-05-18 (Wed.) 15:00 - 16:00 |
地點: | 數學所 722 研討室 (台大院區) |
Abstract: | We present the relation between parking functions and the Tutte polynomial of a general graph $G$ by a combinatorial approach. The main step is to construct a family of graph searching algorithms which induce bijections between the spanning forests of a graph and the generalized parking functions associated with the graph. In particular, the bijection induced by the breadth-first search leads to a new characterization of the external activity, and hence a representation of Tutte polynomial. |
|| Close window || |