-
Notifications
You must be signed in to change notification settings - Fork 43
/
12Bipartitenetworksandtrees.Rmd
127 lines (82 loc) · 4.68 KB
/
12Bipartitenetworksandtrees.Rmd
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
---
title: "Bipartitenetworkan'd'trees"
author: "韩健"
date: "2021/10/28"
output: word_document
---
```{r setup, include=FALSE}
knitr::opts_chunk$set(echo = TRUE)
```
# 二分图和树
本文将对二分图和树的定义和其重要性质做基本介绍。
# 一、二分图
## （1）定义
二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边(i，j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。
## （2）二分图的匹配问题
图的匹配M是由一些边组成的集合，其中的任何两个边都不关联
完全匹配：设X，Y是图G的两个部分，若X中的每个结点都关联于匹配M中的一条边，称M为从X到ý的一个完全匹配（这时M未必是Y到X的完全匹配）
完美匹配：若M是从X到Y，也是从Y到X的完全匹配，则M为完美匹配，这要求| X | = | Y |，即图G是平衡的
最大匹配：匹配M在所有匹配中基数最大（最大就业率问题）
极大匹配：不存在更大的匹配M‘包含M。极大匹配是指不能通过增加边来扩大匹配
图G的M-交错路：是由在M中的边和不在M中的边交替出现构成的
M-匹配：若结点v与M中的某条边相关联，称v是M-匹配的，否则称为M-不匹配
## （3）判断图X是否是二分图的步骤
判断图x是否是二分图（A，B分别表示相反的符号）
取任一结点，标记为一个
所有与一个邻接的结点标记为b
对任意已标记结点V，将v所有邻接且未标记的结点标记为与v相反的符号
重复步骤3，知道不存在与已标记结点向邻接的未标记结点
如果图中还有未标记结点，那么，这些结点一定是在一个新的连通分量中，再选择其中一个结点标记为一个，转到步骤3
如果得到的图中，所有邻接的结点都标记为不同的标号，那么图x就是二分图，否则x不是二分图
## (4)举例说明
在图论中，一个「匹配」（matching）是一个边的集合，其中任意两条边都没有公共顶点。我们定义匹配点、匹配边、未匹配点、非匹配边，它们的含义非常显然。
# 二、树
## （1）定义
连通的无圈图称为树(tree)
## （2）树的重要性质和基本概念
树删除的任意一条边都会变成非连通图产品
对树中给定的两个结点的x，y，树中存在唯一一条XY路，因此此路为测地线
若树有Ñ个结点，对条边，则P = N-1，因此，树是最小连通的（满足该关系的不一定是树，树一定满足该关系）
设S为n个正整数组成的序列d1，d2，d3 ... dn，其中，d1 d2 d3 ... dn，并且d1 + d2 + d3 + ... + dn = 2（n-1），则存在一个树，度序列为小号
判断非同构树：度序列，最长路的长度，对给定的唯一度数相对应结点间的最短路的长度
## （3）最小生成树以及两种算法
最小生成树：代价最小的生成树
贪心算法：
算法每一步要求选出可以获得的最好的（权重最小的）边，并且要保证加入此边后不会形成圈
采用Kruskal算法：
算法该使用了一种边导出子图产品。的特殊类型子图设集合阿为图ģ的边集的子集，称图ħ为集合甲的边导出子图，当图ħ满足：电子（H）= A并且V（H）= {v：v与集合A内的边相关联}，记作<A>
S =
在已排好序的表L中的下一条边e，若e S且导出子图<S {e}>是无圈图，则令S = S {e}（按照边权重大小加入顺序）
若| S | = n-1，算法停止，输出集合S.否则，转第二步，继续遍历表L.
Prim算法（广度优先搜索）：
选出结点v，令V（T）= {v}，E（T）=
在所有u V(T)的结点中，若连接结点u和w的边e = uw是最小权重边，其中w V(T)则令V(T）= V(T) {u}， E(T)= E(T) {uw}（算法每一步得到的都是树）
若| E（T）| = n-1，算法终止，输出E（T）。否则，转步骤2，向树种增加新的结点
##（4）举例说明
遍历树的代码实现：
```{Rcpp}
#include <iostream>
using namespace std;
const int MAXN = 1000;
namespace tree {
int next[MAXN<<1], to[MAXN<<1], head[MAXN<<1], ce;
void add(int x, int y) {
to[++ce] = y; next[ce] = head[x]; head[x] = ce;
to[++ce] = x; next[ce] = head[y]; head[y] = ce;
}
void dfs(int x, int pre) {
for(int i=head[x]; i; i=next[i])
if(to[i]!=pre) dfs(to[i], x);
}
}
int main() {
int n, m;
cin >> n >> m;
for(int i=1; i<=m; i++) {
int u, v; cin >> u >> v;
tree::add(u, v);
}
tree::dfs(1, 0);
return 0;
}
```