MY-ASSIGNMENTEXPERT™可以为您提供 users.cse.umn.edu Math 5707 Graph theory 图论的代写代考和辅导服务！
Math 5707课程简介
We will only be using the course Canvas site for turning in the homeworks and exams as PDFs.
If you write solutions by hand, then use a scanning app (e.g., Adobe Photo Scan) or a scanner to create the PDFs.
Do not just take a photo and convert it to PDF, as those are harder to read.
Late homework will not be accepted.
Homework solutions should be well-explained– the grader is told not to give credit for an unsupported answer.
Complaints about the grading should be brought to me.
Prerequisites
Grading scheme :
Homework = 40% of grade
Midterm 1 = 20% of grade
Midterm 2 = 20% of grade
Final exam = 20% of grade
Graphs are networks of vertices (nodes) connected by edges.
They are interesting objects in mathematics, but also usefully model
problems in computer science, optimization, and social science.
This is a first course in graph theory, emphasizing classical topics, such as
vertex degrees,
Euler and Hamilton circuits,
trees and Laplacian matrices,
matching theory and stable matchings (subject of the 2012 economics Nobel Prize),
network flows, connectivity,
vertex and edge-colorings,
perfect graphs (subject of a nice survey),
planarity and graphs on surfaces,
duality (a class exercise handout)
deletion-contraction, Tutte polynomials,
(a tiny bit of) probabilistic methods.
Math 5707 Graph theory HELP（EXAM HELP， ONLINE TUTOR）
Let $n$ be a positive integer, and $K$ be a nonempty finite set. Let $k=|K|$. A de Bruijn sequence of order $n$ on $K$ means a list $\left(c_0, c_1, \ldots, c_{k^n-1}\right)$ of $k^n$ elements of $K$ such that
(1) for each $n$-tuple $\left(a_1, a_2, \ldots, a_n\right) \in K^n$ of elements of $K$, there exists a unique $r \in\left{0,1, \ldots, k^n-1\right}$ such that $\left(a_1, a_2, \ldots, a_n\right)=\left(c_r, c_{r+1}, \ldots, c_{r+n-1}\right)$.
Here, the indices are understood to be cyclic modulo $k^n$; that is, $c_q$ (for $q \geq k^n$ ) is defined to be $c_q \% k^n$, where $q \% k^n$ denotes the remainder of $q$ modulo $k^n$.
Note that the condition (1) can be restated as follows: If we write the elements $c_0, c_1, \ldots, c_{k^n-1}$ on a circular necklace in this order, so that the last element $c_{k^n-1}$ is followed by the first one, then each $n$-tuple of elements of $K$ appears as a string of $n$ consecutive elements on the necklace, and the position at which it appears on the necklace is unique.
For example, $\left(c_0, c_1, c_2, c_3, c_4, c_5, c_6, c_7, c_8\right)=(1,1,2,2,3,3,1,3,2)$ is a de Bruijn sequence of order 2 on the set ${1,2,3}$, because for each 2-tuple $\left(a_1, a_2\right) \in$ ${1,2,3}^2$, there exists a unique $r \in{0,1, \ldots, 8}$ such that $\left(a_1, a_2\right)=\left(c_r, c_{r+1}\right)$. Namely:
$$
\begin{array}{lll}
(1,1)=\left(c_0, c_1\right) ; & (1,2)=\left(c_1, c_2\right) ; & (1,3)=\left(c_6, c_7\right) \
(2,1)=\left(c_8, c_9\right) ; & (2,2)=\left(c_2, c_3\right) ; & (2,3)=\left(c_3, c_4\right) \
(3,1)=\left(c_5, c_6\right) ; & (3,2)=\left(c_7, c_8\right) ; & (3,3)=\left(c_4, c_5\right)
\end{array}
$$
Prove that there exists a de Bruijn sequence of order $n$ on $K$ (no matter what $n$ and $K$ are).
Hint: Let $D$ be the digraph with vertex set $K^{n-1}$ and an arc from $\left(a_1, a_2, \ldots, a_{n-1}\right)$ to $\left(a_2, a_3, \ldots, a_n\right)$ for each $\left(a_1, a_2, \ldots, a_n\right) \in K^n$ (and no other arcs). Prove that $D$ has an Eulerian circuit.
Solution sketch to Exercise 3. The hint suggests defining a digraph. I shall use a multidigraph instead, as this is slightly simpler and cleaner.
Recall that a multidigraph means a triple $(V, A, \phi)$, where $V$ and $A$ are two finite sets and where $\phi$ is a map from $A$ to $V \times V$. We define a multidigraph $D$ to be $\left(K^{n-1}, K^n, f\right)$, where the map $f: K^n \rightarrow K^{n-1} \times K^{n-1}$ is given by the formula
$$
f\left(a_1, a_2, \ldots, a_n\right)=\left(\left(a_1, a_2, \ldots, a_{n-1}\right),\left(a_2, a_3, \ldots, a_n\right)\right) .
$$
(As usual, we write $f\left(a_1, a_2, \ldots, a_n\right)$ for $f\left(\left(a_1, a_2, \ldots, a_n\right)\right)$, since the extra parentheses do not add any clarity. Thus, in the multidigraph $D$, there is an arc from $\left(a_1, a_2, \ldots, a_{n-1}\right)$ to $\left(a_2, a_3, \ldots, a_n\right)$ for each $\left(a_1, a_2, \ldots, a_n\right) \in K^n$. (Note that if $n=1$, then there is only one vertex, namely the empty 0 -tuple () , but there are $|K|$ many arcs from it to itself. This is why we are using a multidigraph instead of a digraph. Of course, you are free to throw the $n=1$ case aside, seeing how easy it is to handle separately.
Recall that the indegree of a vertex $v$ of a multidigraph $(V, A, \phi)$ is defined to be the number of all arcs $a \in A$ whose target is $v$ that is, which satisfy $\phi(a)=(x, v)$ for some $x \in V$ . This indegree is denoted by $\operatorname{deg}^{-} v$. Also, the outdegree of a vertex $v$ of a multidigraph $(V, A, \phi)$ is defined to be the number of all arcs $a \in A$ whose source is $v$ (that is, which satisfy $\phi(a)=(v, x)$ for some $x \in V)$. This outdegree is denoted by $\operatorname{deg}^{+} v$.
Recall that a multidigraph $(V, A, \phi)$ is said to be strongly connected if $V \neq \varnothing$ and if, for any $u \in V$ and $v \in V$, there is at least one walk from $u$ to $v$ in the multidigraph. The multidigraph $D$ is strongly connected ${ }^3$. Moreover, each vertex $v \in K^{n-1}$ satisfies deg $\operatorname{deg}^{-} v=\mathrm{deg}^{+} v$ where both indegree and outdegree are taken respective to the multidigraph $D 4$.
Recall that a multidigraph has an Eulerian circuit if and only if it is strongly connected and each vertex $v$ satisfies $\operatorname{deg}^{-} v=\operatorname{deg}^{+} v$. Hence, the multidigraph $D$ has an Eulerian circuit since it is strongly connected and each vertex $v$ satisfies $\operatorname{deg}^{-} v=\operatorname{deg}^{+} v$ . Consider such an Eulerian circuit c. It contains each arc of $D$ exactly once, and thus has $k^n$ arcs (since the number of arcs of $D$ is $\left|K^n\right|=|K|^n=$ $k^n$ ). Let $p_0, p_1, \ldots, p_{k^n-1}$ be these arcs listed in the order in which they appear on the Eulerian circuit. We extend the indexing of these arcs modulo $k^n$; in other words, we set $p_i=p_{i \%} k^n$ for each $i \in \mathbb{Z}$. (This, of course, does not conflict with the already introduced notations $p_0, p_1, \ldots, p_{k^n-1}$, since each $i \in\left{0,1, \ldots, k^n-1\right}$ satisfies $\left.i \% k^n=i.\right)$
Let me now explain what I intend to do before I go into the technical details. We want to construct a de Bruijn sequence $\left(c_0, c_1, \ldots, c_{k^n-1}\right)$. I claim that the sequence of the first entries of the $n$-tuples $p_0, p_1, \ldots, p_{k^n-1}$ is such a de Bruijn sequence. Once this is proven, the exercise will clearly be solved.
Recall that the indegree of a vertex $v$ of a digraph $D=(V, A)$ is defined to be the number of all arcs $a \in A$ whose target is $v$. This indegree is denoted by deg d $^{-}(v)$ or by $\operatorname{deg}_D^{-}(v)$ whenever the graph $D$ is not clear from the context.
Likewise, the outdegree of a vertex $v$ of a digraph $D=(V, A)$ is defined to be the number of all arcs $a \in A$ whose source is $v$. This outdegree is denoted by deg ${ }^{+}(v)$ or by $\operatorname{deg}D^{+}(v)$ whenever the graph $D$ is not clear from the context. Exercise 4. Let $D$ be a digraph. Show that $\sum{v \in \mathrm{V}(D)} \operatorname{deg}^{-}(v)=\sum_{v \in \mathrm{V}(D)} \operatorname{deg}^{+}(v)$.
Fact 1. Let $(V, A, \phi)$ be a multidigraph. Then, $\sum_{v \in V} \operatorname{deg}^{-} v=\sum_{v \in V} \operatorname{deg}^{+} v$.
Fact 1 generalizes Exercise 4 , because each digraph $D=(V, A)$ gives rise to a multidigraph $\left(V, A, \mathrm{id}_A\right)$, and the indegrees and the outdegrees of the vertices of the former digraph are exactly the same as in the latter multidigraph. Hence, proving Fact 1 will suffice.
Proof of Fact 1. For each arc $a \in A$, let $s(a)$ denote the source of $a$, and let $t(a)$ denote the target of $a$. (Thus, each $a \in A$ satisfies $\phi(a)=(s(a), t(a))$.)
Now, let us count the number of $\operatorname{arcs} a \in A$ of our multidigraph in two different ways:
Each arc $a \in A$ has a unique source $s(a)$. Thus, we can obtain the number $|A|$ of all arcs $a \in A$ by computing, for each $v \in V$, the number of all arcs $a \in A$ satisfying $s(a)=v$, and then adding up these numbers over all $v \in V$. Thus, we obtain
$$
|A|=\sum_{v \in V} \underbrace{(\text { the number of all } a \in A \text { satisfying } s(a)=v)}{=\mathrm{deg}^{+} v}=\sum{v \in V} \operatorname{deg}^{+} v .
$$
(by the definition of the outdegree $\operatorname{deg}^{+} v$ of $v$ )
Each arc $a \in A$ has a unique target $t(a)$. Thus, we can obtain the number $|A|$ of all arcs $a \in A$ by computing, for each $v \in V$, the number of all arcs $a \in A$ satisfying $t(a)=v$, and then adding up these numbers over all $v \in V$. Thus, we obtain
$$
|A|=\sum_{v \in V} \underbrace{\text { (the number of all } a \in A \text { satisfying } t(a)=v)}{=\mathrm{deg}^{-} v}=\sum{v \in V} \mathrm{deg}^{-} v .
$$
(by the definition of the indegree $\operatorname{deg}^{-} v$ of $v$ )
Comparing (6) with (5), we obtain $\sum_{v \in V} \operatorname{deg}^{-} v=\sum_{v \in V} \operatorname{deg}^{+} v$. This proves Fact
1.
MY-ASSIGNMENTEXPERT™可以为您提供UNIVERSITY OF ILLINOIS URBANA-CHAMPAIGN MATH2940 linear algebra线性代数课程的代写代考和辅导服务！ 请认准MY-ASSIGNMENTEXPERT™. MY-ASSIGNMENTEXPERT™为您的留学生涯保驾护航。
