查看“︁重图”︁的源代码

[[File:Multi-pseudograph.svg|右|缩略图|含有多重边（红色）和自环（蓝色）的多重图。并非所有的多重图都允许包含自环。]]
在[[数学]]中，更具体地为在[[图论]]中， '''重图'''，也称'''多重图'''（multigraph）或'''伪图（pseudograph）'''是一个允许有[[重边]]（也称多重边，平行边）的[[图 (数学)|图]]。<ref>For example, see Balakrishnan 1997, p. 1 or Chartrand and Zhang 2012, p. 26.</ref>重边即两个[[顶点 (图论)|顶点]]之间可能存在多条[[邊 (圖論)|边]]。 每一对顶点之间至多有两条[[重边]]的图叫'''2-重图'''（2-multigraph）。

重边有两种不同的类型:

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

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

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

== 无向重图(没有同一性的边) ==
重图G是一个[[有序对]]''G''=(''V'', ''E'')，其中：

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

== 无向重图(具有同一性的边) ==
重图G是一个有序的[[多元组|三元组合]]''G''=(''V'', ''E'', ''r'')，其中

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

一些文章允许重图有[[自环]]，即一条只与一个顶点连接的边；而另一些则称有自环的图为'''伪图'''，在没有自环的情况下才是多重图。<ref>For example, see Bollobás 2002, p. 7 or Diestel 2010, p. 28.</ref><ref>For example, see Wilson 2002, p. 6 or Chartrand and Zhang 2012, pp. 26-27.</ref>

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

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

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

== 有向重图(具有同一性的边) ==
有向重图G是一个有序的[[多元组|四元组合]]''G''=(''V'', ''A'', ''s'', ''t'')，其中：

* ''V''是一组顶点或节点，
* ''A''是一组边或线，
* <math>s : A \rightarrow V </math>为每条边对应的源节点，
* <math>t : A \rightarrow V </math>为每条边对应的目标节点。

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

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

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

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

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

正式定义：带标记的有向重图G是将顶点和[[有向边]]进行标记的重图。 其严格定义为八元组合 <math>G=(\Sigma_V, \Sigma_A, V, A, s, t, \ell_V, \ell_A)</math>，其中

* V是一组顶点，A是一组[[有向边]]。
* <math>\Sigma_V</math> 和 <math>\Sigma_A</math> 是给定字母中可用于作顶点和有向边标签的部分。
* <math>s\colon A\rightarrow\ V</math> 和 <math>t\colon A\rightarrow\ V</math>是两个表示有向边源节点和目标节点的集合。
* <math>\ell_V\colon V\rightarrow\Sigma_V</math> 和 <math>\ell_A\colon A\rightarrow\Sigma_A</math> 两个描述有向边源节点和目标节点的集合。

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

== 参见 ==

* [[Multidimensional network|多维网络]]
* [[图论术语|图论术语表]]
* [[图论]]

== 注释 ==
{{Reflist}}

== 参考文献 ==

* {{Cite book|first=V. K.|last=Balakrishnan|title=Graph Theory|url=https://archive.org/details/schaumsoutlineof0000bala|publisher=McGraw-Hill|year=1997|isbn=0-07-005489-4}}
* {{Cite book|first=Béla|last=Bollobás|authorlink=Béla Bollobás|title=Modern Graph Theory|series=[[Graduate Texts in Mathematics]]|volume=184|publisher=Springer|year=2002|isbn=0-387-98488-7}}
* {{Cite book|first=Gary|last=Chartrand|authorlink=Gary Chartrand|first2=Ping|last2=Zhang|authorlink2=Ping Zhang (graph theorist)|title=A First Course in Graph Theory|url=https://archive.org/details/firstcourseingra0000char|publisher=Dover|year=2012|isbn=978-0-486-48368-9}}
* {{Cite book|first=Reinhard|last=Diestel|title=Graph Theory|series=Graduate Texts in Mathematics|volume=173|publisher=Springer|edition=4th|year=2010|isbn=978-3-642-14278-9}}
* {{Cite book|first=Jonathan L.|last=Gross|first2=Jay|last2=Yellen|title=Graph Theory and Its Applications|publisher=CRC Press|year=1998|isbn=0-8493-3982-0}}
* {{Cite book|editor-first=Jonathan L.|editor-last=Gross|editor2-first=Jay|editor2-last=Yellen|title=Handbook of Graph Theory|publisher=CRC|year=2003|isbn=1-58488-090-2}}
* {{Cite book|first=Frank|last=Harary|authorlink=Frank Harary|title=Graph Theory|publisher=Addison Wesley|year=1995|isbn=0-201-41033-8}}
* {{Cite journal|title=The birth of the giant component|last=Janson|first=Svante|last2=Knuth|first2=Donald E.|authorlink2=Donald Knuth|journal=Random Structures and Algorithms|issue=3|doi=10.1002/rsa.3240040303|year=1993|volume=4|pages=231–358|issn=1042-9832|mr=1220220|last3=Luczak|first3=Tomasz|last4=Pittel|first4=Boris}}
* {{Cite book|first=Robert A.|last=Wilson|title=Graphs, Colourings and the Four-Colour Theorem|publisher=Oxford Science Publ.|year=2002|isbn=0-19-851062-4|url=https://books.google.com/books?id=iq0sSnIxJioC&pg=PA6&dq=pseudograph&lr=&ei=R-jrSKWoCJGgswOv0eiXBw&sig=ACfU3U20xuoH7jZDq-XGqSnfsmC0oE8KjQ|access-date=2019-05-22|archive-date=2019-07-25|archive-url=https://web.archive.org/web/20190725184050/https://books.google.com/books?id=iq0sSnIxJioC&pg=PA6&dq=pseudograph&lr=&ei=R-jrSKWoCJGgswOv0eiXBw&sig=ACfU3U20xuoH7jZDq-XGqSnfsmC0oE8KjQ|dead-url=no}}
* {{Cite book|first=Daniel|last=Zwillinger|title=CRC Standard Mathematical Tables and Formulae|publisher=Chapman & Hall/CRC|edition=31st|year=2002|isbn=1-58488-291-3}}

==外部链接==
* {{DADS|Multigraph|multigraph}}

{{图论|state= autocollapse}} 
[[Category:数学术语]]