\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}