第一节 图与子图 .ppt

1、 第一节 图与子图图与网络无向图的基本概念有向图和网络关联矩阵和邻接矩阵关联矩阵邻接矩阵主要结论子图 无向图的基本概念无向图G：一个有序二元组(N,E)，记为G=(N,E)G的点集合：N=n1,n2, ,nnG的边集合：E=eij，且eij是一个无序二元组ni,nj，记为eij= ni,njeij的端点：若eij= ni,nj，则称eij连接ni和nj ，点ni和nj称为eij的端点环：两个端点重合为一点的边孤立点：不与任何边关联的点例无向图的基本概念关联：一条边的端点称为与这条边关联邻接：与同一条边关联的端点称为是邻接的，同时如果有两条边有一个公共端点，则称这两条边是邻接的有限图：任何图G=

2、(N,E)若N和E都是有限集合,则称G为有限图空图：没有任何边的图平凡图：只有一个点的图简单图：一个图，即没有环，也没有重边。例如(a)是简单图，但(b)就不是简单图。续一无向图的基本概念完全图：每一对点之间均有一条边相连的图（如图一）二分图G=(S,T,E) ：存在一个二分划(S,T)，使得G的每一条边有一个端点在S中，另一个端点在T中完全二分图：S中的每一个点和T中的每一个点都相连的简单二分图（如图二）简单图G的补图 :与G有相同顶点集合的简单图，且补图中的两个点邻接当且仅当它们在G中不邻接（如图三）续二图二图一 图三有向图有向图G：一个有序二元组(N,A)，记为G=(N,A)G的点集合：

3、 N=n1,n2, ,nnG的弧集合：A=aij且aij是一个有序二元组(ni,nj)记为aij= (ni,nj)下图就是个有向图若aij= (ni,nj)，则称aij从ni连向nj，ni称为aij的尾，nj称为aij的头。ni称为nj的前继，称nj为ni的后继基本图：去掉有向图的每条弧上的方向所得到的无向图。网络设G是一个图（有向图），若对G的每条边（弧）都赋予一个实数，并称为这条边（弧）的权，则G连同它边（弧）上的权称为一个（有向）网络或赋权（有向）图，记为G=(N,E,W)。无向完全图：在无向图中，如果任 两个顶点之间存在边。有向完全图：在有向图中，如果任 两顶点之间都有存在方向 为相

4、的两条弧。有n个顶点的无向完全图有 条边有n个顶点的有向完全图有 条弧？n(n-1)/2n(n-1)关联矩阵简单图G=(N,E)的关联矩阵：一个|N|E| 的矩阵B=(bik)， 中, , =当点与边关联则ik1 i kb0简单有向图G=(N,A)的关联矩阵：一个|N|A| 的矩阵B=(bik)， 中, , =当弧 点为尾，当弧 点为头则ikik ik1 a ib -1 a i0关联矩阵图的关联矩阵是续0 0 0 00 0 0 00 0 0 0 00 0 0 0 0骣琪琪琪琪琪琪桫12 13 14 23 25 34 35 45 e e e e e e e e1 1 1 1 0 0 0 0 02 1 1 1 03 1 1 1 14 1 1 15 1 1 1邻接矩阵简单图G=(N,E)的邻接矩阵：一个|N|E| 的矩阵A=(aij)， 中, , =当点与点邻接则ij1 i ja0简单有向图G=(N,A)的邻接矩阵：一个|N|A| 的矩阵A=(aik)， 中, , =当有弧从连向则ij1 i ja0