南京大学2019春季学期图论作业

因为实在不知道更新点啥博客,就更新一下图论作业吧。

仅供参考,禁止抄袭

1.4

  • 对于一个顶点的图,我们不予考虑。

  • 考虑$n$个点的简单图($n \geq 2$),显然对于任意一个点$v$,其度数$d$满足$0 \leq d \leq n - 1$。

  • 不妨假设每个点的度数不同,那么显然对于$0, 1, \cdots, n - 1$各有且仅有一个点度数为对应值。

  • 考虑度数为$n-1$的点,由于该图为简单图,意味着该点与其余所有点均相邻,可以推出任意点的度数至少为$1$。

    这与存在一个点度数为$0$矛盾。

  • 综上,对于一个简单图,必然存在至少两个顶点拥有相同的度。


1.23

  • 我们不妨假设不存在长度$\geq k$的路,即存在一条最长的路,其长度为$d$,点依次为$v_1, v_2, \cdots, v_d$,同时$d \lt k$。

  • 对于点$v_1$来说,根据条件$\delta(G) \geq k$可知,$\text{degree}(v_1) \geq k$,但路上除$v_1$以外的点数为$d-1 \lt k$。

  • 所以必存在一个点$v$与$v_1$相邻,同时其不在该最长路上。

    换而言之,存在一条更长的路$v, v_1, v_2, \cdots, v_d$,这与最长路长度为$d$矛盾。

  • 综上,对于$\delta(G) \geq k$的简单图$G$,其必存在长度至少为$k$的路。

  • 考虑一条最长路$v_1, v_2, \cdots, v_d$,显然与$v_1$相邻的点均在该最长路上,否则与该路为最长路矛盾。

  • 考虑$\text{degree}(v_1) \geq k$,则必然存在一个点$v_i$与$v_1$相邻,同时满足$i - 1 \geq k$。

    那么$v_1, v_2 \cdots, v_i, v_1$为一个圈,该圈长度为$i \geq k + 1$。


1.31

  • 图$G$不连通,我们不妨假设其具有$n \geq 2$个连通分量$C_1, \cdots, C_n$。
  • 我们考虑$1 \leq i \leq n, v_i \in C_i$, 显然原图中$v_1, \cdots, v_n$互不连通。
  • 在补图中$v_1, \cdots, v_n$构成完全图,显然这$n$个点连通。对于一个其他的点$v$,其必属于原图中的某一个连通分量$C_j$。
  • 考虑连通分量个数$n \geq 2$,必存在$k \neq j$,显然原图中$v \notin C_k$,说明边$(v, v_k)$不存在于原图,其必存在于补图中。
  • 由此我们得出,对于除去$v_1, \cdots, v_n$以外的任意点$v$,其必与$v_1, \cdots, v_n$中至少一点相邻,同时$v_1, \cdots, v_n$两两相邻。
  • 综上,补图为连通图。

1.35

  • 图1和图2同构,图3与图12不同构(图三存在五元环$v_1, v_2, v_3, v_4, v_5, v_1$,但图2显然为二部图,不可能存在奇环)。
  • 图1和图2的点双射关系如下 :
    • a-u, b-y, c-t, d-w, h-v, e-x, f-s, g-z

