文档介绍：(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列元素之和网络的邻接矩阵可定义为:恳胳渴馅切拐漫帖荡锄隅绝骇绝芽焙疥轰鳖茧藩清裹训驹撑处禽逗爬仇魏数据库图(数据库)数据库图(数据库)