一个有七条边的图结构。

在图论中,edges)是图的基本单元之一,其与点共同组成了图。一般的情况下,边通常是连接两个点的图论元素,而在部分的情况下会只连接1个点(如非简单图)或连接3个或更多个点(如超图),因此边通常可以被定义为将点相连的元素,而被边连接的点称为端点。

分类

边依照连接的点数量可以分为三类,其中一种称为简单边,即这些边连接2个相异的点。简单图的每一个边皆为简单边。另一种为超边(hyperedges),即这些边连接3个或更多个点,通常出现于超图中,其也可以依照其连接的边数称为多元边,例如连接三个点的边可称为三元边。另一类为只连接1个点的边,或连接的两点是相同点的边,这种边通常称为自环

而根据图的有向性,边又可以分成两种,有向边和无向边。

简单边

在图论中,简单边是指连接2个相异点的边。简单图的每一个边皆为简单边。更正式地,简单边可以定义为,有一个图 G {\displaystyle G} 是一个二元组 G = ( V , E ) {\displaystyle G=(V,E)} ,其中 V {\displaystyle V} 是点集、 E {\displaystyle E} 是边集,并且满足 E { { x , y } : ( x , y ) V 2 , x y } {\displaystyle E\subseteq \left\{\left\{x,y\right\}:(x,y)\in V^{2},x\neq y\right\}} ,由所有无序点对构成(换句话说,边连接了两相异点),而这个连接了此两个相异点的边则称为简单边。[1]

超边

在图论中,超边又称超链接(hyperlinks)、接口连接(connectors)是指连接任意数量点的边,其连接的点数量不一定为2个,可能是3个或更多。更正式地,超边可以定义为,有一个超图 H {\displaystyle H} 是一个二元组 H = ( X , E ) {\displaystyle H=(X,E)} where X {\displaystyle X} ,其中 X {\displaystyle X} 是点集、 E {\displaystyle E} 是边集,且边集是 P ( X ) { } {\displaystyle {\mathcal {P}}(X)\setminus \{\emptyset \}} 的子集、 P ( X ) {\displaystyle {\mathcal {P}}(X)} X {\displaystyle X} 的幂集,而 P ( X ) { } {\displaystyle {\mathcal {P}}(X)\setminus \{\emptyset \}} 中的边称为超边。

在不同领域中,超边有许多不同的名称,例如,在计算几何学中,超边又可以被称为范围(ranges)、在合作博弈论中,超边又可称为简单博弈(simple games)。

自环

拥有自环的图。主条目:自环

在图论中,自环Loop)是一条顶点与自身连接的边。而花束图英语Bouquet_graph中所有的边皆为自环。

无向边

若一个边不具有方向性,则称该边为无向边,其可以视为2个点的集合,或只有2个点的超边。无向边也可以在有向图中存在,即双向连结都存在的边,例如有两点A和B,若同时存在A到B的边和B到A的边,则这条边在这个有向图中可以称为一个无向边。

有向边

在图论中,有向边又称弧或箭。若一个边具有方向性,则称该边为有向边。有向边通常会包含一个起点与终点。

有向边也可以推广到超图中,其中一种对于有向超边的定义为,有向超边可以被定义为一个有序对(T,H),其中T代表终点集、H代表起点集,H与T是两不相交的集合。

与几何学的关联

在图论中的边与几何学的边不同,图论中的边是指连接点的抽象物件,不同于多边形、多面体等几何图形的边,几何图形的边通常具有具体的线段或曲线,而图论中的边仅表达了哪些顶点要相连,哪些不用。

www.zuoweixin.com
问题反馈联系QQ:暂无联系方式,也可发qq邮箱。