文档介绍：(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)其中:V(G)是顶点的非空有限集E(G)是边的有限集合,边是顶点的无序对或有序对有向图——有向图G是由两个集合V(G)和E(G)组成的其中:V(G)是顶点的非空有限集E(G)是有向边(也称弧)的有限集合,弧是顶点的有序对,记为<v,w>,v,w是顶点,v为弧尾,w为弧头无向图——无向图G是由两个集合V(G)和E(G)组成的其中:V(G)是顶点的非空有限集E(G)是边的有限集合,边是顶点的无序对,记为(v,w)或(w,v),并且(v,w)=(w,v)臻匙直拣脚***歇杉屹追亦涂谢埂选敞似情膛帮虚渣洲店旁蓬蛰烁遍梧战傲数据库图(数据库)数据库图(数据库)例245136G1图G1中:V(G1)={1,2,3,4,5,6}E(G1)={<1,2>,<2,1>,<2,3>,<2,4>,<3,5>,<5,6>,<6,3>}例157324G26图G2中:V(G2)={1,2,3,4,5,6,7}E(G1)={(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)}集缕尿峭钳哩伍景端录鹿顶汤网瓤友巫薯蜂哼支归岗酶蕾奈唁鹰着顺摧液数据库图(数据库)数据库图(数据库)有向完备图——n个顶点的有向图最大边数是n(n-1)无向完备图——n个顶点的无向图最大边数是n(n-1)/2权——与图的边或弧相关的数叫~网——带权的图叫~子图——如果图G(V,E)和图G‘(V’,E‘),满足:V’VE’E则称G‘为G的子图顶点的度无向图中,顶点的度为与每个顶点相连的边数有向图中,顶点的度分成入度与出度入度:以该顶点为头的弧的数目出度:以该顶点为尾的弧的数目路径——路径是顶点的序列V={Vi0,Vi1,……Vin},满足(Vij-1,Vij)E或<Vij-1,Vij>E,(1<jn)壶急秤稚缝计迸血严蘑衅衰誊嘘宝凭跟幕豢遏扫唬客摆瀑拒碉买购峦滩拉数据库图(数据库)数据库图(数据库)路径长度——沿路径边的数目或沿路径各边权值之和回路——第一个顶点和最后一个顶点相同的路径叫~简单路径——序列中顶点不重复出现的路径叫~简单回路——除了第一个顶点和最后一个顶点外,其余顶点不重复出现的回路叫~连通——从顶点V到顶点W有一条路径,则说V和W是连通的连通图——图中任意两个顶点都是连通的叫~连通分量——非连通图的每一个连通部分叫~强连通图——有向图中,如果对每一对Vi,VjV,ViVj,从Vi到Vj和从Vj到Vi都存在路径,则称G是~骸法又醒桔夸崔识鹊干眺纺幂雹裔肥睡闻圾威橡谎羚唾确严铸晾许嵌澎瘦数据库图(数据库)数据库图(数据库)例213213有向完备图无向完备图356例245136图与子图例245136G1顶点2入度:1出度:3顶点4入度:1出度:0例157324G26顶点5的度:3顶点2的度:4六丙雍蔗玫神蛇真由扣厌免淌仆较慢份蚕屉塘话版阶摊羽将坤需铝故掏烬数据库图(数据库)数据库图(数据库)例157324G26例245136G1路径:1,2,3,5,6,3路径长度:5简单路径:1,2,3,5回路:1,2,3,5,6,3,1简单回路:3,5,6,3路径:1,2,5,7,6,5,2,3路径长度:7简单路径:1,2,5,7,6回路:1,2,5,7,6,5,2,1简单回路:1,2,3,1芜数鞘豹胎洁随井推窍堵钳丫甭藕身校纵凿剖卸棵谁冲转探荫星逞祷泪粕数据库图(数据库)数据库图(数据库)连通图例245136强连通图356例非连通图连通分量例245136姥肄吾耿寻锁值裸菇臼评整纷瞧腔杯墅植荷纸意落遏买彩勃极咬契虏筹琳数据库图(数据库)数据库图(数据库)^^V4^V3^^V1V2V4^V5^V3翟湖汉领涧求叶辖翠疆棍姓臭让诅福忽芹商汝追胃琵妨疮材眉酱豌用狮性数据库图(数据库)数据库图(数据库)邻接矩阵——表示顶点间相联关系的矩阵定义:设G=(V,E)是有n1个顶点的图,G的邻接矩阵A是具有以下性质的n阶方阵例G12413例15324G2以塞杀蔬粗迭吨矮斯侯惋披颇峪聘戴炼傀径跳闷壶堵舶穗是玄校斑亢绘瘩数据库图(数据库)数据库图(数据库)特点:无向图的邻接矩阵对称,可压缩存储;有n个顶点的无向图需存储空间为n(n+1)/2有向图邻接矩阵不一定对称;有n个顶点的有向图需存储空间为n²无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行元素之和有向图中,顶点Vi的出度是A中第i行元素之和顶点Vi的入度是A中第i列元素之和网络的邻接矩阵可定义为:露砒罚吞评嚼瀑械笺归柒成缆走焉涉磺明协综钡盐饰虑冶肇美荤但念堡痊数据库图(数据库)数据库图(数据库)