證明最小生成樹環交集問題之猜想

給定一圖G和其一生成樹T，每條在G-T的邊e會在T∪{e}中產生一個環，我們把那些邊稱作環邊；那些環稱作樹環。兩個樹環的交集為其所有共有的邊形成的集合，若兩相異樹環的交集是非空的，我們將其視為一次交集。生成樹T的樹交集數為其所有樹環的交集次數。最小生成樹環交集問題旨在找出圖的所有生成樹中樹交集數最小的生成樹。Dubinsky等人提出一猜想，此猜想敘述為若一圖有一星形生成樹，星形生成樹為其中一點和其它所有點都相鄰的生成樹，則此星形生成樹有最小的樹交集數。在此論文中，我們證明此猜想，並探討其延伸的可能性。

關鍵字

圖；生成樹；環

並列摘要

Let G be a graph and T a spanning tree of G. For an edge e in G−T, there is a cycle in T∪{e}. We call those edges cycle-edges and those cycles tree-cycles. The intersection of two tree-cycles is the set of all edges in common. If the intersection of two distinct tree-cycles is not empty, we regard that as an intersection. The tree intersection number of T is the number of intersections among all tree-cycles of T. The Minimum Spanning Tree Cycle Intersection (MSTCI) problem aims to find a spanning tree with minimum tree intersection number among all possible spanning trees. In this thesis, we prove the conjecture, posed by Dubinsky et al., which states that if a graph admits a star spanning tree in which one vertex is adjacent to all other vertices, then the star spanning tree has the minimum tree intersection number and investigate the possibility of generalizing the conjecture.

並列關鍵字

Graph ； Spanning Tree ； Cycle

參考文獻

E. Amaldi, L. Liberti, F. Maffioli, and N. Maculan. Edge-swapping algorithms for the minimum fundamental cycle basis problem. Mathematical Methods of Operations Research, 69(2):205–233, 2009.

Google Scholar

A. Cassell, J. d. C. Henderson, and K. Ramachandran. Cycle bases of minimal measure for the structural analysis of skeletal structures by the flexibility method. Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences, 350(1660):61–70, 1976.