1.63

  • $\text{diam}G \geq 3$,我们考虑$d(u, v) \geq 3$, 那么对于图中其余任意点$p$,其不与$u, v$同时相邻,否则易知$d(u,v) \leq 2$。

    同时$u,v$不相邻,否则$d(u,v)=1$。

  • 基于以上条件,我们可以推出在补图中有$u,v$相邻,同时对于任意点$p$,其与$u,v$中至少一点相邻。

  • 显然$d(u,v)=1$,对任意点$p$有$d(u, p) \leq 2, d(v, p) \leq 2$。

  • 此外我们考虑两点$x, y$,其必满足以下两种情况之一 :

    • 这两点在原图中与$u, v$中某一点均不相邻,不妨设原图中$u, x$不相邻,$u, y$不相邻。

      那么在补图中$x, u$相邻,$y, u$相邻,易知$d(x,y) \leq 2$。

    • 这两点在原图中分别与$u, v$中某一点不相邻,不妨设原图中$u, x$不相邻,$v, y$不相邻。

      那么在补图中$u, x$相邻,$v, y$相邻,同时$u, v$相邻,故$d(x, y) \leq 3$。

  • 综上,对于补图中任意两点,其距离小于等于3,故$\text{diam}G \geq 3 \Rightarrow \text{diam}\overline{G} \leq 3$。

  • 显然,对于$\text{rad}G \geq 3$的图,相邻的点在补图中的距离不可能为1,下面证明原图中相邻的点补图中距离一定为2。

  • 不妨假设原图中$u, v$相邻,考虑到$\text{rad}G = \min_{x \in V(G)} e(x) \geq 3$,他们的离心率$e(u) \geq 3, e(v) \geq 3$。

  • 下面证明必然存在一点$p$,其在原图中与$u, v$均不相邻。

    假设在原图中对于任意点$p$,其与$u, v$之一相邻,那么显然$e(u) \leq 2, e(v) \leq 2$,与离心率大于等于$3$矛盾。

  • 故存在点$p$,在原图中与$u, v$均不相邻,显然在补图中$u, p$相邻,$v, p$相邻,故$d(u, v) = 2$。

  • 综上,$\text{rad}G \geq 3 \Rightarrow \text{rad}\overline{G} \leq 2$。


2.1

  • 因为$G$不是完全图但连通,所以存在两点$u, w$距离为$2$。
  • 我们考虑$u, w$两点间的最短路$u, v, w$。
  • 显然$d(u, v) = d(v, w) = 1$,即$uv, vw \in E(G)$,同时有$uw \notin E(G)$,证毕。

2.8

  • 反例

    • 考虑两个点的完全图$G$,显然$w(G) = 1$,如果去掉唯一的边,则$w(G) = 2 \gt 1$,故该边为割边。
    • 如果去掉两点之一,不妨假设$V(G) = \lbrace u, v \rbrace$,则有$w(G - u) = w(G - v) = 1$,这两点均不为割点。
  • 补充条件 : 设$e = (u, v)$,若$\nu(u) + \nu(v) \gt 2$,则命题成立。

    • 考虑到$\nu(u) + \nu(v) \gt 2$,必有$\nu(u) \gt 1$和$\nu(v) \gt 1$至少有一个成立。
    • 不失一般性,我们不妨假设$\nu(u) \gt 1$。
    • 下面证明$u$为割点。
    • 我们考虑$G$中包含$e$的连通分量$G_1$,同时令$G_2 = G - G_1$,我们可以得到以下结论 :

      • $w(G_1) = 1$($G_1$为一个连通分量)
      • $w(G) = w(G_1) + w(G_2)$($G_1$和$G_2$不连通)
      • $w(G) = w(G_2) + 1$
    • 由于$\nu(u) \gt 1$,不妨假设存在$w$使得$uw \in E(G)$,那么也有$uw \in E(G_1)$。

    • 已知$e$为$G$的割边,那么$e$为$G_1$的割边,即$w(G_1 - \lbrace e \rbrace) = 2$。
    • 易知$v \in G_1-\lbrace e \rbrace, w \in G_1-\lbrace e \rbrace$,且$G_1-\lbrace e \rbrace$中$v, w$不连通。
    • 那么$G_1 - \lbrace u \rbrace$中$v, w$也不连通,换而言之$w(G_1 - \lbrace u \rbrace) \geq 2$。
    • $w(G - \lbrace u \rbrace) = w(G_2) + w(G_1 - \lbrace u \rbrace) \geq w(G_2) + 2 \gt w(G_2) + 1 = w(G)$,由定义$u$为割点。

