搜索
第六章图与网络分析第一节图与子图第二节图的连通性第三节树与支撑树第四节最小树问题第五节最短有向路问题第六节最大流问题第七节最小费用流问题第八节最大对集问题第一节图与子图图与网络无向图的基本概念有向图和网络关联矩阵和邻接矩阵关联矩阵邻接矩阵主要结论子图无向图的基本概念无向图G：一个有序二元组(N,E)，记为G=(N,E)G的点集合：N={n1,n2,…,nn}G的边集合：E={eij}，且eij是一个无序二元组{ni,nj}，记为eij={ni,nj}eij的端点：若eij={ni,nj}，则称eij连接ni和nj，点ni和nj称为eij的端点环：两个端点重合为一点的边孤立点：不与任何边关联的点例如右图G=(N,E)，其中N={n1,n2,n3,n4,n5}E={e11,e12,e14,e23,e24,e34,e34}e11为环e34为重边n5为孤立点n1n2n4n3n5e11e12e14e21e23e34e341.图与网络无向图的基本概念续一关联：一条边的端点称为与这条边关联邻接：与同一条边关联的端点称为是邻接的。如果两条边有一个公共端点，则称这两条边是邻接的。有限图：图G=(N,E)为有限图，若N和E都是有限集合。空图：没有任何边的图。平凡图：只有一个点的图。简单图：既没有环，也没有重边。例如(a)是简单图，但(b)就不是简单图。无向图的基本概念续二完全图：每一对点之间均有一条边相连的图（如图一）二分图G=(S,T,E)：存在一个二分划(S,T)，使得G的每一条边有一个端点在S中，另一个端点在T中。完全二分图：S中的每一个点和T中的每一个点都相连的简单二分图（如图二）简单图G的补图:与G有相同顶点集合的简单图，且补图中的两个点相邻当且仅当它们在G中不相邻（如图三）图二图一图三有向图有向图G：一个有序二元组(N,A)，记为G=(N,A)G的点集合：N={n1,n2,…,nn}G的弧集合：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)。无向完全图：在无向图中，任意两个顶点之间存在边。有向完全图：在有向图中，任意两顶点之间都有存在方向互为相反的两条弧。含有n个顶点的无向完全图有多少条边？含有n个顶点的有向完全图有多少条弧？n(n-1)/2n(n-1)关联矩阵简单图G=(N,E)的关联矩阵：一个|N|×|E|阶的矩阵B=(bik)，其中简单有向图G=(N,A)的关联矩阵：一个|N|×|A|阶的矩阵B=(bik)，其中2.关联矩阵和邻接矩阵1,当点i与边k关联0,否则bik=1,当aik弧以点i为尾-1,当aik弧以点i为尾0,否则bik=关联矩阵续右图的关联矩阵是0000000000000000001213142325343545eeeeeeee111100000211103111141115111邻接矩阵简单图G=(N,E)的邻接矩阵：一个|N|×|E|阶的矩阵A=(aij)，其中简单有向图G=(N,A)的邻接矩阵：一个|N|×|A|阶的矩阵A=(aik)，其中1,当点i与边j邻接0,否则aij=1,当有弧从点i连向j0,否则aij=邻接矩阵续右图的邻接矩阵是123410110210113010040010几个基本结论定理6.1.1G是二分图当且仅当G的邻接矩阵可以表示成如下形式一个简单有向图G=(N,A)的点i的入次是指G中以点i为头的弧数，记为di-；点i的出次是指G中以点i为尾的弧数，记为di+T0AAA0定理6.1.2∑di=2|E|,其中di表示图中点i的次i定理6.1.3∑di-=|A|=∑di+,其中|A|表示弧的数目ii3.子图图G=(N,E)的子图G'=(N',E')：N'N和E'E，对E'中的任意一条eij={ni,nj}，都有inN'和jnN'图G的支撑子图G'：G'是G的子图，且N'=N.点导出子图G[N']：以N的一个非空子集N'作为点集,以两端点均在N'中的所有边为边集的子图边导出子图G[E']：以E的一个非空子集E'作为边集，以E'中边的所有端点作为点集的子图子图续图G的不相交子图G1和G2:G1和G2没有公共点.图G的边不重子图G1和G2:G1和G2没有公共边子图G1和G2的并G1∪G2:以G1和G2的点集的并为点集,以G1和G2的边集的并为边集的子图子图G1和G2的交G1∩G2：以G1和G2的点集的交为点集，以G1和G2的边集的交为边集的子图