如果你也在 怎样代写图论Graph Theory 这个学科遇到相关的难题，请随时右上角联系我们的24/7代写客服。图论Graph Theory有趣的部分原因在于，图可以用来对某些问题中的情况进行建模。这些问题可以在图表的帮助下进行研究(并可能得到解决)。因此，图形模型在本书中经常出现。然而，图论是数学的一个领域，因此涉及数学思想的研究-概念和它们之间的联系。我们选择包含的主题和结果是因为我们认为它们有趣、重要和/或代表主题。

图论Graph Theory通过熟悉许多过去和现在对图论的发展负责的人，可以增强对图论的欣赏。因此，我们收录了一些关于“图论人士”的有趣评论。因为我们相信这些人是图论故事的一部分，所以我们在文中讨论了他们，而不仅仅是作为脚注。我们常常没有认识到数学是一门有生命的学科。图论是人类创造的，是一门仍在不断发展的学科。

statistics-lab™ 为您的留学生涯保驾护航 在代写图论Graph Theory方面已经树立了自己的口碑, 保证靠谱, 高质且原创的统计Statistics代写服务。我们的专家在代写图论Graph Theory代写方面经验极为丰富，各种代写图论Graph Theory相关的作业也就用不着说。

数学代写|图论作业代写Graph Theory代考|Drawings

An embedding in the plane, or planar embedding, of an (abstract) graph $G$ is an isomorphism between $G$ and a plane graph $H$. The latter will be called a drawing of $G$. We shall not always distinguish notationally between the vertices and edges of $G$ and of $H$. In this section we investigate how two planar embeddings of a graph can differ.

How should we measure the likeness of two embeddings $\rho: G \rightarrow H$ and $\rho^{\prime}: G \rightarrow H^{\prime}$ of a planar graph $G ?$ An obvious way to do this is to consider the canonical isomorphism $\sigma:=\rho^{\prime} \circ \rho^{-1}$ between $H$ and $H^{\prime}$ as abstract graphs, and ask how much of their position in the plane this isomorphism respects or preserves. For example, if $\sigma$ is induced by a simple rotation of the plane, we would hardly consider $\rho$ and $\rho^{\prime}$ as genuinely different ways of drawing $G$.

So let us begin by considering any abstract isomorphism $\sigma: V \rightarrow V^{\prime}$ between two plane graphs $H=(V, E)$ and $H^{\prime}=\left(V^{\prime}, E^{\prime}\right)$, with face sets $F(H)=: F$ and $F\left(H^{\prime}\right)=: F^{\prime}$ say, and try to measure to what degree $\sigma$ respects or preserves the features of $H$ and $H^{\prime}$ as plane graphs. In what follows we shall propose three criteria for this in decreasing order of strictness (and increasing order of ease of handling), and then prove that for most graphs these three criteria turn out to agree. In particular, applied to the isomorphism $\sigma=\rho^{\prime} \circ \rho^{-1}$ considered earlier, all three criteria will say that there is essentially only one way to draw a 3-connected graph.

Our first criterion for measuring how well our abstract isomorphism $\sigma$ preserves the plane features of $H$ and $H^{\prime}$ is perhaps the most natural one. Intuitively, we would like to call $\sigma$ ‘topological’ if it is induced by a homeomorphism from the plane $\mathbb{R}^2$ to itself. To avoid having to grant the outer faces of $H$ and $H^{\prime}$ a special status, however, we take a detour via the homeomorphism $\pi: S^2 \backslash{(0,0,1)} \rightarrow \mathbb{R}^2$ chosen in Section 4.1: we call $\sigma$ a topological isomorphism between the plane graphs $H$ and $H^{\prime}$ if there exists a homeomorphism $\varphi: S^2 \rightarrow S^2$ such that $\psi:=\pi \circ \varphi \circ \pi^{-1}$ induces $\sigma$ on $V \cup E$. (More formally: we ask that $\psi$ agree with $\sigma$ on $V$, and that it map every plane edge $x y \in H$ onto the plane edge $\sigma(x) \sigma(y) \in$ $H^{\prime}$. Unless $\varphi$ fixes the point $(0,0,1)$, the map $\psi$ will be undefined at $\pi\left(\varphi^{-1}(0,0,1)\right)$.)

数学代写|图论作业代写Graph Theory代考|Planar graphs: Kuratowski’s theorem

A graph is called planar if it can be embedded in the plane: if it is isomorphic to a plane graph. A planar graph is maximal, or maximally planar, if it is planar but cannot be extended to a larger planar graph by adding an edge (but no vertex).

Drawings of maximal planar graphs are clearly maximally plane. The converse, however, is not obvious: when we start to draw a planar graph, could it happen that we get stuck half-way with a proper subgraph that is already maximally plane? Our first proposition says that this can never happen, that is, a plane graph is never maximally plane just because it is badly drawn:
Proposition 4.4.1.
(i) Every maximal plane graph is maximally planar.
(ii) A planar graph with $n \geqslant 3$ vertices is maximally planar if and only if it has $3 n-6$ edges.
Proof. Apply Proposition 4.2.8 and Corollary 4.2.10.

Which graphs are planar? As we saw in Corollary 4.2.11, no planar graph contains $K^5$ or $K_{3,3}$ as a topological minor. Our aim in this section is to prove the surprising converse, a classic theorem of Kuratowski: any graph without a topological $K^5$ or $K_{3,3}$ minor is planar.

Before we prove Kuratowski’s theorem, let us note that it suffices to consider ordinary minors rather than topological ones:

Lemma 4.4.2. A graph contains $K^5$ or $K_{3,3}$ as a minor if and only if it contains $K^5$ or $K_{3,3}$ as a topological minor.

