第十四部分图的基本概念教学提纲.ppt

第十四章图的基本概念七桥问题图论棋盘上马的行走路线问题环游世界各国的问题四色猜想图论第十四章图的基本概念第一节：图下面定义一些专门名词：
（１）通常用G表示无向图，D表示有向图，但G也可以泛指图。V(G)，E(G)分别表示G的顶点集和边集。|V(G)|,|E(G)|分别表示G的顶点数和边数，
若|V(G)|＝n，则称G为n阶图。
（２）若|V(G)|,|E(G)|均为有限数，则称G为有限图。
（３）若图G中，边集为空，则称之为零图，
若G为n阶图，则称之为n阶零图，记为Nn，
N1称为平凡图。
（4）顶点集为空的图记为空图。一些定义一些定义一些定义一些定义一些定义一些定义例1握手定理例2例3握手定理的推论可图化、可简单图化可图化的判断定理可图化同构的定义例4例5同构的性质完全图特殊图子图的定义例6例7补图例8图的操作第十四章图的基本概念14.2通路和回路14.2通路和回路例1通路的性质通路和回路的性质通路和回路14.3图的连通性14.3图的连通性连通图连通分支距离点割集、割点点连通度、边连通度的关系距离连通性连通性图的连通性二部图例4二部图第十四章图的基本概念图的矩阵表示图的矩阵表示图的矩阵表示图的矩阵表示图的矩阵表示图的矩阵表示图的矩阵表示A(D)中所有元素之和为D中长度为1的通路的条数
对角线元素之和为D中长度为1的回路的条数
考虑：A(D)的n次幂表示什么？图的矩阵表示令例图的矩阵表示例图的矩阵表示图的矩阵表示图的矩阵表示图的矩阵表示图的矩阵表示图的运算作业