2.22

  • 不失一般性,我们只考虑$G$为连通图的情况。
  • 由定理2.2.1知,$\kappa(G) \leq \kappa’(G)$。
  • 下面只需要证明,$\Delta(G) \leq 3$时,有$\kappa(G) \geq \kappa’(G)$。
  • 假设我们对于图G找到了一个最小点割集$S$,满足$|S| = \kappa(G)$。
  • 显然$G - S$被分成了两个连通分量$C_1, C_2$,且对于$\forall x \in S$,$x$至少各有一条边分别连向$C_1, C_2$。
  • 考虑到$\Delta(G) \leq 3$,我们考虑$x$可能存在的第三条边。
  • 我们根据以下策略构建一个边集$T$ :
    • 对于$x \in S$,若$\nu(x) = 2$,将其连向$C_1$的边纳入$T_1$,$x$纳入$S_1$。
    • 若$x$只有一条边连向$C_1$,将这条边纳入$T_1$,$x$纳入$S_1$。
    • 若$x$有两条边连向$C_1$,将其连向$C_2$的边纳入$T_2$,$x$纳入$S_2$。
    • $T = T_1 \cup T_2$。
  • 显然有$|T| \leq |S|$,下面我们证明$T$为图$G$的边割集,等价于$C_1 \cup S_2$和$C_2 \cup S_1$在$G - T$中不连通。
  • 假设连通,由于$C_1$与$C_2$无边直接相连,那么可能有以下三种情况 :
    • $C_1$与$S_1$相连,显然不可能,因为$\forall x \in S_1$,其只有一条边与$C_1$相连,该条边必在$T_1$中。
    • $C_2$与$S_2$相连,显然不可能,因为$\forall x \in S_2$,其只有一条边与$C_2$相连,该条边必在$T_2$中。
    • $S_1$与$S_2$相连,显然不可能,因为$\forall x_1, x_2 \in S$,若$(x_1, x_2) \in E(G)$,必有$x_1, x_2 \in S_1$。
  • 综上所述,$T$为$G$的边割集。故有$\Delta(G) \leq 3$时,$\kappa’(G) \leq |T| \leq |S| = \kappa(G)$。
  • 又因为对于任意连通图$G$,有$\kappa(G) \leq \kappa’(G)$。
  • 最终,我们得到,$\Delta(G) \leq 3$时,$\kappa(G) = \kappa’(G)$。

2.2

  • 对于$|V(G)| \geq 3$的连通图$G$,我们需要证明$v$是割点$\Leftrightarrow$$v$至少属于两个不同的块。

  • 不妨假设$v \in H_1, v \in H_2$。

  • $v$是割点$\Rightarrow$$v$至少属于两个不同的块

    • 显然,一个点不属于任何一个块当且仅当其度为0。
      • 一个度大于0的点$u$必有一个邻居$v$,考虑子图$V(G’) = {u, v}, E(G’) = (u, v)$。
      • 显然$G’$是$2$-连通的,如果不存在更大的块包含$u$,那么$G’$就是一个块,否则$u$属于某个更大块。
    • 已知$v$属于至少一个块,假如$v$仅属于一个块,由块的定义,$v$不可能是割点。
    • 所以显然,$v$至少属于两个不同的块。
  • $v$至少属于两个不同的块$\Rightarrow$$v$是割点

    • 假设$x \in H_1, y \in H_2, x, y \neq v$,那么在$G$中,$x, v$连通, $y, v$连通,故$x, y$连通。

    • 假设去掉$v$以后,$x, y$仍连通,那么显然$H_1 - \lbrace v \rbrace$同样与$H_2 - \lbrace v \rbrace$连通。

    • 那么$H_1 \cup H_2 \cup \lbrace v \rbrace = H$不是一个块当且仅当存在一个点$u$,其为$H$的割点。

    • 由于$u \neq v$,所以不失一般性地假设$u \in H_1$。

    • 已知$H_1$为块,$H_1 - \lbrace u \rbrace$依然连通

      那么$H_1 - \lbrace u \rbrace$中的任意一点$p$与$v$连通,$v$与$H_2 - \lbrace v \rbrace $中任意点$q$连通

    • 即$H - \lbrace u \rbrace$依然连通,与$u$为$H$的割点矛盾。

    • 即去掉$v$以后,$x, y$不连通,由割点定义知,$v$为$G$的割点。


