Graph theory，图论不仅在理论数学中是重要的研究对象，在cs和应用数学中也因为自然出现而备受关注。在理论数学中图论有很多分支，比如极值图论的目标是确定一些图论中出现的极值问题的界，以及取到极值时图的行为，概率图论用概率的工具来研究图，代数图论用到更多代数结构的东西，spectral graph theory侧重于研究图的谱性质，比如由自然的adjecent matrix定义的特征值或者由laplace定义的特征值，而图又是很多问题的玩具模型所以图论在理论数学中和很多领域都密切相关。

在相关领域的应用中，图的结构会自然的出现,因此对于计算机和应用数学图论也是必修的一门重要的基础课

以下是Toronto大学的一次图论assignment.更多的经典案例请参阅以往案例，关于abstract algebra的更多的以往案例可以参阅相关文章。abstract algebra代写请认准UpriviateTA.

(a) Cut Property: the smallest edge crossing any cut must be in all MSTs. Reminder: a cut in a graph $G=(V, E)$ is a partition $A \cup B=V$.

(b) Cycle Property: The largest edge on any cycle is never in any MST.

(b) Let $C$ be a cycle in $G$ and let $e=(u, v)$ be the edge of maximum weight on $C .$ Suppose it is contained in an MST $T$. Deleting $e$ from $T$ we get two connected components $T_{1}, T_{2}$. But the cycle $C$ must contain an edge $f \neq e$ with one end in $T_{1}$ and one end in $T_{2},$ and $T-e+f$ is a tree of smaller weight. Contradiction.

$$

\begin{array}{c}

\left(\begin{array}{c}

n-2 \\

2

\end{array}\right) \geq|E(G)|-d(u)-d(v)>\left(\begin{array}{c}

n-1 \\

2

\end{array}\right)+1-d(u)-d(v) \\

\Longrightarrow \quad d(u)+d(v)>\left(\begin{array}{c}

n-1 \\

2

\end{array}\right)-\left(\begin{array}{c}

n-2 \\

2

\end{array}\right)+1=n-1

\end{array}

$$

Thus the condition of Exercise 2 holds, so $G$ has a Hamilton cycle.

2. Prove that every tournament has an almost central vertex.

Solution: We proceed by induction on the number of vertices. For $n=2,$ it is clear. Let $n>2$ and let $G=(V, A)$ be a tournament on $n$ vertices. Pick a vertex $w$ and consider the tournament $G^{\prime}=G-w$ on the set $V^{\prime}$ of $n-1$ vertices. By induction, there exists an almost central vertex $v$ in $G^{\prime}$. The situation now breaks down in three cases. If there is an arc $a \in A$ directed from $v$ to $w,$ then $v$ is almost central in $G .$ Otherwise, consider the sets $V_{i}^{\prime}:=\left\{u \in V^{\prime} \mid d(v, u)=i\right\}, i=1,2,$ of vertices at distance $i$ of $v .$ Note that because $v$ is almost central in $G^{\prime}$, we have that $\{v\} \cup V_{1}^{\prime} \cup V_{2}^{\prime}=V^{\prime}$. If there is an arc directed from $V_{1}^{\prime}$ to $w,$ the $v$ is almost central in $G .$ Otherwise, all arcs between $w$ and $V_{1}^{\prime}$ are directed from $w$ to $V_{1}^{\prime}$ and there is a directed path of length at most 2 from $w$ to all vertices in $V_{1}^{\prime} \cup V_{2}^{\prime} .$ Furthermore, $w$ and $v$ are connected by an arc from $w$ to $v$. Thus $w$ is almost central in $G$.

abstract algebra代写请认准UpriviateTA. UpriviateTA为您的留学生涯保驾护航。

更多内容请参阅另外一份Galois代写.