边 (图论)

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

一个有七条边的图结构

分类

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

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

简单边

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

超边

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

在不同领域中，超边有许多不同的名称，例如，在计算几何学中，超边又可以被称为范围（ranges）^[4]、在合作博弈论中，超边又可称为简单博弈（simple games）^[5]。

自环

拥有自环的图。

主条目：自环

在图论中，自环（Loop）是一条顶点与自身连接的边^{[6][7][8][9][10][11]}。而花束图（英语：Bouquet_graph）中所有的边皆为自环。^[12]

无向边

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

有向边

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

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

与几何学的关联

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

参见

• 边 (几何)

参考文献

1. Bender, Edward A.; Williamson, S. Gill. Lists, Decisions and Graphs. With an Introduction to Probability. 2010 [2019-09-14]. （原始内容存档于2020-10-19）.
2. See, for instance, Iyanaga and Kawada, 69 J, p. 234 or Biggs, p. 4.
3. Judea Pearl, in HEURISTICS Intelligent Search Strategies for Computer Problem Solving, Addison Wesley (1984), p. 25
4. Haussler, David; Welzl, Emo, ε-nets and simplex range queries, Discrete and Computational Geometry, 1987, 2 (2): 127–151, MR 0884223, doi:10.1007/BF02187876
5. Peleg, B. Chapter 8 Game-theoretic analysis of voting in committees. Handbook of Social Choice and Welfare Volume 1. Handbook of Social Choice and Welfare 1. 2002: 195–201. ISBN 9780444829146. doi:10.1016/S1574-0110(02)80012-1.
6. Balakrishnan, V. K.; Graph Theory, McGraw-Hill; 1 edition (February 1, 1997). ISBN 0-07-005489-4
7. Bollobás, Béla; Modern Graph Theory, Springer; 1st edition (August 12, 2002). ISBN 0-387-98488-7
8. Diestel, Reinhard; Graph Theory, Springer; 2nd edition (February 18, 2000). ISBN 0-387-98976-5
9. Gross, Jonathon L, and Yellen, Jay; Graph Theory and Its Applications, CRC Press (December 30, 1998). ISBN 0-8493-3982-0
10. Gross, Jonathon L, and Yellen, Jay; (eds); Handbook of Graph Theory. CRC (December 29, 2003). ISBN 1-58488-090-2
11. Zwillinger, Daniel; CRC Standard Mathematical Tables and Formulae, Chapman & Hall/CRC; 31st edition (November 27, 2002). ISBN 1-58488-291-3
12. Beineke, Lowell W.; Wilson, Robin J., Topics in topological graph theory, Encyclopedia of Mathematics and its Applications 128, Cambridge University Press, Cambridge: 5, 2009, ISBN 978-0-521-80230-7, MR 2581536, doi:10.1017/CBO9781139087223
13. G. Gallo, G. Longo, S. Nguyen, S. Pallottino, Directed hypergraphs and applications, DOI link, Citeseer link.
14. Senechal, Marjorie, Shaping Space: Exploring Polyhedra in Nature, Art, and the Geometrical Imagination, Springer: 81, 2013 [2019-09-14], ISBN 9780387927145, （原始内容存档于2014-01-07）.

外部链接

• 埃里克·韦斯坦因. 邊. MathWorld.