2.43

  • 我们考虑不相邻的两个点$x, y \in G_m$。

  • $x, y \in G$,已知$G$为$k$-连通,故$x, y$被至少$k$条两两内部无公共顶点的路相连。

  • $x, y \in H = \lbrace w_1, \cdots, w_m \rbrace$,考虑到$|N_G(v)| \geq k$,

    显然存在$k$条两两内部无公共顶点的路$1 \leq i \leq k, u_i \in N_G(v), (x, u_i, y)$

  • 不失一般性,假设$x \in H, y \in G$ :

    • 若$y = v$, 显然存在$k$条两两内部无公共顶点的路$1 \leq i \leq k, u_i \in N_G(v), (x, u_i, v)$
    • 若$y \neq v$,由于$x, y$不相邻,所以$y \not\in N_G(v)$。
    • 已知$G$是$k$-连通的,所以$y, v$存在$k$条两两内部无公共顶点的路$p_1, \cdots, p_k$。
    • 不妨假设$1 \leq i \leq k, p_i = (v, u_i, t_i, y)$,其中$t_i$表示$p_i$除去$v, u_i, y$三个点后的路(可以为空)。
    • 显然,$\lbrace t_i \mid 1 \leq i \leq k \rbrace$之间两两内部无公共顶点。
    • 我们构造$k$条路$1 \leq i \leq k, s_i = (x, u_i, t_i, y)$,显然这$k$条路两两内部无公共顶点。
  • 综上,对于任意两不相邻的点$x, y \in G_m$,它们之间存在$k$条两两内部无公共顶点的路。

  • 由$\text{Menger}$定理的推论,$G_m$是$k$-连通的。


3.5

  • 由策梅洛定理,该游戏必存在必胜策略。
  • 第一选点人有必胜策略$\Rightarrow$图$G$没有完美匹配
    • 假设图$G$存在完美匹配。
    • 对于第一选点人选择的任何一个点,第二选点人可以选择其在完美匹配中对应的点。
    • 第二选点人必胜,与第一选点人有必胜策略矛盾。
  • 图$G$没有完美匹配$\Rightarrow$第一选点人有必胜策略

    • 图$G$没有完美匹配,说明存在一个最大匹配$M$,同时也存在一个不被最大匹配$M$饱和的点$u$。

      否则$M$即为完美匹配,与假设矛盾了。

    • 对于$\forall u$不被$M$饱和,$u$的邻居显然都被$M$饱和,否则存在一个更大的匹配。

    • 第一选点人选点$u$,之后对于第二选点人的每个点,第一选点人均选取其在最大匹配中对应的点。

    • 下面我们证明,第二选点人选取的每个点必被$M$饱和。

      • 假设存在路$u, p_1, q_1, \cdots, p_k, q_k, v$,其中$1 \leq i \leq k, (p_i, q_i)$均是$M$中的边。
      • $u, v$均不被$M$饱和,那么显然这样的路是一条增广路,与$M$是最大匹配矛盾。
    • 考虑第二选点人选取的每个点必被$M$饱和
      同时第一选点人除开始点之外选取的点均是第二选点人选取点在$M$中对应的点,
      显然第一选点人必胜。


3.10

  • 题目等价于证明右图不存在完美匹配。
  • 取$S = \lbrace 2, 7, 5, 10, 8, 13 \rbrace$,那么$o(G - S) = 8 \gt 6 = |S|$,故$G$不存在完美匹配。

3.12

  • 因为原图$G$是3-正则的,所以若其存在完美匹配$M$(1-正则),则$G - M$是2-正则的。
  • 无割边的3-正则图$G$存在完美匹配(推论3.2.2),证毕。

OJ作业

Problem 1

参考Problem 2的代码,去掉权值读入和solve2函数即可

Problem2

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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
/*****************************************
Author: lizi
Email: zyli@smail.nju.edu.cn
*****************************************/

#pragma GCC optimize("O2")

#include<bits/stdc++.h>

using namespace std;

const double eps=1e-10;
const double pi=3.1415926535897932384626433832795;
const double eln=2.718281828459045235360287471352;

#define LL long long
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define sqr(x) (x) * (x)
#define pr(x) printf("Case %d: ",x)
#define prn(x) printf("Case %d:\n",x)
#define prr(x) printf("Case #%d: ",x)
#define prrn(x) printf("Case #%d:\n",x)
#define lowbit(x) (x&(-x))
#define fi first
#define se second
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;

