| Abstract | 第3-4页 |
| 摘要 | 第5-7页 |
| Chapter 1 Introduction | 第7-14页 |
| 1.1 The background and related work of belief propagation | 第7-11页 |
| 1.2 Our results | 第11-12页 |
| 1.3 Organization | 第12-14页 |
| Chapter 2 The Chinese postman problem in undirected graph | 第14-27页 |
| 2.1 Min-Sum BP algorithm | 第15-16页 |
| 2.2 Main result | 第16-17页 |
| 2.3 Convergence of BP for UCPP | 第17-27页 |
| 2.3.1 Computation tree | 第17-18页 |
| 2.3.2 Main technical lemmas | 第18-24页 |
| 2.3.3 Extension to arbitrary undirected graph | 第24-27页 |
| Chapter 3 The Chinese postman problem in directed graph with capacity | 第27-38页 |
| 3.1 Linear programming relaxation | 第27-29页 |
| 3.2 Complementary slackness conditions | 第29-30页 |
| 3.3 The algorithm and result for DCPPC | 第30-31页 |
| 3.4 Convergence of BP for DCPPC | 第31-37页 |
| 3.5 The case when εis not well-defined | 第37-38页 |
| Chapter 4 Asynchronous BP for the Chinese postman problem | 第38-40页 |
| Chapter 5 Conclusion | 第40-41页 |
| Bibliography | 第41-47页 |
| 致谢 | 第47页 |
