1,526
个编辑
更改
跳到导航
跳到搜索
第96行：
第96行： − + + +
→Bipartite graph model
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.
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.
==Bipartite graph model==
==二部图模型 Bipartite graph model==
A hypergraph ''H'' may be represented by a [[bipartite graph]] ''BG'' as follows: the sets ''X'' and ''E'' are the partitions of ''BG'', and (''x<sub>1</sub>'', ''e<sub>1</sub>'') are connected with an edge if and only if vertex ''x<sub>1</sub>'' is contained in edge ''e<sub>1</sub>'' in ''H''. Conversely, any bipartite graph with fixed parts and no unconnected nodes in the second part represents some hypergraph in the manner described above. This bipartite graph is also called [[incidence graph]].
A hypergraph ''H'' may be represented by a [[bipartite graph]] ''BG'' as follows: the sets ''X'' and ''E'' are the partitions of ''BG'', and (''x<sub>1</sub>'', ''e<sub>1</sub>'') are connected with an edge if and only if vertex ''x<sub>1</sub>'' is contained in edge ''e<sub>1</sub>'' in ''H''. Conversely, any bipartite graph with fixed parts and no unconnected nodes in the second part represents some hypergraph in the manner described above. This bipartite graph is also called [[incidence graph]].
[[File:bipartie graph.jpeg|300px|缩略图|右| 设<math>G=(V,E)</math>是一个无向图，如果顶点V可分割为两个互不相交的子集<math> (group1, group2)</math>，并且图中的每条边<math>（i，j）</math>所关联的两个顶点<math>i</math>和<math>j</math>分别属于这两个不同的部分<math>(i in group1,j in group2)</math>，则称图<math>G</math>为一个二部图。]]
一个'''超图“ <math>H </math>”'''可以用二部图“<math>BG </math>”表示，其构成如下: 集合“X”和“ E”是“BG”的分割，而且 (''x<sub>1</sub>'', ''e<sub>1</sub>'') 与边连通当且仅当顶点''x<sub>1</sub>''包含在“ <math>H </math>”的边“ e<sub>1</sub>”中。 反之，任何具有固定的'''部分 part'''且在第二部分中没有不连通节点的二部图也代表具有上述性质的部分超图。 这个二部图也称为'''关联图'''。
==Acyclicity==
==Acyclicity==