19th Ave New York, NY 95822, USA

# 数学代写|优化理论代写Optimization Theory代考|CSCI8955

my-assignmentexpert™提供最专业的一站式服务：Essay代写，Dissertation代写，Assignment代写，Paper代写，Proposal代写，Proposal代写，Literature Review代写，Online Course，Exam代考等等。my-assignmentexpert™专注为留学生提供Essay代写服务，拥有各个专业的博硕教师团队帮您代写，免费修改及辅导，保证成果完成的效率和质量。同时有多家检测平台帐号，包括Turnitin高级账户，检测论文不会留痕，写好后检测修改，放心可靠，经得起任何考验！

## 数学代写|优化理论代写Optimization Theory代考|The bipartite case

We start with an observation which will be used over and over again in the bipartite as well as in the general case.

Suppose that $M$ is a matching in $G=(V, E), G$ any graph. A path $P=v_0 e_1 v_1 \ldots v_{r-1} e_r v_r$ in $G$ is called alternating (with respect to $M$, or $M-$ alternating) if $M$ contains either all the edges $e_i$ with $i$ even or all the $e_i$ with $i$ odd $(i \leq r) . P$ is called an $M$-augmenting path if both of its endpoints are exposed nodes. In this case, $r$ is odd and $M^{\prime}:=M \backslash\left{e_2, e_4, \ldots, e_{r-1}\right} \cup$ $\left{e_1, e_3, \ldots, e_r\right}$ is a matching with $\left|M^{\prime}\right|=|M|+1$. In 1957, Berge proved the following characterization of maximum matchings in terms of augmenting paths:

Theorem 14.3.1 (Berge) A matching $M$ in a graph $G$ is maximum if and only if there exists no $M$-augmenting path in $G$.

Proof. We did already explain why maximum matchings do not have augmenting paths. Conversely, assume that $M$ and $M^{\prime}$ are matchings with $|M|<\left|M^{\prime}\right|$. Denote by $M \oplus M^{\prime}$ the symmetric difference of $M$ and $M^{\prime}$, i.e. the set of edges which belong either to $M$ or to $M^{\prime}$ but not to both. Since $M$ and $M^{\prime}$ are matchings, the graph with edge set $M \oplus M^{\prime}$ has all degrees at most 2, hence all its components are either cycles of even length or $M_{-}$ and $M^{\prime}$-alternating paths. It is clear that the cycles and the paths of even length all have the same number of $M$ – and $M^{\prime}$-edges. Since $\left|M^{\prime}\right|>|M|$, at least one component must be an alternating path containing more edges from $M^{\prime}$ than from $M$. This path is clearly $M$-augmenting.
By a similar argument we obtain the following result:
Lemma 14.3.2 Suppose $B$ and $B^{\prime}$ are the sets of nodes covered by the maximum matchings $M$ and $M^{\prime}$, respectively. Then for each $x \in B \backslash B^{\prime}$ there exists some $y \in B^{\prime} \backslash B$ such that $(B \backslash{x}) \cup{y}$ is again covered by some maximum matching $M^{\prime \prime}$.

Proof. Consider again the components spanned by $M \oplus M^{\prime}$. Since both matchings are maximum, all paths have even length. The vertex $x \in B \backslash B^{\prime}$ is an endpoint of one of the alternating paths, say of
$$P: x=v_0 e_1 v_1 \ldots v_{2 s-1} e_{2 s} v_{2 s} .$$
Now it clearly suffices to choose
$$y:=v_{2 s} \quad \text { and } \quad M^{\prime \prime}:=\left(M \backslash\left{e_1, e_3, \ldots, e_{2 s-1}\right}\right) \cup\left{e_2, e_4, \ldots, e_{2 s}\right}$$

## 数学代写|优化理论代写Optimization Theory代考|Nonbipartite matching

We now turn our attention to general graphs, starting with the description of the so-called Gallai-Edmonds Structure Theorem.

