Abstract
Product network 最早是由 Harary 和 Sabidusi在1959年定義的。由於具有優良的特性，所以也受到相當的重視。有一些基礎的演算法是專為product network而設計的如排序。但因為product network也是interconnection network的一種，所以關於容錯方面的研究也有相當多的人在進行。在容錯方面的研究有很多的雛形都是先在要討論的network上找到一個具優良性質的結構。然後再利用這個結構去設計相關的演算法。那能夠找到的優良結構有很多，例如edge不重複的spanning tree或是edge不重複的路徑等。已經有相當多的研究結果發表了，稍後在本篇論文會有更詳盡的介紹。在本篇論文中我們要說明的是如何在一個product network中找到n1+n2個edge-disjoint spanning trees，當構成product network的兩個component graph分別具有n1及n2個edge-disjoint spanning trees。同時我們證明了不是所有的product network都可以找到n1+n2個edge-disjoint spanning trees，必須要滿足某個條件才行。在第二章中先介紹關於product network和edge-disjoint spanning tree的定義。第三章中對一些相關的graph與topology做一簡介。同時對相關論文的結果作一整理。第四章是說明product network需要符合哪些條件才能找到這麼多的edge-disjoint spanning tree。第五章是我們主要的演算法。說明如何去建立n1+n2個edge-disjoint spanning tree。第六章是對我們的演算法做一些必要的補充。第七章即是結論以及未來我們還有什麼方向可以去努力。