763
个编辑
更改
跳到导航
跳到搜索
第84行：
第84行： − −
→二分图模型
===二分图模型===
===二分图模型===
[[File:bipartie graph.jpeg|200px|缩略图|右| 设<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>为一个二分图。]]
[[File:bipartie graph.jpeg|200px|缩略图|右| 设<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>表示，其构成如下: 集合<math>X</math>和<math> E </math>是<math>BG</math>的分割，而且 ("x<sub>1</sub>", "e<sub>1</sub>") 与边连通当且仅当顶点"x<sub>1</sub>"包含在<math>H </math>的边" e<sub>1</sub>"中。 反之，任何具有固定的'''部分 part'''且在第二部分中没有不连通节点的二分图也代表具有上述性质的部分超图。 这个二分图也称为'''关联图'''。
一个'''超图 <math>{H} </math>'''可以用二分图<math>{BG} </math>表示，其构成如下: 集合<math>X</math>和<math> E </math>是<math>BG</math>的分割，而且 ("x<sub>1</sub>", "e<sub>1</sub>") 与边连通当且仅当顶点"x<sub>1</sub>"包含在<math>H </math>的边" e<sub>1</sub>"中。 反之，任何具有固定的'''部分 part'''且在第二部分中没有不连通节点的二分图也代表具有上述性质的部分超图。 这个二分图也称为'''关联图'''。