const int maxn = 400005;
const int maxm = 2000005;

vi g[maxn];
int nx, ny, m, dis[maxn], maxdis, match[maxn], tmp[maxn], tmpcnt, q[maxn], ql, qr, val[maxn], xulie[maxn];
bool vis[maxn];

bool DFS1(int p)
{
for(vector<int>::iterator it = g[p].begin(); it != g[p].end(); ++ it)
{
int v = *it;
if(!vis[v] && dis[v] > 0 && dis[v] == dis[p] - 1)
{
vis[v] = true;
if(match[v] == 0 || DFS1(match[v]))
{
match[p] = v; match[v] = p;
return true;
}
}
}
return false;
}

bool BFS1()
{
maxdis = 1e9 + 7;
ql = 0; qr = 0;
for(int i = 1; i <= nx; ++ i) if(match[ i ] == 0) {q[qr ++] = i; dis[ i ] = 1;}
while(ql < qr)
{
int p = q[ql ++];
if(dis[p] >= maxdis) break;
for(vector<int>::iterator it = g[p].begin(); it != g[p].end(); ++ it)
{
int v = *it;
if(dis[v] > 0) continue;
dis[v] = dis[p] + 1;
if(match[v] == 0) { maxdis = dis[v]; tmp[++ tmpcnt] = v; break;}
else
{
int u = match[v];
dis[u] = dis[v] + 1;
q[qr ++] = u;
}
}
}
return tmpcnt > 0;
}

void solve1()
{
while(true)
{
for(int i = 1; i <= nx + ny; ++ i) dis[i] = 0, vis[i] = false;
tmpcnt = 0; if(!BFS1()) break;
for(int i = 1; i <= tmpcnt; ++ i) if(match[tmp[i]] == 0) DFS1(tmp[i]);
}
}

bool cmp(int x, int y) {return val[x] > val[y];}

bool BFS2()
{
for(int i = 1; i <= nx; ++ i)
{
int bg = xulie[i];
if(match[bg] > 0) continue;
ql = qr = 0;
q[qr ++] = bg; dis[bg] = 0;
while(ql < qr)
{
int p = q[ql ++];
for(vector<int>::iterator it = g[p].begin(); it != g[p].end(); ++ it)
{
int v = *it;
if(dis[v] > 0) continue;
dis[v] = p; dis[match[v]] = v;
assert(match[v] > 0);
if(val[match[v]] < val[bg])
{
int nd = match[v], cnt = 0;
match[nd] = 0;
while(nd != bg)
{
int tmp = dis[nd];
cnt ++;
if(cnt & 1) match[tmp] = dis[tmp]; else match[tmp] = nd;
nd = tmp;
}
return true;
}
q[qr ++] = match[v];
}
}
}
return false;
}

void solve2()
{
while(true)
{
// printf("%d\n", maxdis);
for(int i = 1; i <= nx + ny; ++ i) dis[i] = 0;
if(!BFS2()) break;
}
}

int main()
{
scanf("%d%d", &nx, &ny);
for(int i = 1; i <= nx + ny; ++ i)
{
g[i].clear();
match[i] = 0;
}
for(int i = 1; i <= nx; ++ i)
{
scanf("%d", &val[i]);
int t, k; scanf("%d", &k);
while(k --)
{
scanf("%d", &t);
g[i].pb(nx + t); g[nx + t].pb(i);
}
}
for(int i = 1; i <= nx; ++ i) xulie[i] = i;
sort(xulie + 1, xulie + nx + 1, cmp);
for(int i = 1; i <= ny; ++ i) sort(g[nx + i].begin(), g[nx + i].end(), cmp);
solve1(); solve2();
LL ans = 0; for(int i = 1; i <= nx; ++ i) if(match[i] > 0) ans += val[i];
printf("%lld\n", ans);
return 0;
}

