The Hamiltonian Circuit Algorithm
2004年8月 · Institute of Mathematics
5.0star
1 則評論report
電子書
36
頁數
report評分和評論未經驗證 瞭解詳情
關於這本電子書
We present a new polynomial-time algorithm for finding Hamiltonian circuits in graphs. It is shown that the algorithm always finds a Hamiltonian circuit in graphs that have at least three vertices and minimum degree at least half the total number of vertices. In the process, we also obtain a constructive proof of Dirac’s famous theorem of 1952, for the first time. The algorithm finds a Hamiltonian circuit (respectively, tour) in all known examples of graphs that have a Hamiltonian circuit (respectively, tour). In view of the importance of the P versus NP question, we ask: does there exist a graph that has a Hamiltonian circuit (respectively, tour) but for which this algorithm cannot find a Hamiltonian circuit (respectively, tour)? The algorithm is implemented in C++ and the program is demonstrated with several examples.
評分和評論
5.0
1 則評論
關於作者
Ashay Dharwadker is the Distinguished Professor of Mathematics & Natural Sciences at the Institute of Mathematics, Gurgaon, India. He is the author of a dozen exquisitely illustrated books describing his fundamental contributions to combinatorics, graph theory, computer science and the foundations of physics.
為這本電子書評分
請分享你的寶貴意見。
閱讀資訊
智能手機和平板電腦
手提電腦和電腦
你可以使用電腦的網絡瀏覽器聆聽在 Google Play 上購買的有聲書。
電子書閱讀器及其他裝置
如要在 Kobo 等電子墨水裝置上閱覽書籍，你需要下載檔案並傳輸到你的裝置。請按照說明中心的詳細指示，將檔案傳輸到支援的電子書閱讀器。
