113 lines
4.2 KiB
TeX
113 lines
4.2 KiB
TeX
\documentclass[11pt]{article}
|
||
|
||
\usepackage{myctex}
|
||
\usepackage{tikz}
|
||
\usepackage{tikz,fullpage}
|
||
\usetikzlibrary{arrows,%
|
||
petri,%
|
||
topaths}%
|
||
\usepackage{tkz-berge}
|
||
\usepackage{tkz-graph}
|
||
\GraphInit[vstyle=Normal]
|
||
\usepackage[position=top]{subfig}
|
||
|
||
|
||
\title{作业 3}
|
||
\author{11 丛宇 202411081537}
|
||
\date{}
|
||
|
||
\begin{document}
|
||
\maketitle
|
||
\section*{第四章}
|
||
|
||
\begin{itemize}
|
||
\item[1.] a 四个奇点 不行; b 可以; c 两个奇点 不行; d 可以
|
||
\item[3.] \begin{minipage}{0.9\textwidth}
|
||
\begin{figure}[H]
|
||
\centering
|
||
\subfloat[]{
|
||
\begin{tikzpicture}
|
||
\grCycle[prefix=v,Math=true,RA=1]{4};
|
||
\end{tikzpicture}
|
||
}
|
||
\subfloat[]{
|
||
|
||
\begin{tikzpicture}
|
||
\SetVertexMath
|
||
\Vertex[x=0,y=0]{v_1}
|
||
\Vertex[x=2,y=0]{v_2}
|
||
\Vertex[x=1,y=1.5]{v_3}
|
||
\Vertex[x=3,y=1.5]{v_4}
|
||
\Vertex[x=1,y=3]{v_5}
|
||
\Edge(v_1)(v_2)
|
||
\Edge(v_1)(v_3)
|
||
\Edge(v_2)(v_3)
|
||
% \Edge(v_2)(v_4)
|
||
\Edge(v_3)(v_4)
|
||
\Edge(v_3)(v_5)
|
||
\Edge(v_4)(v_5)
|
||
\end{tikzpicture}
|
||
}
|
||
\subfloat[]{
|
||
|
||
\begin{tikzpicture}
|
||
\grComplete[RA=1,prefix=v,Math=true]{4}
|
||
\end{tikzpicture}
|
||
}
|
||
\subfloat[]{
|
||
|
||
\begin{tikzpicture}
|
||
\grComplete[RA=1,prefix=v,Math=true]{2}
|
||
\end{tikzpicture}
|
||
}
|
||
\end{figure}
|
||
\end{minipage}
|
||
|
||
\item[4.] 归纳. $n=3$时显然成立. 假设对所有$n\leq k$成立, 现在考虑$n=k+1$. $m=\frac{k(k-1)}{2}+2$. 取 $v$ 为 $\deg(v)$ 最小的点, $G\setminus\set{v}$ 的边数 $m'\geq \frac{k(k-1)}{2}+2-(k-1)\geq \frac{(k-1)(k-2)}{2}+2$. 由归纳假设 $G\setminus\set{v}$ 包含 Hamilton cycle. 由于 $\deg(v)\geq 2$, $G$也包含 Hamilton cycle.
|
||
\item[5.] $S=\set{i,g,k,p,b,d}$, $\omega(G\setminus S)=7>6=|S|$.
|
||
\item[10.]
|
||
\begin{itemize}
|
||
\item $G$ 不是2-connected则存在两点 $u,v$之间只有一条 vertex disjoint path. 假设$G$有 Hamilton cycle, 则$u,v$之间存在两条vertex disjoint path. 矛盾.
|
||
\item 假设二分图$G$ 存在 Hamilton cycle, $(v_1,...,v_n,v_1)$, 则所有奇数编号点属于$X$, 所有偶数编号点属于$Y$且$|X|=|Y|$. 与假设$|X|\neq|Y|$矛盾.
|
||
\end{itemize}
|
||
\item[12.] %假设 $G$ 无hamilton path. 对任意$(u,v)\notin E$, $G+(u,v)$ 不包含Hamilton cycle.
|
||
令 $d'_1\leq \dots\leq d'_n$ 为 $G+(u,v)$ 的度序列, 令$d_1\leq \dots\leq d_n$ 为 $G$ 的度序列. 由于$d'$中只有两个位置与$d$不同且都只$+1$, 不妨假设两个序列对应顶点相同. 因此 $d'_m\leq d_m+1\leq m$ 或 $d'_{n-m}\leq d_{n-m+1}<n-m$ 对 $G+(u,v)$成立. 由定理8, $G+(u,v)$ 一定包含 Hamilton cycle, 因此 $G$ 中一定有Hamilton path.
|
||
\item[13.] 假设$G$不是Hamilton图, 那么存在$m<n/2$, $G$ 度弱于$C_{m,n}$.
|
||
\begin{align*}
|
||
|E(G)| &\leq |E(C_{m,n})|\\
|
||
& \leq \frac{1}{2}[m^2+(n-2m)(n-m-1)+m(n-1)]\\
|
||
& = \binom{n-\delta}{2}+\delta^2-\frac{1}{2}(m-\delta)(2n-3m-3\delta-1)\\
|
||
& \leq \binom{n-\delta}{2}+\delta^2
|
||
\end{align*}
|
||
最后一个不等号是观察到 $m\geq \delta$, $2n-3m-3\delta -1>n/2-3\delta-1\geq -1$. 有$2n-3m-3\delta -1\geq 0$ (是整数).
|
||
|
||
因此与假设矛盾.
|
||
\end{itemize}
|
||
\section*{第五章}
|
||
\begin{itemize}
|
||
\item[2.] 考虑$T$中任何$\deg(v)=1$的点, 如果存在完美匹配, 与叶子相连的边都在匹配中. 可以确定性的知道$T$中所有边是否在匹配中. 因此完美匹配唯一(如果存在).
|
||
\item[5.] 3, 5
|
||
\item[7.] \begin{minipage}{0.4\textwidth}
|
||
\begin{tikzpicture}
|
||
\grComplete[RA=3,prefix=,Math=true]{9}
|
||
\end{tikzpicture}
|
||
\end{minipage}
|
||
cycles: $\begin{aligned}
|
||
&\set{1, 2, 8, 3, 7, 4, 6, 5, 9},\\
|
||
&\set{2, 3, 1, 4, 8, 5, 7, 6, 9},\\
|
||
&\set{3, 4, 2, 5, 1, 6, 8, 7, 9},\\
|
||
&\set{4, 5, 3, 6, 2, 7, 1, 8, 9}\\
|
||
\end{aligned}$
|
||
\item[13.] 找$K_{5,5}$的最小权重完美匹配. 30
|
||
\item[14.] SDR等价于bipartite matching 等价于 Hall's Theorem, 略
|
||
\item[18.] 等价于证明Tutte–Berge formula.
|
||
\begin{proof}
|
||
令$d=\frac{1}{2}\min_{S\subset V} |V|-o(G-S)+|S|$, $\nu(G)$是$G$的最大匹配的大小.
|
||
考虑任意点集$U\subset V$, 有$\nu(G)\leq |U|+\nu(G-U)\leq |U|+1/2(|V\setminus U|-o(G-U))$ 因为$G-U$的每个odd component都至少有一个点不能被匹配到. 因此 $\nu(G)\leq d$. 下面证明$d\leq \nu(G)$.
|
||
|
||
需要证明$\exists S\subset V$ 使 $|V|+|S|+o(G-S)=\nu(G)$. 满足条件的$S$是 Edmonds-Gallai decomposition. 所以$d\leq \nu(G)$.
|
||
|
||
|
||
\end{proof}
|
||
\end{itemize}
|
||
\end{document} |