邊 (圖論)

一個有七條邊的圖結構

在圖論中，邊（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.