4.12

  • 需要求出图2的最优邮路
  • 先求出任意两奇度点间最短路
    $d(B, C) = 7, d(B, D) = 7, d(B, E) = 13, d(C, D) = 14, d(C, E) = 9, d(D, E) = 6$
  • 我们根据任意两奇度点间最短路构造完全图$K_4$(图略)
  • 利用Edmonds算法求出最小权完美匹配$(B, C), (D, E)$
  • 我们添加三条重边$(A, B), (B, C), (D, E)$,此时所有点的度数均为偶数,图存在Euler笔迹
  • 图2的最优邮路总长为64
  • 顺便吐槽一下这图竟然不满足三角形不等式。。。

5.6

  • 为简化说明,我们记$d = \text{diam}G$。
  • 我们考虑图$G$的直径这条路径$D = \lbrace v_1, \cdots, v_{d + 1} \rbrace$
  • 我们构造集合$S_1 = (V - D) \cup \lbrace v_i \mid i = 2k, 1 \leq i \leq d + 1, k \in N_+ \rbrace$
    显然$S_1$是一个支配集,因此$\gamma(G) \leq |S_1| = \nu - \lceil \frac{d}{2} \rceil$。
  • $\forall p \in D$,显然$p$最多有$2$个邻居在$D$内;$\forall q \notin D$,显然$q$最多有$3$个邻居在$D$内,否则与$D$为直径矛盾。
  • 对于$\forall u \in G$,其最多支配$D$中的$3$个点,因此$3\gamma(G) \geq |D|$。
  • 综上,有$\frac{1 + \text{diam}G}{3} \leq \gamma(G) \leq \nu - \lceil \frac{\text{diam}G}{2} \rceil$

5.11

  • $G$是恰含一个圈的非二部图,说明此圈是奇圈,不妨假设该奇圈大小为$k$,$k$为奇数。
  • 我们选择奇圈上的一个点$u$,考虑剩下的点$v$到$u$的距离$d(u, v)$。
  • 显然对于$S_l = \lbrace x \mid d(x, u) = l \rbrace$,$S_l$集合中的点两两不相邻
    除了一种情况,即$\exist p, q \in S_{\frac{k - 1}{2}}$,$p, q, u$均在奇圈上,$(p, q) \in E(G)$。
  • 不失一般性,我们强制将$p$排除出$S_{\frac{k - 1}{2}}$,此时对于$\forall x, y \in S_i, 0 \leq i \leq e(u)$,$x, y$不相邻。
  • 我们考虑$A_0 = \cup_{0 \leq i \leq e(u) \ i \equiv 0 \mod 2} S_i$,$A_1 = \cup_{0 \leq i \leq e(u) \ i \equiv 1 \mod 2} S_i$。
  • 显然$A_0$和$A_1$均满足集合中的点两两不相邻,同时有$|A_0 \cup A_1| = \nu - 1, |A_0 \cap A_1| = 0$。
  • 因此两个集合中必有至少一个,集合的势不小于$\lfloor \frac{\nu - 1}{2} \rfloor$,不失一般性,我们记其为$A$。
  • 因此有$\alpha(G) \geq |A| \geq \lfloor \frac{\nu - 1}{2} \rfloor$,证毕。

5.15

  • 由定理5.1.13,对于任意点覆盖集$B$,$V - B$是点独立集;对于任意点独立集$A$,$V - A$是点覆盖集。
  • 我们取任一最大点独立集$I$满足$|I| = \alpha(G)$,其补集$V - I$是点覆盖集,同时$|V - I| = \nu - \alpha(G)$。
  • 假设存在一个点覆盖集$S$满足$|S| < \nu - \alpha(G)$,其补集$V - S$是点独立集,$|V - S| = \nu - |S| > \alpha(G)$。
  • 这与$I$是最大点独立集矛盾!
  • 综上,$V - I$是最小点覆盖集,$\beta(G) = \nu - \alpha(G) \Leftrightarrow \alpha(G) + \beta(G) = \nu$。

