Scroll Top
19th Ave New York, NY 95822, USA

Graph Theory代写|图论代写|Hamitonion cycle代写|counting argument代写

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


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

问题 1. Show the following two properties of Minimum Spanning Trees (MST), under the assumption that no two edge weights are equal.
(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.
证明 . (a) Let $G=(V, E)$ be a graph, $A \cup B=V$ a cut of this graph and let $T$ be a spanning tree of $G .$ Let $e=(u, v)$ be the edge of minimum weight that crosses from $A$ to $B$. Suppose now that $T$ does not contain $e .$ Since $T$ is connected, it contains a path $P$ between $u$ and $v,$ and $P$ must contain an edge $f$ that crosses from $A$ to $B$. But $T^{\prime}=T-f+e$ is a tree of smaller weight, which is a contradiction.
(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.
问题 2. Let $G=(V, E)$ be a graph with weights $w: E \rightarrow \mathbb{R}$. Consider the problem of identifying a forest of maximum weight in $G .$ Show that this problem can be reduced to the problem of computing a minimum weight spanning tree in a suitable graph $G^{\prime}$ with weights $w^{\prime} .$ Is your reduction efficient in the sense that $G^{\prime}$ is of polynomial size in $G ?$
证明 . We construct a new graph $G^{\prime}=\left(V^{\prime}, E^{\prime}\right)$ with edge weight $w^{\prime}: E^{\prime} \rightarrow \mathbb{R}$ such that $V \subseteq V^{\prime}$ $E \subseteq E^{\prime}$ and a minimum weight spanning tree of $G^{\prime}$ restricted to $G$ is a maximum weight forest of $G .$ Let $V^{\prime}=V \cup\{u\}$ where $u$ is a new vertex and let $E^{\prime}=E \cup\{(u, v): v \in V\}$ be the new edge set. Define $w^{\prime}(e)=-w(e)$ for all edges $e \in E$ and $w^{\prime}(e)=0$ otherwise. Let $T$ be a spanning tree of $G^{\prime}$ and $F$ its restriction to $G .$ Then if $F$ is not of maximal weight, there exists an other forest $F^{\prime}$ with higher weight. Adding an edge from $u$ to each connected component of $F^{\prime}$ gives a tree in $G^{\prime}$ whose weight is lower than the weight of $T$. This implies that $T$ was not a minimal weight spanning tree and thus each minimal weight spanning tree of $G^{\prime}$ gives a maximal weight forest in $G$.
问题 3. Use Ore’s theorem to give a short proof of the fact that any $n$ -vertex graph $G$ with more than $\left(\begin{array}{c}n-1 \\ 2\end{array}\right)+1$ has a Hamilton cycle.
证明 . Set $|V(G)|=n$. If the graph is complete then it has a Hamilton cycle. Consider two nonadjacent vertices $u, v$. Remove them to get a graph $G-u-v$ with $n-2$ vertices and $|E(G)|-d(u)-d(v)$ edges. It has at most $\left(\begin{array}{c}n-2 \\ 2\end{array}\right)$ edges, so we have
n-2 \\
\end{array}\right) \geq|E(G)|-d(u)-d(v)>\left(\begin{array}{c}
n-1 \\
\end{array}\right)+1-d(u)-d(v) \\
\Longrightarrow \quad d(u)+d(v)>\left(\begin{array}{c}
n-1 \\
n-2 \\
Thus the condition of Exercise 2 holds, so $G$ has a Hamilton cycle.
问题 4. We say that a vertex $u$ in a tournament is almost central if for every other vertex $v$, there is a directed $u-v$ path of length at most
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

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


Leave a comment