例题 画出所有的6个顶点的非同构的树。 解:所要画的树有6个顶点,则边数为5,因此 6个顶点的度数之和为10,可以产生以下五种 度数序列 (1)111115 东南大学计算机科学与工程学院 同的出学 图论
例题 画出所有的6个顶点的非同构的树。 解：所要画的树有6个顶点，则边数为5，因此 6个顶点的度数之和为10，可以产生以下五种 度数序列： (1) 1 1 1 1 1 5 T1
(2)1 1924 (3)1191133 (4)111223 (5)112222 东南大学计算机科学与工程学院 同的出学 图论
(2) 1 1 1 1 2 4 T2 (3) 1 1 1 1 3 3 T3 (4) 1 1 1 2 2 3 T4 T5 (5) 1 1 2 2 2 2 6 T
生成树 定义162如果无向图G的生成子图T是树,则称T是G的生成树。 设T是G的生成树,G的在T中的边称为T的树枝,不在T 中的边称为T的弦。称T的所有弦的导出子图为T的余树, 记为T 余树可能存在回路 余树不一定连通 东南大学计算机科学与工程学院 同的出学 图论
定义 16.2 如果无向图G的生成子图T是树，则称T是G的生成树。 设T是G的生成树，G的在T中的边称为T的树枝，不在T 中的边称为T的弦。称T的所有弦的导出子图为T的余树， 记为 T
生成树存在的充要条件 定理163无向图G有生成树当且仅当G是连通图。 若G有生成树,显然各个顶点之间是连通的。必要性得证 当G是连通图时,若G中不存在回路,则G本身就可以作为生成树。 若G中存在圈,则可以选取任意一个圈,并删除其中一条边,仍可保 持G的连通性;若还存在圈,则可重复该动作,直到最后G中不存在 圈。由此可以得到生成树。 推论设G为n阶m条边的无向连通图,则m≥n-1 东南大学计算机科学与工程学院 同的出学 图论
定理 16.3 无向图G有生成树当且仅当G是连通图。 若G有生成树，显然各个顶点之间是连通的。必要性得证 当G是连通图时，若G中不存在回路，则G本身就可以作为生成树。 若G中存在圈，则可以选取任意一个圈，并删除其中一条边，仍可保 持G的连通性；若还存在圈，则可重复该动作，直到最后G中不存在 圈。由此可以得到生成树。 推论 设G为n阶m条边的无向连通图，则m≥n-1
生成树与弦 定理164设T为无向连通图G中一棵生成树,e为T的任意一条弦, 则TUe中含G中只含一条弦其余边均为树枝的圈,而且 不同的弦对应的圈也不同。 东南大学计算机科学与工程学院 同的出学 图论
定理 16.4 设T为无向连通图G中一棵生成树，e为T的任意一条弦， 则T∪e中含G中只含一条弦其余边均为树枝的圈，而且 不同的弦对应的圈也不同