5.16

  • 任意一个二部图有一个至少含$\frac{\epsilon(G)}{\Delta(G)}$条边的匹配
    • 由Konig定理,二部图最小点覆盖数等于最大匹配数
    • 一个点最多覆盖$\Delta(G)$条边,故最小点覆盖$\alpha(G) \geq \frac{\epsilon(G)}{\Delta(G)}$
    • 最大匹配数等于最小点覆盖数,故最大匹配最少含有$\frac{\epsilon(G)}{\Delta(G)}$条边
  • 上一条结论中,我们可以认为至少含$\lceil \frac{\epsilon(G)}{\Delta(G)} \rceil$条边
  • 因此,$\Delta(G) \leq n$,$\epsilon(H) \gt (k-1)n \Rightarrow \epsilon(H) \geq (k-1)n + 1$
  • $H$有一个至少含$\lceil \frac{\epsilon(H)}{\Delta(H)} \rceil \geq k$条边的匹配

5.18

$G$无孤立点,说明$\delta(G) > 0$

(1) 证明 : $M$是最大匹配当且仅当$M$含于某个最小边覆盖中

  • $M$是最大匹配$\Rightarrow$$M$含于某个最小边覆盖中

    • $M$是最大匹配等价于$M$是最大边独立集
    • $\beta’(G) = \nu(G) - \alpha’(G) =\alpha’(G) + (\nu(G) - 2\alpha’(G))$
    • 因此我们可以每个未被最大匹配覆盖的点添加一条覆盖它的边,构造出最小边覆盖
    • $M$含于某个最小边覆盖中
  • $M$含于某个最小边覆盖中$\Rightarrow$$M$是最大匹配

    • 已知$M$是极大匹配,不妨假设$|M| = m$
    • $M$含于某个最小边覆盖中,即未被$M$覆盖的点,每个点均需要一条边来覆盖
    • 由此我们可以得出$m + (\nu(G) - 2m) = \beta’(G) \Leftrightarrow m = \alpha’(G)$
    • 那么显然$M$是最大匹配

(2) 证明 : $L$是最小边覆盖当且仅当$L$包含一个最大匹配

  • $L$是最小边覆盖$\Rightarrow$$L$包含一个最大匹配
    • 我们在$L$的边中取尽可能多的覆盖无重复的两个点的边,不妨设该边集为$S$,$|S| = s$
    • 显然$S$是一个匹配,下面我们证明$S$是最大匹配
    • 已知$L$是最小边覆盖,故有$|L| = \beta’(G)$
    • $\nu(G) = 2s + |L| - s = |L| + s = \beta’(G) + s \Leftrightarrow s = \alpha’(G)$
    • 显然$S$是最大匹配
  • $L$包含一个最大匹配$\Rightarrow$$L$是最小边覆盖
    • 已知$L$是极小边覆盖,因此除去最大匹配覆盖的点之外每个点需要且仅需要一条边覆盖
    • $|L| = \alpha’(G) + (\nu(G) - 2\alpha’(G)) \Leftrightarrow |L| = \beta’(G)$
    • 显然$L$是最小边覆盖

5.20

  • 图$G$是二部图$\Rightarrow$对$G$的每个适合$\delta(H) > 0$的子图$H$均有$\alpha(H) = \beta’(H)$

    • 图$G$是二部图$\Rightarrow$其每个$\delta(H) > 0$的子图$H$也是二部图
    • 显然二部图满足$\alpha(H) = \beta’(H)$
  • 对$G$的每个适合$\delta(H) > 0$的子图$H$均有$\alpha(H) = \beta’(H)$$\Rightarrow$图$G$是二部图

    • 假设$G$不是二部图$\Leftrightarrow$$G$存在奇圈,我们取该圈作为子图
      $V(H) = \lbrace v_0, v_2, \cdots, v_{2k} \rbrace$

      $E(H) = \lbrace (v_i, v_{(i+1)\mod 2k}) \mid 0 \leq i \leq 2k \rbrace$

    • 显然有$\alpha(H) = k$,$\beta’(H) = k + 1$,与$\alpha(H) = \beta’(H)$矛盾

    • 综上,图$G$是二部图


7.4


7.15

