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. Recall that $K_n$ denotes the complete graph on $n$ vertices. This is the graph with vertex set $V={1,2, \ldots, n}$ and edge set $\mathcal{P}_2(V)$ (so each two distinct vertices are connected).
Find Eulerian circuits for the graphs $K_3, K_5$, and $K_7$.
Solution sketch to Exercise 2. An Eulerian circuit of $K_3$ is $(1,2,3,1)$.
An Eulerian circuit of $K_5$ is $(1,2,3,4,5,1,3,5,2,4,1)$.
An Eulerian circuit of $K_7$ is $(1,2,3,4,5,6,7,1,3,5,7,2,4,6,1,4,7,3,6,2,5,1)$.
[Remark: Of course, other choices are possible. For each odd positive integer $n$, the complete graph $K_n$ has an Eulerian circuit (because it is connected, and each of its vertices has even degree $n-1$ ), and so it has at least one Eulerian circuit; but in truth, there are many. (How many? See OEIS entry A007082. There doesn’t seem to be an explicit formula.)
When $n$ is an odd prime ${ }^2$, there is actually a simple way to construct an Eulerian circuit in $K_n$ : For each $k \in{1,2, \ldots,(n-1) / 2}$, let $c_k$ be the cycle $\left(a_0, a_1, \ldots, a_n\right)$, where $a_i$ denotes the unique element of $(1,2, \ldots, n)$ that is congruent to $k i+1$ modulo $n$. Then, the cycles $c_1, c_2, \ldots, c_{(n-1) / 2}$ can be combined to a single Eulerian circuit. Finding Eulerian circuits on $K_n$ for non-prime $n$ is harder, but of course the algorithm done in class still works.
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}
$$
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.
MY-ASSIGNMENTEXPERT™可以为您提供UNIVERSITY OF ILLINOIS URBANA-CHAMPAIGN MATH2940 linear algebra线性代数课程的代写代考和辅导服务！ 请认准MY-ASSIGNMENTEXPERT™. MY-ASSIGNMENTEXPERT™为您的留学生涯保驾护航。
