图与网络学习课件.ppt

* 努力奋斗 * 努力奋斗 * 努力奋斗 图与网络 定义 一个图(Graph ) G是由一个非空有限集合V(G)和V(G)中某些元素的无序对集合A(G)构成的二元组，记为图G=(V(G)，A(G)). 其中V(G) 称为图G的结点集，V(G)中的每一个元素称为该图的一个结点或顶点； A(G)称为图G的边集，A(G)中的每一个元素称为该图的一条边. 记号V(G)和A(G)简记为V和A，而记图G=（V，A）. 有向图:对图G中的每条边赋予一个方向. (有序对; 边称弧） 赋权图: 对图G中的每条边赋予一个或多个实数，得到的图称为或网络(Network). * 例 有向图G=(V，A)，顶点集V= 边集A= 边 * 图的阶(Order) :顶点的个数. 顶点的度（Degree）:与顶点相连的边数. (出度,入度). 相邻点、相邻边、环、多重边. 简单图(Simple Graph): 没有环、且没有多重边的图. 基本概念 链(chain)：由两两相邻的点及其相关联的边构成的点边序列. 如：v0 , e1 , v1 , … , vn－1,en , vn ； v0 , vn 分别称为链的起点和终点 . 路 (Path): 图的不包含重复顶点的链. 圈(Cycle): 起点和终点重合的路. 连通图(Connected Graph) ： 图中任意两点之间均至少有一 条路，否则称作不连通图。 树(tree): 无圈连通图称为树,无圈图称为森林. * 子图(Subgraph): G=（V，A） 称为G的子图(Subgraph) 图的支撑子图 (又称生成子图): 包含G 的所有顶点的子图. Kn的边的数量为 n(n-1)/2 完全图(Complete Graph) ： 若图G的任意两个顶点间有且只有一条边相连，则称其为完全图. n阶完全图记为Kn. 图与网络中的几个重要问题 最短路径问题 最小生成树问题 最小费用最大流问题 * 在6人的聚会中，假设认识是相互的，则必可找出这样的3人，他们或者彼此均认识或者彼此均不认识 。请问这个结论正确吗？ 利用图的方法来描述该问题。将人看成顶点，两人彼此都认识用实线连，否则虚线。 证明： 相识问题（拉姆齐问题） ? 问题转化为在一个6阶图中必存在实线三角形或虚线三角形。 请大家一起画图证明 * υ2 υ1 υ3 υ4 υ6 υ5 υ1 υ2 υ3 υ4 任取一顶点，不妨υ1 考察υ2υ3、υ2υ4和υ3υ4 υ2υ3、υ2υ4和υ3υ4只能是虚线 ，否则得证 但这样三角形υ2υ3υ4的三边均为虚线 ， 得证。 不妨取υ1 υ2 、 υ1 υ3 、 υ1 υ4 实线 与υ1相连的边必然有： 实线条数不小于3或虚线条数不小于3 拉姆齐问题也可这样叙述： 6阶2色完全图中必含有3阶单色完全图。 * 命题1 任一6阶2色完全图中至少含有两个3阶单色完全图。 证明：前面证明必存在3阶单色完全图，不妨设υ1υ2υ3 为红色完全图 υ1υ5、υ2υ5、υ3υ5中至少有两条黑色、故υ1υ5 与υ2υ5中至少有一条是黑色 若υ4υ5υ6也是红色三角形，命题已得证 。反之， 至少一边与υ1υ2υ3的边异色，不妨设υ4υ5黑色 υ1υ4、υ2υ4、υ3υ4至少应有两条黑色，不妨设 υ1υ4 、υ2υ4 黑色 所以存在第二个3阶单色完全图。 υ2 υ1 υ3 υ4 υ6 υ5 其他类似可推出的结果 ： 直接推广：以上结论对于人数大于6人仍成立！ * 命题2 7阶2色完全图至少含有4个3阶单色安全图。 命题3 18阶2色完全图中必含有4阶单色完全图。 对拉姆齐问题的认识不能仅仅停留在本例的水平上。利用逻辑推理方法，实际上还可获得一大批结果。命题2和命题3的证明留给大家自己去完成。 * 最短路径问题 设有一个半径为 r 的圆形湖，圆心为 O。A、 B 位于湖的两侧，AB连线过O，见图。 现拟从A点步行到B点，在不得进入湖中的限 制下，问怎样的路径最近? A B O r * A B O r E F E′