Theorem 14.4.1 (Gallai-Edmonds Structure Theorem) Let a graph $G=(V, E)$ be given. Denote by $D_G$ the set of all vertices of $G$ which are not covered by all maximum matchings of $G$. Let $A_G:=\Gamma\left(D_G\right) \backslash D_G$ and $C_G:=V \backslash\left(A_G \cup D_G\right)$. Then the following conditions hold:
(i) $D_{G-x}=D_G$ and $C_{G-x}=C_G$ for all $x \in A_G$.
(ii) Each maximum matching of $G$ contains a perfect matching of $G\left[C_G\right]$ and a maximum matching of each component of $G\left[D_G\right]$.
(iii) Each component $H$ of $G\left[D_G\right]$ is factor-critical, which means that $H-x$ has a perfect matching for each vertex $x$ of $H$.
(iv) $\nu(G)=\frac{1}{2}\left(|V|+\left|A_G\right|-c\left(G\left[D_G\right]\right)\right)$, where $c\left(G\left[D_G\right]\right)$ denotes the number of components of $G\left[D_G\right]$.

Example 14.4.2 The graph in Figure 14.12 might clarify the objects used in the Gallai-Edmonds Structure Theorem.

Proof. (i) Suppose $x \in A_G$ is given. Since $x$ is covered by each maximum matching, $\nu(G-x)=\nu(G)-1$. We conclude that for each $y \in D_G$ there exists some maximum matching of $G-x$ missing $y$, hence $D_G \subseteq D_{G-x}$. To prove the reversed inclusion, we assume that a vertex $y \in D_{G-x} \backslash D_G$ exists which is an exposed node of the maximum matching $M^{\prime}$ of $G-x$. We choose some neighbour $z$ of $x$ in $D_G$ and a maximum matching $M$ of $G$ avoiding $z$. Now consider again the graph $\left(V, M \oplus M^{\prime}\right)$. The component of $y$ in this graph is obviously some alternating path $P$ starting with an $M$-edge at its endpoint $y$. If $P$ had even length, the matching
$$M^{\prime \prime}:=(M \backslash E(P)) \cup\left(M^{\prime} \cap E(P)\right)$$
would be a maximum matching of $G$ avoiding $y$ which is impossible in view of $y \notin D_G$. The length of $P$ is thus odd. Since $M^{\prime}$ admits no augmenting path in $G-x$, the other endpoint of $P$ must be $x$. But then
$$M^{\prime \prime \prime}:=(M \backslash E(P)) \cup\left(M^{\prime} \cap E(P)\right) \cup{x z}$$
is again a maximum matching of $G$ avoiding $y$. Contradiction! The equation $C_{G-x}-C_G$ is now easy.
(ii) This follows readily from (i) by applying part (i) successively for all $x \in A_G$. The details are left to the reader.

## Matlab代写

MATLAB 是一种用于技术计算的高性能语言。它将计算、可视化和编程集成在一个易于使用的环境中，其中问题和解决方案以熟悉的数学符号表示。典型用途包括：数学和计算算法开发建模、仿真和原型制作数据分析、探索和可视化科学和工程图形应用程序开发，包括图形用户界面构建MATLAB 是一个交互式系统，其基本数据元素是一个不需要维度的数组。这使您可以解决许多技术计算问题，尤其是那些具有矩阵和向量公式的问题，而只需用 C 或 Fortran 等标量非交互式语言编写程序所需的时间的一小部分。MATLAB 名称代表矩阵实验室。MATLAB 最初的编写目的是提供对由 LINPACK 和 EISPACK 项目开发的矩阵软件的轻松访问，这两个项目共同代表了矩阵计算软件的最新技术。MATLAB 经过多年的发展，得到了许多用户的投入。在大学环境中，它是数学、工程和科学入门和高级课程的标准教学工具。在工业领域，MATLAB 是高效研究、开发和分析的首选工具。MATLAB 具有一系列称为工具箱的特定于应用程序的解决方案。对于大多数 MATLAB 用户来说非常重要，工具箱允许您学习应用专业技术。工具箱是 MATLAB 函数（M 文件）的综合集合，可扩展 MATLAB 环境以解决特定类别的问题。可用工具箱的领域包括信号处理、控制系统、神经网络、模糊逻辑、小波、仿真等。