重图

在数学中，更具体地为在图论中， 重图，也称多重图（multigraph）或伪图（pseudograph）是一个允许有重边（也称多重边，平行边）的图。^[1]重边即两个顶点之间可能存在多条边。 每一对顶点之间至多有两条重边的图叫2-重图（2-multigraph）。

含有多重边（红色）和自环（蓝色）的多重图。并非所有的多重图都允许包含自环。

重边有两种不同的类型:

• 边没有身份:边的身份仅由其两端頂點定义。这种情况下，术语“重边”表示同一条边在两个节点间多次出现。
• 边有身份:边与节点一样是基本实体。当多条边连接两个节点时，这些边是不同的边。

重图与超图不同，超图是指一条边可以连接任意数量的节点，而不是两个。

一些学术文章中，伪图和重图是同义词。另一些则认为伪图是允许有自环的重图。

无向重图(没有同一性的边)

重图G是一个有序对G=(V, E)，其中：

• V是一组顶点或节点，
• E是一组无序的顶点对，称为边或线。

无向重图(具有同一性的边)

重图G是一个有序的三元组合G=(V, E, r)，其中

• V是一组顶点或节点，
• E是一组边或线，
• r : E → {{x,y} : x, y ∈ V},为每条边对应的一对无序节点。

一些文章允许重图有自环，即一条只与一个顶点连接的边；而另一些则称有自环的图为伪图，在没有自环的情况下才是多重图。^[2][3]

有向重图(没有同一性的边)

有向重图是允许有向自环存在的有向图，即具有相同源节点和目标节点的有向边。有向重图G是一个有序对G=(V,A)，其中

• V是一组顶点或节点，
• A是一组有序的顶点对，称为有向边。

混合重图G = (V,E,A) 可以用与混合图类似的方法定义。

有向重图(具有同一性的边)

有向重图G是一个有序的四元组合G=(V, A, s, t)，其中：

• V是一组顶点或节点，
• A是一组边或线，
• ${\displaystyle s:A\rightarrow V}$ 为每条边对应的源节点，
• ${\displaystyle t:A\rightarrow V}$ 为每条边对应的目标节点。

这个概念可以用来为航空公司建立潜在航线建立模型。在这种情况下，重图将是一个有向图，每一对有向平行的代表航线的边与代表城市的节点连接，以表明有可能多次飞离或飞到某地点。

在范畴论中，一个小的范畴可以被定义为一个有向重图(边具有同一性)，它具有结合律，在每个顶点上都有一个结合律和一个可区分的自环作为组合的左右标识。因此，在范畴理论中，“图”一词通常被理解为“有向重图”，该范畴的潜在有向重图被称为潜在有向图。

标签

重图和有向重图也以类似的方式支持图标记的概念。然而，在这种情况下没有统一的术语。

带标记的重图和带标记的有向重图的定义是相似的，在此我们只对后者作定义。

定义1:带标记的有向重图是标记有向边的标记图。

正式定义：带标记的有向重图G是将顶点和有向边进行标记的重图。 其严格定义为八元组合 ${\displaystyle G=(\Sigma _{V},\Sigma _{A},V,A,s,t,\ell _{V},\ell _{A})}$ ，其中

• V是一组顶点，A是一组有向边。
• ${\displaystyle \Sigma _{V}}$  和 ${\displaystyle \Sigma _{A}}$  是给定字母中可用于作顶点和有向边标签的部分。
• ${\displaystyle s\colon A\rightarrow \ V}$  和 ${\displaystyle t\colon A\rightarrow \ V}$ 是两个表示有向边源节点和目标节点的集合。
• ${\displaystyle \ell _{V}\colon V\rightarrow \Sigma _{V}}$  和 ${\displaystyle \ell _{A}\colon A\rightarrow \Sigma _{A}}$  两个描述有向边源节点和目标节点的集合。

定义2:带标记的有向重图是标记有向重边的标记图，这种边即为标记了相同顶点和相同方向的边(注意，标记图的概念与图标记中给出的概念不同)。

参见

• 多维网络
• 图论术语表
• 图论

注释

1. For example, see Balakrishnan 1997, p. 1 or Chartrand and Zhang 2012, p. 26.
2. For example, see Bollobás 2002, p. 7 or Diestel 2010, p. 28.
3. For example, see Wilson 2002, p. 6 or Chartrand and Zhang 2012, pp. 26-27.

参考文献

• Balakrishnan, V. K. Graph Theory. McGraw-Hill. 1997. ISBN 0-07-005489-4. 
• Bollobás, Béla. Modern Graph Theory. Graduate Texts in Mathematics 184. Springer. 2002. ISBN 0-387-98488-7. 
• Chartrand, Gary; Zhang, Ping. A First Course in Graph Theory. Dover. 2012. ISBN 978-0-486-48368-9. 
• Diestel, Reinhard. Graph Theory. Graduate Texts in Mathematics 173 4th. Springer. 2010. ISBN 978-3-642-14278-9. 
• Gross, Jonathan L.; Yellen, Jay. Graph Theory and Its Applications. CRC Press. 1998. ISBN 0-8493-3982-0. 
• Gross, Jonathan L.; Yellen, Jay (编). Handbook of Graph Theory. CRC. 2003. ISBN 1-58488-090-2. 
• Harary, Frank. Graph Theory. Addison Wesley. 1995. ISBN 0-201-41033-8. 
• Janson, Svante; Knuth, Donald E.; Luczak, Tomasz; Pittel, Boris. The birth of the giant component. Random Structures and Algorithms. 1993, 4 (3): 231–358. ISSN 1042-9832. MR 1220220. doi:10.1002/rsa.3240040303. 
• Wilson, Robert A. Graphs, Colourings and the Four-Colour Theorem. Oxford Science Publ. 2002 [2019-05-22]. ISBN 0-19-851062-4. （原始内容于2019-07-25）. 
• Zwillinger, Daniel. CRC Standard Mathematical Tables and Formulae 31st. Chapman & Hall/CRC. 2002. ISBN 1-58488-291-3. 

外部链接

•   本条目引用的公有领域材料。材料来自NIST的文档：Black, Paul E. Multigraph. 演算法與資料結構辭典（英语：Dictionary of Algorithms and Data Structures）.