更改

超图 Hypergraph (查看源代码)

2020年4月23日 (四) 09:29的版本

删除2,889字节、 2020年4月23日 (四) 09:29

→‎术语

第50行：第50行：

* 无环超图 Acyclic hypergraph：不包含任何环的超图。

−

~~Because hypergraph links can have any cardinality, there are several notions of the concept of a subgraph, called ''subhypergraphs'', ''partial hypergraphs'' and ''section hypergraphs''.~~

因为超图中的连接可以有任意基数，所以有好几种关于子图的概念，分别是'''子超图 subhypergraphs'''、'''部分超图 partial hypergraphs'''和'''分段超图 section hypergraphs'''。

−

~~Let <math>H=(X,E)</math> be the hypergraph consisting of vertices~~

−

~~:<math>X = \lbrace x_i | i \in I_v \rbrace,</math>~~

−

~~and having ''edge set''~~

−

~~:<math>E = \lbrace e_i | i\in I_e \land e_i \subseteq X \land e_i \neq \emptyset \rbrace,</math>~~

−

~~where <math>I_v</math> and <math>I_e</math> are the [[index set]]s of the vertices and edges respectively.~~

第73行：第60行：

和 “边集”：

−

~~<math>E = \lbrace e_i | i\in I_e \land e_i \subseteq X \land e_i \neq \emptyset \rbrace,</math>~~

其中 <math>I_v</math> 和 <math>I_e</math> 分别是顶点和边集的索引集 index set

−

~~A ''subhypergraph'' is a hypergraph with some vertices removed. Formally, the subhypergraph <math>H_A</math> induced by <math>A \subseteq X </math> is defined as~~

−

~~:<math>H_A=\left(A, \lbrace e \cap A | e \in E \land~~

−

~~e \cap A \neq \emptyset \rbrace \right).</math>~~

*'''子超图 subhypergraph''' 是去掉某些顶点的超图。在形式上，若 <math>A \subseteq X </math> 是顶点子集，则子超图 <math>H_A</math> 被定义为：

第87行：第69行：

e \cap A \neq \emptyset \rbrace \right).</math>

−

~~An ''extension'' of a ''subhypergraph'' is a hypergraph where each~~

−

~~hyperedge of <math>H</math> which is partially contained in the subhypergraph <math>H_A</math> and is fully contained in the extension <math>Ex(H_A)</math>.~~

−

~~Formally~~

:: 一个'''子超图'''的'''扩展 extension'''是一个超图，其中每个属于 <math>H</math> 的超边都部分包含在子超图的 <math>H_A</math>中，并且完全包含在扩展的 <math>Ex(H_A)</math> 中。即在形式上：

:<math>Ex(H_A) = (A \cup A', E' )</math>和 <math>A' = \bigcup_{e \in E} e \setminus A</math> 和<math>E' = \lbrace e \in E | e \subseteq (A \cup A') \rbrace</math>。

−

The ''partial hypergraph'' is a hypergraph with some edges removed. Given a subset <math>J \subset I_e</math> of the edge index set, the partial hypergraph generated by <math>J</math> is the hypergraph

*'''部分超图 partial hypergraph'''是去掉一些边的超图。给定一个边索引集的子集 <math>J \subset I_e</math> ，由 <math>J</math> 生成的部分超图就是

第101行：第78行：

<math>\left(X, \lbrace e_i | i\in J \rbrace \right).</math>

−

~~Given a subset <math>A\subseteq X</math>, the ''section hypergraph'' is the partial hypergraph~~

*而给定一个子集 <math>A\subseteq X</math>，则''section hypergraph''是部分超图:

第108行：第83行：

<math>H \times A = \left(A, \lbrace e_i |

i\in I_e \land e_i \subseteq A \rbrace \right).</math>

−

The '''dual''' <math>H^*</math> of <math>H</math> is a hypergraph whose vertices and edges are interchanged, so that the vertices are given by <math>\lbrace e_i \rbrace</math> and whose edges are given by <math>\lbrace X_m \rbrace</math> where

第116行：第89行：

<math>X_m = \lbrace e_i | x_m \in e_i \rbrace. </math>

−

~~When a notion of equality is properly defined, as done below, the operation of taking the dual of a hypergraph is an [[involution (mathematics)|involution]], i.e.,~~

当等式的记号被合理定义时，如下所示，对一个超图采取两次乘方 involution运算是就可得到<math>H</math> 的对偶：

<math>\left(H^*\right)^* = H.</math>

−

A [[connected graph]] ''G'' with the same vertex set as a connected hypergraph ''H'' is a '''host graph''' for ''H'' if every hyperedge of ''H'' [[induced subgraph|induces]] a connected subgraph in ''G''. For a disconnected hypergraph ''H'', ''G'' is a host graph if there is a bijection between the [[connected component (graph theory)|connected components]] of ''G'' and of ''H'', such that each connected component ''G<nowiki>'</nowiki>'' of ''G'' is a host of the corresponding ''H<nowiki>'</nowiki>''.

对于连通的超图'' G'' 和具有相同顶点连通的超图 ''H''，如果 ''H'' 的每个超边都由 ''G'' 中一个子图导出 induce，则 ''G'' 是一个主图 host graph；

对于不连通的超图 H，如果 ''G'' 和 ''H'' 的连通部分之间存在一个双射，使得 G 的每个连通部分 ''G'' 都是对应的 ''H'' 的主图，则 ''G'' 是一个主图。

−

A hypergraph is ''bipartite'' if and only if its vertices can be partitioned into two classes ''U'' and ''V'' in such a way that each hyperedge with cardinality at least 2 contains at least one vertex from both classes. Alternatively, such a hypergraph is said to have [[Property B]].

一个超图是二分（bipartite）的，当且仅当它的顶点能被分成两类''U'' 和 ''V'' ：每个基数至少为 2 超边包含两类中的至少一个顶点。换而言之，超图则被称为具有 B 属性 Property B。

−

The '''2-section''' (or '''clique graph''', '''representing graph''', '''primal graph''', '''Gaifman graph''') of a hypergraph is the graph with the same vertices of the hypergraph, and edges between all pairs of vertices contained in the same hyperedge.

2-段 2-section 超图（或团图 clique graph，表示图 representing graph，原始图 primal graph、盖夫曼图 Gaifman graph）是具有相同顶点的图，并且所有顶点对之间的边包含在相同的超边中。

乐多多

763

个编辑