图的基本概念.ppt

图论的产生背景 1.生活中的图 交通图，通讯网络图等 2.图论的起源 哥尼斯堡的七桥问题 3.应用：计算机科学、化学、运筹学、社会学等领域 1.无序积： 2.无向图：一个无向图G是一个二元组V,E，即G=V,E其中 （1）V={v1,v2,…,vn}是非空集合，称为G的顶点集，V中的元素称为顶点或结点； （2）E ={e1,e2,…,en}是无序积VV的一个多重子集，称E为G的边集，E中的元素称为无向边或简称边。 3.相关基本概念 如果边e=(vi,vj)，则称vi,vj是e的端点，顶点vi(或vj) 关联于边e，当vi=vj称e为环。与一条边相关联的两个顶点称为邻接的或相邻的。若几条边关联于一公共顶点，称这些边是邻接的或相邻的。如果两个顶点间的边数多于一条，称这些边为平行边，平行边的边数称为重数。没有边关联的顶点称为孤立点。关联顶点v的边数（当边为环时，按两条边计算）称为v的度数，记为deg(v). 度数为1的顶点为悬挂顶点，它所对应的边称为悬挂边 4.图的分类及特殊的图 若V，E均为有穷集合，则称G为有限图，否则称为无限图。以后我们只讨论有限图。 若|V|=n,则称图G为n阶图。 若E= ，则称G为零图，若|V|=1，E= ，则称图G为平凡图。 有m条边的n阶图称也称(n,m)图。 既不含环，也不含平行边的图称为简单图。 设G=V,E为n阶无向简单图，若G中任意两个顶点都有边相连，则称图G为n阶无向完全图，记作Kn。n阶无向完全图共的n(n-1)/2条边，每个顶点的度数为n-1 5.有向图及相关概念 5.有向图及相关概念 5.有向图及相关概念 5.有向图及相关概念 5.有向图及相关概念 5.有向图及相关概念 6.同构 判断下列各组图是否同构 6.同构 7.子图 7.子图 8.补图 8.补图 9.删去图中的顶点和边 7.通路与回路 7.通路与回路 7.通路与回路 7.通路与回路 7.通路与回路 8.连通性 8.连通性 8.有向图的连通性 8.有向图的连通性 8.有向图的连通性 * * A B C D v1 v2 v3 v4 e1 e2 e3 e4 e5 e6 e7 v1 v2 v3 v4 e1 e2 e3 e4 e5 e6 例1 （1）（3，3，2，3），（5，2，3，1，4）能成为图的度数序列吗？为什么？ （2）已知图G中有10条边，4个3度顶点，其余顶点的度数均小于等于2，问G中至少有多少个顶点？为什么？ v4 e6 v1 v2 v3 e1 e2 e3 e4 e5 v4 e6 v1 v2 v3 e1 e2 e3 e4 e5 v4 e6 v1 v2 v3 e1 e2 e3 e4 e5 v4 e6 v1 v2 v3 e1 e2 e3 e4 e5 v4 e6 v1 v2 v3 e1 e2 e3 e4 e5 （1） （2） 彼得森图（略） （3） 例：（1）画出4个顶点3条边的所有可能非同构的无向简单图， （2）画出3个顶点2条边的所有可能非同构的有向简单图。 写出下面图的补图: v1 v2 v3 v4 e1 e2 e3 e4 e5 e6 v1 v2 v3 v4 e1 e2 e3 e4 e5 e6 v1 v2 v3 v4 e1 e2 e3 e4 e5 e6 e6 v1 v2 v3 e1 e2 e3 e4 e5 e6 v1 v2 v3 e1 e2 e3 e4 e5 e6 v1 v2 v3 e1 e2 e3 e4 e5 v1 v2 v3 v4 e1 e2 e3 e4 e5 e6 v5 v6 v1 v2 v3 v4 e1 e2 e3 e4 e5 e6 v6 e6 v1 v2 v3 e1 e2 e3 e4 e5