西北工业大学《离散数学（第6版）》课件-第8章图论原理.pdfVIP

第三部分 图论 2008-2018 by Li Weigang. All rights reserved. 第三部分 图论 图论是用图的方法研究客观世界的一门科学； 用结点表示事物，用边表示事物间的联系，结点和边构成的 图表示所研究的客观对象； 图论中所关注的并不是图的几何状态，而是其抽象结构性质； 将结点组成集合，将边看成集合上的关系，所以图论是从结 构观点研究关系的一门学科。 主要内容  图论的基本原理  欧拉图、哈密顿图  树 2 第八章 图论原理 3 2008-2018 by Li Weigang. All rights reserved. 主要内容  图 通路、回路与图的连通性  欧拉图  哈密顿图  图的矩阵表示 预备知识  多重集合——元素可以重复出现的集合 无序集——AB={(x,y ) | x Ay B} 4 8.1 图的基本概念 18 历史背景： 世纪的哥尼斯堡七桥问题与欧拉图 5 图的定义 8.1 G = V,E, 定义 无向图 其中 (1) V 为顶点集，元素称为顶点 (2) E为VV 的多重集，其元素称为无向边，简称边 实例 设 V = {v , v , …,v }, 1 2 5 E = {(v ,v ), (v ,v ), (v ,v ), (v ,v ), 1 1 1 2 2 3 2 3 (v ,v ), (v ,v ), (v ,v )} 2 5 1 5 4 5 则G = V,E为一无向图 6 有向图 8.2 D= V,E, E VV 定义 有向图 只需注意 是 的多重子集 2 V E 图 表示的是一个有向图，试写出它的 和 注意：图的数学定义与图形表示，在同构（待叙）的意义下 是一一对应的 7 相关概念 1. 图 ①可用 泛指图（无向的或有向的） G ② V(G), E(G), V(D), E(D) n n ③顶