[原创]关于网络图论的一个命题

我不会

[watermark]注：图论在电路中的应用称为“网络图论”。
为了证明本文的主要结果，先介绍几个基本概念。
定义1：3条或3条以上支路的交点称为结点。
定义2：从一个图的某一个结点出发，沿着一些支路移动而到达另一结点（或回到出发点），这样的一系列支路称为一条路径。一条支路本身也算为路径。
定义3：当图的任意两个结点之间至少存在一条路径时，该图称为连通图。
定义4：如果一条路径的起点和终点重合，且经过的其他结点不重复出现，这条闭合路径就构成图的一个回路。
定义5：包含图的全部结点且不包含任何回路的连通子图称为连通图的树。树中包含的支路称为该树的树支。
下面的论断是有用的。
引理：在图的任何树中，任意两个结点之间的路径有且只有一条。
证明：如果存在两个结点，它们之间的路径有两条，那么就已经构成一个回路，这与树的定义矛盾。
下面的结论的证明是我独立得到的。
定理：任一个具有n 个结点的连通图，它的任何一个树的树支数为（n－1）。
证明：对于图G的任何给定的树T，我们总可以这样处理，在树T中任意选取一个结点，标记为1号。将与之直接相连的结点都标记为2号，依次为2A,2B,2C……，与所有2号结点直接相连的结点都标记为3号，依次为3A,3B,3C……，……………………重复上述步骤，直到将所有n个结点都标记完为止。这样一来，除对1号结点外的每个结点而言，与之直接连接的前一号结点都唯一确定，不妨将直接连接的两个结点之间的支路算作后者“所有”。从而除1号结点外，每个结点都对应一条支路（这里的对应是一一对应）。所以，树T中的支路数为（n－1）。如果在树中增加一条支路，由于树是连通的，所以这必然会产生一条回路，与树的定义矛盾。另一方面，若减少任意一条支路，根据引理1的结论，树T将不再连通，也构成矛盾。综上所述，树T的树支总数为（n－1）。证毕。
[/watermark]