Proof. By Proposition 1.7.2 it suffices to show that every graph $G$ $(1.7 .2)$ with a $K^5$ minor contains either $K^5$ as a topological minor or $K_{3,3}$ as a minor. So suppose that $G \succcurlyeq K^5$, and let $K \subseteq G$ be minimal such that $K=M K^5$. Then every branch set of $K$ induces a tree in $K$, and between any two branch sets $K$ has exactly one edge. If we take the tree induced by a branch set $V_x$ and add to it the four edges joining it to other branch sets, we obtain another tree, $T_x$ say. By the minimality of $K, T_x$ has exactly 4 leaves, the 4 neighbours of $V_x$ in other branch sets (Fig. 4.4.1).

图论代考

数学代写|图论作业代写Graph Theory代考|Drawings

(抽象)图$G$的平面嵌入或平面嵌入是$G$与平面图$H$之间的同构。后者将被称为$G$的绘图。我们并不总是用符号来区分$G$和$H$的顶点和边。在本节中，我们研究一个图的两个平面嵌入是如何不同的。

我们应该如何测量平面图形的两个嵌入$\rho: G \rightarrow H$和$\rho^{\prime}: G \rightarrow H^{\prime}$的相似性$G ?$一个明显的方法是考虑$H$和$H^{\prime}$之间的规范同构$\sigma:=\rho^{\prime} \circ \rho^{-1}$作为抽象图形，并询问它们在平面上的同构尊重或保留了多少位置。例如，如果$\sigma$是由平面的简单旋转引起的，我们几乎不会认为$\rho$和$\rho^{\prime}$是绘制$G$的真正不同的方法。

因此，让我们首先考虑两个平面图形$H=(V, E)$和$H^{\prime}=\left(V^{\prime}, E^{\prime}\right)$之间的抽象同构$\sigma: V \rightarrow V^{\prime}$，比如面集$F(H)=: F$和$F\left(H^{\prime}\right)=: F^{\prime}$，并尝试测量$\sigma$在多大程度上尊重或保留了$H$和$H^{\prime}$作为平面图形的特征。在接下来的内容中，我们将按照严格程度的递减顺序(以及易处理程度的递增顺序)提出三条准则，然后证明对于大多数图，这三条准则是一致的。特别是，应用于前面考虑的同构$\sigma=\rho^{\prime} \circ \rho^{-1}$，所有三个标准都表明，实际上只有一种方法可以绘制3连通图。

我们衡量抽象同构$\sigma$在多大程度上保留了$H$和$H^{\prime}$的平面特征的第一个标准可能是最自然的标准。直观地说，如果$\sigma$是由平面$\mathbb{R}^2$到自身的同胚引起的，我们就把它称为“拓扑的”。然而，为了避免不得不赋予$H$和$H^{\prime}$的外表面一个特殊的地位，我们绕道通过4.1节中选择的同胚性$\pi: S^2 \backslash{(0,0,1)} \rightarrow \mathbb{R}^2$:我们称$\sigma$为平面图$H$和$H^{\prime}$之间的拓扑同构，如果存在一个同胚性$\varphi: S^2 \rightarrow S^2$，使得$\psi:=\pi \circ \varphi \circ \pi^{-1}$在$V \cup E$上诱导出$\sigma$。(更正式地说:我们要求$\psi$同意$V$上的$\sigma$，并且它将每个平面边$x y \in H$映射到平面边$\sigma(x) \sigma(y) \in$$H^{\prime}$上。除非$\varphi$固定了$(0,0,1)$点，否则映射$\psi$在$\pi\left(\varphi^{-1}(0,0,1)\right)$处将是未定义的。)

数学代写|图论作业代写Graph Theory代考|Planar graphs: Kuratowski’s theorem

如果一个图可以嵌入到平面中，如果它与一个平面图同构，则称为平面图。如果平面图是平面的，但不能通过添加边(但没有顶点)扩展为更大的平面图，则该平面图是最大平面。

最大平面图的绘制显然是最大平面。然而，相反的情况并不明显:当我们开始画一个平面图时，我们会不会在画到一半的时候被一个已经是最大平面的适当子图卡住了?我们的第一个命题是，这种情况永远不会发生，也就是说，一个平面图形永远不会因为画得不好而成为最大平面;
提案4.4.1。
(i)每个最大平面图都是最大平面。
(ii)有$n \geqslant 3$个顶点的平面图当且仅当它有$3 n-6$条边时才是最大平面。
证明。应用命题4.2.8和推论4.2.10。

哪些图形是平面的?正如我们在推论4.2.11中看到的，没有平面图包含$K^5$或$K_{3,3}$作为拓扑次元。本节的目的是证明一个惊人的逆定理，库拉托夫斯基的一个经典定理:任何没有拓扑$K^5$或$K_{3,3}$次元的图都是平面的。

在我们证明Kuratowski定理之前，让我们注意到，考虑普通次子而不是拓扑次子就足够了:

引理4.4.2。当且仅当图中包含$K^5$或$K_{3,3}$作为拓扑次元时，图中包含$K^5$或$K_{3,3}$作为次元。

证明。根据命题1.7.2，足以表明每个具有$K^5$次元的图$G$$(1.7 .2)$都包含$K^5$作为拓扑次元或$K_{3,3}$作为次元。假设$G \succcurlyeq K^5$，让$K \subseteq G$最小使得$K=M K^5$。那么$K$的每个分支集都在$K$中引出一棵树，并且在任意两个分支集$K$之间只有一条边。如果我们取一个分支集$V_x$生成的树，并加上将它与其他分支集连接起来的四条边，我们就得到了另一棵树$T_x$。根据极小性，$K, T_x$恰好有4个叶子，那么$V_x$在其他分支集中的4个邻居(图4.4.1)。

统计代写请认准statistics-lab™. statistics-lab™为您的留学生涯保驾护航。