763
个编辑
更改
跳到导航
跳到搜索
第12行：
第12行： − + 第20行：
第20行： − +
→无向图
=== 无向图 ===
=== 无向图 ===
[[File:Undirected.png|缩略图|有三个顶点和三条边的图]]
[[File:Undirected.png|缩略图|有三个顶点和三条边的图]]
'''图 graph'''通常定义为一个'''有序对 ordered pair''' <math>G=(V,E)</math>，<ref>See, for instance, Iyanaga and Kawada, ''69 J'', p. 234 or Biggs, p. 4.</ref>其中
'''图 graph'''通常定义为一个'''有序对 ordered pair''' <math>G=(V,E)</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.148</ref><ref>See, for instance, Iyanaga and Kawada, ''69 J'', p. 234 or Biggs, p. 4.</ref>其中
* <math>V</math> 是'''顶点 vertices/nodes/points'''的集合；
* <math>V</math> 是'''顶点 vertices/nodes/points'''的集合；
* <math>E\subseteq\left\{\left\{x,y\right\}:(x,y)\in V^2,x\neq y\right\}</math> 是'''边 edges/links/lines'''的集合，边由所有顶点的'''无序对 ordered pair'''构成（换句话说，边连接了顶点对）。
* <math>E\subseteq\left\{\left\{x,y\right\}:(x,y)\in V^2,x\neq y\right\}</math> 是'''边 edges/links/lines'''的集合，边由所有顶点的'''无序对 ordered pair'''构成（换句话说，边连接了顶点对）。
在边<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>，其中
允许重边时，上述定义可以推广：'''图'''是'''有序三元组 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> 是边集；