(1)

  • 假设存在点$u$满足$d(u) \leq 2$
    • $d(u) = 0$和$d(u) = 1$时,该图显然不是极大可平面图
    • $d(u) = 2$时,假设$(u, x), (u, y) \in E(G)$
    • 我们定义$V(G’) = V(G) - \lbrace u \rbrace,E(G’) = E(G) - \lbrace (u, x), (u, y) \rbrace$
      显然$G’$是简单可平面图
    • 原图是极大可平面图,有$\epsilon(G) = 3\nu(G) - 6$
    • 那么$\epsilon(G’) = \epsilon(G) - 2, \nu(G’) = \nu(G) - 1 \Rightarrow \epsilon(G’) = 3\nu(G’) - 5$
    • 已知$\nu(G) \geq 4 \Rightarrow \nu(G’) \geq 3$
    • 由定理7.2.5,对于$\nu(G’) \geq 3$简单可平面图$G’$有$\epsilon(G’) \leq 3\nu(G’) - 6$,与$\epsilon(G’) = 3\nu(G’) - 5$矛盾
  • 综上,不存在点$u$满足$d(u) \leq 2$,即$\delta(G) \geq 3$

(2)

  • $\nu(G) = 3$时,其实不存在这样的$4$个顶点,我们当作特例即可。
  • 下面证明$\nu(G) \geq 4$时,极大可平面图$G$有至少$4$个顶点度数不超过$5$
  • 假设$G$有$k$个点的度数不超过$5$,那么有$\nu(G) - k$个点的度数不小于$6$
    同时由(1),$\delta(G) \geq 3$
  • 对于极大可平面图,有$6\nu(G) - 12 = 2\epsilon(G) = \sum_{u \in V(G)} d(u) \geq 6(\nu(G) - k) + 3k$
  • 上式可以推出$6\nu(G) - 12 \geq 6\nu(G) - 3k \Leftrightarrow k \geq 4$
  • 即至少有$4$个点的度数不超过$5$

7.23

  • 假设$G$的每个面度数均超过5,即大于等于$6$
  • $2\epsilon(G) = \sum d(F) \geq 6\varphi = 6(\epsilon(G) - \nu(G) + 2) \Leftrightarrow 6\nu(G) - 12 \geq 4\epsilon(G)$
  • $6\nu(G) - 12 \geq 4\epsilon(G) = 2 \sum_{u \in V(G)} d(u) \geq 2 \times 3\nu(G) = 6\nu(G)$
    (因为$\delta(G) \geq 3$)
  • 这显然矛盾
  • 综上,$G$至少有一个面度数不超过$5$

7.26

设$G^*$是具有$w$个连通分支的平面图$G$的对偶图

(1) $\nu^* = \varphi$

  • 因为对偶图的构造就是原图的每个面作为对偶图的一个点,所以显然

(2) $\epsilon^* = \epsilon$

  • 因为对偶图的每条边和原图的每条边一一对应,所以显然

(3) $\varphi^* = \nu - w + 1$

  • 对于$G$,有$\nu - \epsilon + \varphi = w + 1$
  • 对于$G^$,有$\nu^ - \epsilon^ + \varphi^ = 1$ ($G^*$连通)
  • 由$\nu^ = \varphi, \epsilon^ = \epsilon$,得证

(4) 设$G^$的顶点$v_i^$位于$G$的面$F_i$中,则$d_{G^}(v_i^) = d(F_i)$

  • 对于$F_i$边界上的边,非割边对等式两侧各贡献$1$,割边对等式两侧各贡献$2$,故成立

7.29

(1)

  • 因为平面图的对偶图连通,因此自对偶图必然是连通图

  • 对于自对偶图,有$\nu = \nu^, \epsilon = \epsilon^$

  • 由Euler公式,$\nu - \epsilon + \varphi = 2, \nu = \nu^* = \varphi, \Rightarrow \epsilon = 2\nu - 2$

(2)

  • 对于$n = \nu(G) \geq 4$的图$G$,令$E(G) = \lbrace (1, i) \mid 2 \leq i \leq n \rbrace \cup \lbrace (i, i + 1) \mid 2 \leq i \leq n - 1 \rbrace \cup \lbrace (2, n) \rbrace$
  • 那么$G$是自对偶图,既然不要证明,那我就不证明了,反正挺显然的(o゚v゚)ノ