MY-ASSIGNMENTEXPERT™可以为您提供 lse.ac.uk MA316 Graph Theory 图论的代写代考和辅导服务！
这是伦敦政经学校图论课程的代写成功案例。
MA316课程简介
Teacher responsible
Prof Graham Brightwell
Availability
This course is available on the BSc in Data Science, BSc in Mathematics and Economics, BSc in Mathematics with Economics and BSc in Mathematics, Statistics and Business. This course is available as an outside option to students on other programmes where regulations permit. This course is available with permission to General Course students.
Pre-requisites MA103 or equivalent course giving a background in rigorous mathematics.
Prerequisites
Course content
This course examines the basic concepts and techniques of graph theory. The topics to be covered are: fundamental concepts, connectivity and matchings, colourings, extremal problems, Ramsey theory, the probabilistic method.
Teaching
20 hours of lectures and 10 hours of classes in the LT. 1 hour of lectures in the ST.
This course is taught through a combination of classes and lectures totalling a minimum of 30 hours in Lent Term.
MA316 Graph Theory HELP（EXAM HELP， ONLINE TUTOR）
The next few exercises are about tournaments. A tournament is a loopless ${ }^9$ digraph $D=(V, A)$ with the following property: For any two distinct vertices $u \in V$ and $v \in V$, precisely one of the two pairs $(u, v)$ and $(v, u)$ belongs to $A$. In other words, any two distinct vertices are connected by an arc in one direction, but not in both.
A 3-cycle ${ }^{10}$ in a tournament $D=(V, A)$ means a triple $(u, v, w)$ of vertices in $V$ such that all three pairs $(u, v),(v, w)$ and $(w, u)$ belong to $A$
Exercise 5. Let $D=(V, A)$ be a tournament. Set $n=|V|$ and $m=$ $\sum_{v \in V}\left(\begin{array}{c}\operatorname{deg}^{-}(v) \ 2\end{array}\right)$
(a) Show that $m=\sum_{v \in V}\left(\begin{array}{c}\operatorname{deg}^{+}(v) \ 2\end{array}\right)$.
(b) Show that the number of 3-cycles in $D$ is $3\left(\left(\begin{array}{l}n \ 3\end{array}\right)-m\right)$.
Solution sketch to Exercise 5. Let us introduce some convenient notations for this exercise:
- A 3-set shall mean a 3-element subset of $V$. Clearly, the number of all 3-sets is $\left(\begin{array}{l}n \ 3\end{array}\right)$ (since $|V|=n$ ).
- A 3-set ${u, v, w}$ is said to be cyclic if its elements in some order form a 3cycle (i.e., if one of the triples $(u, v, w),(u, w, v),(v, u, w),(v, w, u),(w, u, v)$ and $(w, v, u)$ is a 3-cycle).
- A 3-set ${u, v, w}$ is said to be acyclic if it is not cyclic.
- We say that a 3-set $S$ is sourced at a vertex $u \in V$ if this vertex $u$ belongs to $S$ and if the $\operatorname{arcs} u v$ and $u w$ are in $A$, where $v$ and $w$ are the two vertices of $S$ distinct from $u$.
- We say that a 3-set $S$ is targeted at a vertex $u \in V$ if this vertex $u$ belongs to $S$ and if the arcs $v u$ and $w u$ are in $A$, where $v$ and $w$ are the two vertices of $S$ distinct from $u$.
(a) Let us count the number of all acyclic 3-sets in two different ways. First, we make a few observations:
Observation 1: Let $u, v$ and $w$ be three distinct vertices in $V$ such that the $\operatorname{arcs} u v$ and $u w$ are in $A$. Then, ${u, v, w}$ is an acyclic 3 -set sourced at $u$. Observation 2: Let $u \in V$ be a vertex. Then, the number of all acyclic 3-sets sourced at $u$ is $\left(\begin{array}{c}\operatorname{deg}^{+} u \ 2\end{array}\right)$. - Proof of Observation 2. First of all, we introduce one more notion: An out-neighbor of $u$ shall mean a vertex $x \in V$ such that the arc $u x$ is in $A$. Clearly, the out-neighbors of $u$ are in bijection with the arcs of $D$ whose source is $u \quad{ }^{11}$. Hence, the number of the former out-neighbors equals the number of the latter arcs. Since the number of the latter arcs is $\operatorname{deg}^{+} u$ (indeed, this is how $\operatorname{deg}^{+} u$ was defined), we can thus conclude that the number of the former out-neighbors is $\operatorname{deg}^{+} u$. In other words, the number of all out-neighbors of $u$ is $\operatorname{deg}^{+} u$.
Observation 2 now easily follows: A 3-set is an acyclic 3-set sourced at $u$ if and only if it consists of $u$ and two distinct out-neighbors of $u$. Hence, choosing an acyclic 3-set sourced at $u$ is tantamount to choosing two distinct out-neighbors of $u$ (without specifying the order ${ }^{12}$ ). But the latter can be done in exactly $\left(\begin{array}{c}\operatorname{deg}^{+} u \ 2\end{array}\right)$ ways (since the number of all out-neighbors of $u$ is $\operatorname{deg}^{+} u$ ). Hence, the number of all acyclic 3-sets sourced at $u$ is $\left(\begin{array}{c}\operatorname{deg}^{+} u \ 2\end{array}\right) . \quad{ }^{13}$ This proves Observation 2.
If a tournament $D$ has a 3-cycle $(u, v, w)$, then we can define a new tournament $D_{u, v, w}^{\prime}$ as follows: The vertices of $D_{u, v, w}^{\prime}$ shall be the same as those of $D$. The arcs of $D_{u, v, w}^{\prime}$ shall be the same as those of $D$, except that the three $\operatorname{arcs}(u, v),(v, w)$ and $(w, u)$ are replaced by the three new $\operatorname{arcs}(v, u),(w, v)$ and $(u, w)$. (Visually speaking, $D_{u, v, w}^{\prime}$ is obtained from $D$ by turning the arrows on the $\operatorname{arcs}(u, v),(v, w)$ and $(w, u)$ around.) We say that the new tournament $D_{u, v, w}^{\prime}$ is obtained from the old tournament $D$ by a 3-cycle reversal operation.
Now, let $V$ be a finite set, and let $E$ and $F$ be two tournaments with vertex set $V$. Prove that $F$ can be obtained from $E$ by a sequence of 3-cycle reversal operations if and only if each $v \in V$ satisfies $\operatorname{deg}_E^{-}(v)=\operatorname{deg}_F^{-}(v)$. Note that a sequence may be empty, which allows handling the case $E=F$ even if $E$ has no 3-cycles to reverse.
Solution sketch to Exercise 6. Exercise 6 is Moon13, Theorem 35.
Here is another solution:
Let us forget about $V, E$ and $F$. Instead, we first introduce some more terminology:
If $(u, v)$ is an arc of a tournament $D$, then reversing this arc $(u, v)$ means replacing it by the $\operatorname{arc}(v, u)$ (in other words, removing the arc $(u, v)$, and adding a new $\operatorname{arc}(v, u)$ instead). The digraph that results from this operation is again a tournament. Visually speaking, reversing an arc in a tournament means turning the arrow on this arc around.
Using this terminology, our concept of “3-cycle reversal operation” can be reformulated as follows: A tournament $D^{\prime}$ is obtained from $D$ by a 3-cycle reversal operation if and only if there exists a 3-cycle $(u, v, w)$ such that $D^{\prime}$ is obtained from $D$ by reversing the $\operatorname{arcs}(u, v),(v, w)$ and $(w, u)$. If this is the case, we shall also say (more concretely) that $D^{\prime}$ is obtained from $D$ by reversing the 3-cycle $(u, v, w)$.
Let us introduce a new operation:
If a tournament $D$ has a cycle $\mathrm{c}=\left(v_0, v_1, \ldots, v_k\right)$, then we let $D_{\mathrm{c}}^{\prime \prime}$ be the tournament obtained from $D$ by reversing the $\operatorname{arcs}\left(v_0, v_1\right),\left(v_1, v_2\right), \ldots,\left(v_{k-1}, v_k\right)$. In other words, we let $D_c^{\prime \prime}$ be the tournament obtained from $D$ by reversing all arcs of the cycle c. We say that the new tournament $D_{\mathrm{c}}^{\prime \prime}$ is obtained from the old tournament $D$ by reversing the cycle c.
We now claim the following facts:
Observation 1: Let $D$ be a tournament. Let $\mathbf{c}$ be a cycle of $D$. Then, $\mathbf{c}$ has length $\geq 3$.
MY-ASSIGNMENTEXPERT™可以为您提供 LSE.AC.UK MA316 GRAPH THEORY 图论的代写代考和辅导服务！
