通信网络基础11资料.ppt

人有了知识，就会具备各种分析能力， 明辨是非的能力。 所以我们要勤恳读书，广泛阅读， 古人说“书中自有黄金屋。 ”通过阅读科技书籍，我们能丰富知识， 培养逻辑思维能力； 通过阅读文学作品，我们能提高文学鉴赏水平， 培养文学情趣； 通过阅读报刊，我们能增长见识，扩大自己的知识面。 有许多书籍还能培养我们的道德情操， 给我们巨大的精神力量， 鼓舞我们前进。 * * 西安邮电学院通信工程系 郭娟 1. 图的概念（2） 我们也可以用边的两个顶点来表示边。如果边e的两个顶点是u和v，那么e可写成 e=(u,v)，这里（u,v）表示u和v的有序对。 如果有（u,v）和（v,u）同时存在，它表达了以u，v为端点的一条无向边。 如果图中的所有边都是无向边，则 称该图为无向图。 可以这样来表示无向图1-16： G = (V, E) ， V = { v1, v2, v3, v4 }, E = {(v1,v2), (v1,v3), (v1,v4), (v2,v3), (v2,v4), (v3,v4)} 或：E = {(v2,v1), (v3,v1), (v4,v1), (v3,v2), (v4,v2), (v4,v3)} * 西安邮电学院通信工程系 郭娟 1. 图的概念（3） 一般图G = (V, E)的顶点数用 n =(|V|)表示，边的数目用 m=(|??E| )表示。若 V 和 E都是有限的，则称图G是有限图，否则称为无限图。 * 西安邮电学院通信工程系 郭娟 1. 图的概念（4） 在实际应用中，图中每条边可能有一个方向是很自然的（它反映了信息或物质的流向）。当给图G的每一条边都规定一个方向，则称该图为有向图。对有向图图G =(V, E)，有向边e用与其关联的顶点（u，v）的有序对来表示，即e=(u,v)，它表示u为边e的起点，v为边e的终点。 图1-17所示的有向图可表示如下： G = (V, E) ， V = { v1, v2, v3, v4 }, E = { (v1,v2), (v1,v3), (v1,v4), (v2,v3), (v2,v4), (v3,v4) } * 西安邮电学院通信工程系 郭娟 1. 图的概念（5） 如果顶点v是边e的一个端点，则称边e和顶点v相关联(incident)；对于顶点u和v，若(u,v) ∈E，则称u和v是邻接的（adjacent）。在图1-16中，边e2，e4，e5都与顶点v4相关联，v4分别与v1，v2，v3相邻接。 若两条边有共同的顶点，则称这两条边是邻接的。在图1-16中，边e1，e2，e3两两相邻接。 * 西安邮电学院通信工程系 郭娟 1. 图的概念（6） 对图G = (V, E)和G’ = (V’, E’)来说，若有V’?V和E’? E，则称图 G’是图G的一个子图； 若V’ V或E’ E，则称图G’是图G的一个真子图。 * 西安邮电学院通信工程系 郭娟 2． 路径与回路(1) 定义：图的一些顶点和边的交替序列 =v0 e1v1 ...v k-1ekvk，且边ei的端点为vi-1和vi，i=1,2,3,…k，则称?为一条路径（Path），v0和vk分别为?的起点和终点。如果?中所有的边均不相同，则称其为简单路径。以v0为起点，vk为终点的路径称为v0 - vk路径。 如果路径?中有v0=vk，则?为回路(或环Cycle)，回路中没有重复边时称为简单回路。 * 西安邮电学院通信工程系 郭娟 2． 路径与回路(2) 例4： 在图1-18中，S={v1e1v2e3v3e6v4 } 是一路径，C={v1e1v2e3v3e6v4e4v1}是一回路。 * 西安邮电学院通信工程系 郭娟 2． 路径与回路(3) 定义：对图G=(V,E)来说，若G的两个顶点u，v之间存在一条路径，则称u和v是连通的； 若图G的任意两个顶点都是连通的，则称图G是连通的；否则是非连通的。 非连通的图可分解为若干连通的子图。 * 西安邮电学院通信工程系 郭娟 2． 路径与回路(4) 图1-19的无方向图中，图（a）中任意两个顶点之间都有路径，所以该图是连通的； 图(b)中顶点3和其它顶点之间没有路径，所以该图是非连通的； 图（c）则是一个孤立的节点。 * 西安邮电学院通信工程系 郭娟 2． 路径与回路(5) 对于有向图，若边去掉方向后是连通的，则称该图为连通的有向图。 若对于有向图的任意两个顶点u和v之间存在u到v的路径和v到u的路径时，称该图为强连通的。 图1-20（a）的有向图是 一个连通的有向图，但 不是强连通的。因为顶 点2和顶点3之间不存在双向的路径； 图1-20（b）是一个强连通的图，该图中任意两个顶点之间都存在双向的路径。 图1-20 方向图 （a）连通的方向图 (b) 强连