首页 理论教育无向图与连通性:B-1、B-3、B-4的定义

无向图与连通性:B-1、B-3、B-4的定义

【摘要】:图的本质内容是二元关系,图又分为无向图和有向图两种。定义B-1(无向图)无向图G定义为一个二元组G=(N,E),其中,N是顶点的非空有限集合,N={ni|i=0,…,k};E是边的有限集合,E={|ni,nj∈N}。定义B-3(连通图)连通图是一个无向图G=(N,E)或有向图D=(N,E),对于N中的任意两个顶点ns和nt,存在一个顶点的序列P,使得ns=ni0,ni1,…,nik=nt均属于N,且ej=(j=0,1,…定义B-4(回路)设P是有向图D的一条路径,P=ni0,ni1,…

图的本质内容是二元关系,图又分为无向图和有向图两种。

定义B-1(无向图)无向图G定义为一个二元组G=(NE),其中,N是顶点的非空有限集合,N={nii=0,…,k};E是边的有限集合,E={(ninj)|ninjN}。

定义B-2(有向图)有向图D定义为一个二元组D=(NE),其中,N是顶点的非空有限集合,N={nii=0,…,k};E是边的有限集合,E={(ninj)|ninjN}且(ninj)≠(njni),(ninj)∈E是顶点ni的出边,顶点nj的入边。

定义B-3(连通图)连通图是一个无向图G=(NE)或有向图D=(NE),对于N中的任意两个顶点nsnt,存在一个顶点的序列P,使得ns=ni0ni1,…,nik=nt均属于N,且ej=(nijnij+1)(j=0,1,…,k-1)均属于EP也被称为图GD的一条路径或通路。

定义B-4(回路)设P是有向图D的一条路径,P=ni0ni1,…,nik,如果ni0=nik,则称PD的一条回路,即开始和终结于同一顶点的通路。如果k=0,则P称为自回路。若P是无向图G的一条路径,P=ni0ni1,…,nikni0=nik,且k﹥0,那么,称PG的一条回路。若图中无任何回路,则称该图为无回路图。