2.1树及其性质 树:一类极其简单然而却很有用的图 今例4 o已知有五个城市,要在它们之间架设电话线,要 求任何两个城市都可以互相通话(允许通过其他城 市),并且电话线的根数最少。 图10-11 清华大学出版社
v 树：一类极其简单然而却很有用的图。 v 例4 ¢ 已知有五个城市，要在它们之间架设电话线，要 求任何两个城市都可以互相通话(允许通过其他城 市)，并且电话线的根数最少。 图10-11 2.1 树及其性质 清华大学出版社 27
2.1树及其性质 令用五个点v1,12,n3,v4,v代表五个城市,如 果在某两个城市之间架设电话线,则在相应的 两个点之间连一条边,这样一个电话线网就可 以用一个图来表示。为了使任何两个城市都可 以通话,这样的图必须是连通的。其次,若图 中有圈的话,从圈上任意去掉一条边,余下的 图仍是连通的,这样可以省去一根电话线。因 而,满足要求的电话线网所对应的图必定是不 含圈的连通图。图10-11代表了满足要求的一个 电话线网。 清华大学出版社
2.1 树及其性质 v 用五个点v1，v2，v3，v4，v5代表五个城市，如 果在某两个城市之间架设电话线，则在相应的 两个点之间连一条边，这样一个电话线网就可 以用一个图来表示。为了使任何两个城市都可 以通话，这样的图必须是连通的。其次，若图 中有圈的话，从圈上任意去掉一条边，余下的 图仍是连通的，这样可以省去一根电话线。因 而，满足要求的电话线网所对应的图必定是不 含圈的连通图。图10-11代表了满足要求的一个 电话线网。 清华大学出版社 28
2.1树及其性质 定义1(树的定义) o一个无圈的连通图称为树。 例5某工厂的组织机构如下所示 厂长 行政办公室 生产办公室 工厂组织机构图生技供 四 术销 车军军军 设王 科科 段 清华大学出版社
2.1 树及其性质 v 定义1（树的定义） ¢ 一个无圈的连通图称为树。 v 例5 某工厂的组织机构如下所示 清华大学出版社 29
2.1树及其性质 如果用图表示,该工厂的组织机构图就是一 个树(如图10-12所示) 树 图10-12 清华大学出版社
2.1 树及其性质 v 如果用图表示，该工厂的组织机构图就是一 个树(如图10-12所示)。 树 图10-12 清华大学出版社 30
2.1树及其性质 定理3设图G=(V,E)是一个树,p(G)≥2,则G中 至少有两个悬挂点。 o证明令p=(v1,"2…,v)是G中含边数最多的一条初等链,因 p(G)≥2,并且G是连通的,故链P中至少有一条边,从而v1与vk 是不同的。现在来证明:v1是悬挂点,即d(v1)=1 o用反证法,如果d(v1≥2,则存在边[vm使m+2。若点vn不在P 上,那么(vn,",n2,…v是G中的一条初等链,它含的边数比P多 条,这与P是含边数最多的初等链矛盾。若点v在P上,那么 (的…仚腳)这与树的定义矛盾。于是必有d(v1)=1,即v是 悬挂点。同理可证v也是悬挂点,因而G至少有两个悬挂点 清华大学出版社
v 定理3 设图G=(V，E)是一个树，p(G)≥2，则G中 至少有两个悬挂点。 ¢ 证明:令 是G中含边数最多的一条初等链，因 p(G)≥2，并且G是连通的，故链P中至少有一条边，从而v1与vk 是不同的。现在来证明：v1是悬挂点，即d(v1)=1。 ¢ 用反证法，如果d(v1)≥2，则存在边 使m≠2。若点vm不在P 上，那么 是G中的一条初等链，它含的边数比P多 一条，这与P是含边数最多的初等链矛盾。若点vm在P上，那么 是G中的一个圈，这与树的定义矛盾。于是必有d(v1)=1，即v1是 悬挂点。同理可证vk也是悬挂点，因而G至少有两个悬挂点。 2.1 树及其性质 ( ) 1 2 k p v ,v ,,v v1 ,vm ( ) m 1 2 k v ,v ,v ,,v 1 ( ) 1 2 m v ,v ,,v ,v 清华大学出版社 31