763
个编辑
更改
→无向图
为避免歧义，上面定义的对象可被更精准地称作无向简单图 undirected simple graph。
在边<math>{ x,y }</math>中，顶点<math>x</math>和<math>y</math>称为边的端点 endpoints，边称为连接 join/incident on<math> x </math>和<math> y </math>。图中的某顶点可能不属于任意一条边。'''重边 Multiple edges'''/'''平行边 parallel edges'''是连接同一对顶点的两条或多条边。
在边<math>{ x,y }</math>中，顶点<math>x</math>和<math>y</math>称为边的端点 endpoints，边称为连接 join/incident on<math> x </math>和<math> y </math>。图中的某顶点可能不属于任意一条边。重边 Multiple edges/平行边 parallel edges是连接同一对顶点的两条或多条边。
允许重边时，上述定义可以推广：图是有序三元组 ordered triple <math>G=(V,E,\phi)</math>，<ref> {{cite book |last1=Bender |first1=Edward A. |last2=Williamson |first2=S. Gill |date=2010 |title=Lists, Decisions and Graphs. With an Introduction to Probability |url=https://books.google.fr/books?id=vaXv_yhefG8C |location= |page= |isbn= |author-link= }}p.149</ref><ref>See, for instance, Graham et al., p. 5.</ref> 其中
* <math>V</math> 是点集；
* <math>V</math> 是点集；
* <math>E</math> 是边集；
* <math>E</math> 是边集；
* <math>\phi:E\to\left\{\left\{x,y\right\}:(x,y)\in V^2,x\neq y\right\}</math> 是一个将每条边映射到一个无序顶点对的'''关联函数 incidence function'''（于是边连接了顶点对）。
* <math>\phi:E\to\left\{\left\{x,y\right\}:(x,y)\in V^2,x\neq y\right\}</math> 是一个将每条边映射到一个无序顶点对的关联函数 incidence function（于是边连接了顶点对）。
'''自环 loop'''是连接顶点与自身的边，上述两个定义中的图不能有自环。为了允许自环，需要扩展定义。对于无向简单图，<math>E\subseteq\left\{\left\{x,y\right\}:(x,y)\in V^2,x\neq y\right\}</math>应为<math>E\subseteq\left\{\left\{x,y\right\}:(x,y)\in V^2 \right\}</math>。对于无向多重图，<math>E\to\left\{\left\{x,y\right\}:(x,y)\in V^2,x\neq y\right\}</math>应为<math>E\to\left\{\left\{x,y\right\}:(x,y)\in V^2\right\}</math>。为避免歧义，这些类型的对象可以分别称为带自环的无向简单图 undirected simple graph permitting loops和带自环的无向多重图 undirected multigraph permitting loops。
'''自环 loop'''是连接顶点与自身的边，上述两个定义中的图不能有自环。为了允许自环，需要扩展定义。对于无向简单图，<math>E\subseteq\left\{\left\{x,y\right\}:(x,y)\in V^2,x\neq y\right\}</math>应为<math>E\subseteq\left\{\left\{x,y\right\}:(x,y)\in V^2 \right\}</math>。对于无向多重图，<math>E\to\left\{\left\{x,y\right\}:(x,y)\in V^2,x\neq y\right\}</math>应为<math>E\to\left\{\left\{x,y\right\}:(x,y)\in V^2\right\}</math>。为避免歧义，这些类型的对象可以分别称为带自环的无向简单图 undirected simple graph permitting loops和带自环的无向多重图 undirected multigraph permitting loops。
（编者注：一种更常见的定义认为简单图是不含重边或自环的图，而多重图是允许重边的图；另外，伪图 pseudograph一说同多重图 multigraph，一说是允许含自环的多重图。）
<math>V,E</math> 的元素个数通常被认为是有限的；在'''无限图 infinite graphs'''中许多著名的性质都会改变或不成立。此外，<math>V</math> 通常被假定为非空集，而 <math>E</math> 允许为空集。以下再给出一些图论中的定义：图的'''阶 order'''是其顶点个数 <math>|V|</math>，图的尺寸 size为其边数 <math>|E|</math>，顶点的'''度 degree/ valency'''是关联于该顶点的边的数目（自环会被算两次）。
<math>V,E</math> 的元素个数通常被认为是有限的；在无限图 infinite graphs中许多著名的性质都会改变或不成立。此外，<math>V</math> 通常被假定为非空集，而 <math>E</math> 允许为空集。以下再给出一些图论中的定义：图的'''阶 order'''是其顶点个数 <math>|V|</math>，图的尺寸 size为其边数 <math>|E|</math>，顶点的'''度 degree/ valency'''是关联于该顶点的边的数目（自环会被算两次）。
带自环无向简单图<math>G</math>在其顶点上诱导出一个对称齐次关系 homogeneous relation，称为<math>G</math>的'''邻接关系 adjacency relation'''。具体来说，对每条边<math>\{ x,y \}</math>，端点<math>x</math>和<math>y</math>称为彼此'''邻接 adjacent''' ，表示为<math>x\sim y</math>。
带自环无向简单图<math>G</math>在其顶点上诱导出一个对称齐次关系 homogeneous relation，称为<math>G</math>的'''邻接关系 adjacency relation'''。具体来说，对每条边<math>\{ x,y \}</math>，端点<math>x</math>和<math>y</math>称为彼此邻接 adjacent，表示为<math>x\sim y</math>。
=== [[有向图]] ===
=== [[有向图]] ===