MY-ASSIGNMENTEXPERT™可以为您提供 sydney MATH2069 Graph Theory图论的代写代考和辅导服务！
这是悉尼大学图论课程的代写成功案例。
MATH2069课程简介
This unit introduces students to several related areas of discrete mathematics, which serve their interests for further study in pure and applied mathematics, computer science and engineering. Topics to be covered in the first part of the unit include recursion and induction, generating functions and recurrences, combinatorics. Topics covered in the second part of the unit include Eulerian and Hamiltonian graphs, the theory of trees (used in the study of data structures), planar graphs, the study of chromatic polynomials (important in scheduling problems).
Prerequisites
At the completion of this unit, you should be able to:
- LO1. identify and use combinatorial objects involved in counting problems to solve them
- LO2. solve linear recurrence relations by using generating functions and characteristic equations
- LO3. identify Eulerian and Hamiltonian graphs
- LO4. apply special algorithms to find minimal walks in weighted graphs
- LO5. apply special algorithms to find spanning trees in graphs
- LO6. find chromatic numbers and chromatic polynomials of graphs.
MATH2069 Graph Theory HELP（EXAM HELP， ONLINE TUTOR）
Prove Heawood’s theorem that a plane triangulation is 3 -colorable if and only if all its vertices have even degree.
Solution: Let $G$ be a plane triangulation. Then the dual graph $G^$ is 3 -regular. $G$ is 3 -colorable if and only if $G^$ has a 3-flow. By Proposition 6.4.2, a cubic graph has a 3 -flow if and only if it is bipartite. It is equivalent to say $G^*$ is bipartite, or $G$ has a 2 -flow. It is necessary and sufficient that all its degrees of $G$ have even degree.
Show that a graph $G=(V, E)$ has a $k$-flow if and only if it admits an orientation $D$ that directs, for every $X \subset V$, at least $\frac{1}{k}$ of the edges in $E(X, \bar{X})$ from $X$ towards $\bar{X}$.
Solution: One direction is easy. Suppose that $G$ has a $k$-flow $f$. One may orient an edge $e$ so that $f(\vec{e})>0$. For any partition of $C=X \cup \bar{X}$. We have $f(X, \bar{X})=0$. Let $a$ be the number of edges oriented from $X$ to $\bar{X}$ and $a$ be the number of edges oriented from $\bar{X}$ to $X$. We have
$$
0=f(X, \bar{X}) \leq(k-1) a-b .
$$
This implies that $a \geq \frac{1}{k}(a+b)=\frac{1}{k}|E(X, \bar{X})|$.
For the other direction, we need to prove a stronger statement for induction. Suppose that $G$ admits an orientation $D$ that directs, for every $X \subset V$, at least $\frac{1}{k}$ of the edges in $E(X, \bar{X})$ from $X$ towards $\bar{X}$. We assign each directed edge $\vec{e}$ a capacity $c_{\vec{e}}$. Initially all capacities are set to be $k-1$. We say the capacity $\left{c_{\vec{e}}\right}$ is balanced, if for any vertex partition $V=X \cup \bar{X}$, we have
$$
\sum_{\vec{e} \in \vec{E}D(X, \bar{X})} c{\vec{e}} \geq\left|\vec{E}_D(\bar{X}, X)\right| .
$$
The property “for every $X \subset V$, at least $\frac{1}{k}$ of the edges in $E(X, \bar{X})$ from $X$ towards $\bar{X}$ ” implies that the initial capacity is balanced.
Claim: If $D$ has a balanced capacity $\left{c_{\vec{e}}\right}$, then $G$ has an integer flow $f$ so that for each directed edge $\vec{e}, 1 \leq f(\vec{e}) \leq c_{\vec{e}}$.
We will prove the Claim by induction on the sum of all capacities. It is trivial if $G$ is an empty graph, otherwise, we assume the claim holds for smaller graphs or smaller capacities. Note that if $G$ has a balanced capacity then every non-isolated vertex has positive indegree and outdegree. $G$ must contain a directed cycle $C$. Now we push a flow $f_C$ on $C$ by 1 unit along the direction of $C$ and decreasing each capacity of the edge of $C$ by 1. If some edge has 0 capacity, delete that edge. Note that the balanced property still holds after updating the capacity. By induction, the new graph and new capacity has a flow $g$. Now let $f=g+f_C$. This is the $k$-flow of $G$.
Determine the value of $\operatorname{ex}\left(n, K_{1, r}\right)$ for all $r, n \in \mathbb{N}$.
Solution: We would like to determine how many edges a graph $G$ on $n$ vertices can have before a $K_{1, r}$ subgraph is forced. Note that $G$ has a $K_{1, r}$ subgraph if and only if $\Delta(G) \geq r$. Thus, we must determine the maximum number of edges $G$ can have and still maintain $\Delta(G)<r$. We consider two cases:
Case 1: $n \leq r$. Clearly, if $n \leq r$, we must have $\Delta(G)r$. In this case, we try to draw edges on the vertices of $G$ so that $d(v)=r-1$ for all $v \in V(G)$. While it may not be possible to draw an $r-1$-regular graph on $n$ vertices, we are able to draw $\left\lfloor\frac{(r-1) \cdot n}{2}\right\rfloor$ edges. Thus $\operatorname{ex}\left(n, K_{1, r}\right)=\left\lfloor\frac{(r-1) \cdot n}{2}\right\rfloor$.
Given $k>0$, determine the extremal graphs without a matching of size $k$.
Solution: Let $n \in \mathbb{N}$ and $k>0$. We will consider two cases:
Suppose $n<2 k$. The complete graph $K_{2 n}$ will certainly have no matching of size $k$. This graph $K_{2 n}$ has $\left(\begin{array}{l}n \ 2\end{array}\right)$ edges, and we certainly cannot better. Thus $K_{2 n}$ is the extremal graph in this case.
Suppose $n \geq 2 k$. We construct the extremal graph in the following way: First, construct a $K_{k-1}$. Then, draw an edge from each of the remaining $(n-k+1)$ vertices to each of the edges in the $K_{k-1}$. Then every edge in a maximal matching will be incident to a vertex in the $K_{k-1}$. Thus, the size of the maximal matching on this graph is $k-1$. This graph has $\left(\begin{array}{c}k-1 \ 2\end{array}\right)+(n-k+1)(k-1)$ edges, and it is the extremal graph.
MY-ASSIGNMENTEXPERT™可以为您提供 SYDNEY MATH2069 GRAPH THEORY图论的代写代考和辅导服务！
