Answers to the graph theory chapter 2 after-school exercises!
Necessity is obvious, only sufficiency is proved.
Use mathematical induction.
When n=2, there are 2 points with degree: d1+d2=2.
And since d1 and d2 are natural numbers, d1=d2=1, a tree.
Assuming that <n holds, we examine the situation at n.
There are n points, and the sum of the degrees is: 2(n-1)
By the principle of the drawer, there is at least 1 point with degree 1, let d1=1
Still by the principle of the drawer, when n>=3, there is at least 1 point with degree 2, let d2=2
Let’s connect an edge between d1, d2, and then examine the relationship of remaining vertices to the degree. relationship.
If the remaining vertices can form a tree with degrees, then adding this edge between d1 and d2 still forms a tree.
Number of vertices left: the point d1 is missing, so it’s n-1 vertices.
The total number of degrees left: 2 degrees less, so it’s 2(n-1)-2=2(n-2).
By the induction hypothesis, the rest can form a tree.
The proof is complete.
Graph Theory, Algorithms
I think a lot of people who study graph theory know that J.A. Bondy and U.S.R. Murty’s GraphTheorywithApplication (Elsevier, 1976) is a classic graph theory textbook, and to this day, it’s still a good introductory book for beginners. I still remember that Prof. Zhang Zhongfu from Lanzhou Jiaotong University said that the first graph theory society in China gathered everyone to study Bundy’s GraphTheorywithApplication, which shows that the influence of this book on the domestic graph theory session is so great. Wu Wangming and others translated it into Chinese version of Graph Theory and its Application (Beijing: Science Press, 1984), and in 1988, Zhang Kemin and others prepared a reference answer to the book, Graph Theory and its Application Exercise Answers (Tsinghua University Press, 1988).
In 2008, J.A. Bondy and U.S.R. Murty published a new book, GraphTheory (GTM244, Springer, 2008), which can be regarded as the second edition of GraphTheorywithApplication. After all, in the nearly 30 years since the publication of the first edition, many new results have emerged, so GraphTheory has added some new results to its content. I just read a few chapters of this book, and I think it is very well written, so I suggest that you read it, and it is worth mentioning that the 50 questions posed at the end of the first edition have been updated, and some new questions have been added. All in all, I personally think that GraphTheory is indeed an excellent graph theory textbook.
The links to these two textbooks and their answers are given below (I would like to express my thanks to the providers of the resources, if the following links do not work, please do it yourself or google):
1. Download of the English version of GraphTheorywithApplication:
http://old.math.org. cn/forums/index.php?showtopic=57282
http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html
2. GraphTheorywithApplication” Chinese version download: http://old.math.org.cn/forums/index.php?showtopic=54871
3.GraphTheorywithApplication” answer download:
http://old.math.org.cn/forums/index.php?showtopic=54878
4. GraphTheory download:
http://ifile.it/5kdc19/1846289696. pdf.zip
This article is from the CSDN blog, reproduced please indicate the source: http://blog.csdn.net/zhaoyang17/archive/2009/08/27/4491066.aspx
This article is from the CSDN blog, reproduced please indicate the source: http:// blog.csdn.net/zhaoyang17/archive/2009/08/27/4491066.aspx
This article is from the CSDN blog, reproduced please indicate the source: http://blog.csdn.net/zhaoyang17/archive/2009/08/ 27/4491066.aspx