如果你也在 怎样代写图论Graph Theory 这个学科遇到相关的难题,请随时右上角联系我们的24/7代写客服。图论Graph Theory有趣的部分原因在于,图可以用来对某些问题中的情况进行建模。这些问题可以在图表的帮助下进行研究(并可能得到解决)。因此,图形模型在本书中经常出现。然而,图论是数学的一个领域,因此涉及数学思想的研究-概念和它们之间的联系。我们选择包含的主题和结果是因为我们认为它们有趣、重要和/或代表主题。
图论Graph Theory通过熟悉许多过去和现在对图论的发展负责的人,可以增强对图论的欣赏。因此,我们收录了一些关于“图论人士”的有趣评论。因为我们相信这些人是图论故事的一部分,所以我们在文中讨论了他们,而不仅仅是作为脚注。我们常常没有认识到数学是一门有生命的学科。图论是人类创造的,是一门仍在不断发展的学科。
couryes-lab™ 为您的留学生涯保驾护航 在代写图论Graph Theory方面已经树立了自己的口碑, 保证靠谱, 高质且原创的统计Statistics代写服务。我们的专家在代写图论Graph Theory代写方面经验极为丰富,各种代写图论Graph Theory相关的作业也就用不着说。
数学代写|图论作业代写Graph Theory代考|Algebraic planarity criteria
One of the most conspicuous features of a plane graph $G$ are its facial cycles, the cycles that bound a face. If $G$ is 2 -connected it is covered by its facial cycles, so in a sense these form a ‘large’ set. In fact, the set of facial cycles is large even in the sense that they generate the entire cycle space: every cycle in $G$ is easily seen to be the sum of the facial cycles (see below). On the other hand, the facial cycles only cover $G$ ‘thinly’, as every edge lies on at most two of them. Our first aim in this section is to show that the existence of such a large yet thinly spread family of cycles is not only a conspicuous feature of planarity but lies at its very heart: it characterizes it.
Let $G=(V, E)$ be any graph. We call a subset $\mathcal{F}$ of its edge space $\mathcal{E}(G)$ simple if every edge of $G$ lies in at most two sets of $\mathcal{F}$. For example, the cut space $\mathcal{C}^*(G)$ has a simple basis: according to Proposition 1.9.3 it is generated by the cuts $E(v)$ formed by all the edges at a given vertex $v$, and an edge $x y \in G$ lies in $E(v)$ only for $v=x$ and for $v=y$.
Theorem 4.5.1. (MacLane 1937)
A graph is planar if and only if its cycle space has a simple basis.
Proof. The assertion being trivial for graphs of order at most 2, we consider a graph $G$ of order at least 3. If $\kappa(G) \leqslant 1$, then $G$ is the union of two proper induced subgraphs $G_1, G_2$ with $\left|G_1 \cap G_2\right| \leqslant 1$. Then $\mathcal{C}(G)$ is the direct sum of $\mathcal{C}\left(G_1\right)$ and $\mathcal{C}\left(G_2\right)$, and hence has a simple basis if and only if both $\mathcal{C}\left(G_1\right)$ and $\mathcal{C}\left(G_2\right)$ do (proof?). Moreover, $G$ is planar if and only if both $G_1$ and $G_2$ are: this follows at once from Kuratowski’s theorem, but also from easy geometrical considerations. The assertion for $G$ thus follows inductively from those for $G_1$ and $G_2$. For the rest of the proof, we now assume that $G$ is 2-connected.
数学代写|图论作业代写Graph Theory代考|Plane duality
In this section we shall use MacLane’s theorem to uncover another connection between planarity and algebraic structure: a connection between the duality of plane graphs, defined below, and the duality of the cycle and cut space hinted at in Chapters 1.9 and 2.4.
A plane multigraph is a pair $G=(V, E)$ of finite sets (of vertices and edges, respectively) satisfying the following conditions:
(i) $V \subseteq \mathbb{R}^2$;
(ii) every edge is either an arc between two vertices or a polygon containing exactly one vertex (its endpoint);
(iii) apart from its own endpoint(s), an edge contains no vertex and no point of any other edge.
We shall use terms defined for plane graphs freely for plane multigraphs. Note that, as in abstract multigraphs, both loops and double edges count as cycles.
Let us consider the plane multigraph $G$ shown in Figure 4.6.1. Let us place a new vertex inside each face of $G$ and link these new vertices up to form another plane multigraph $G^$, as follows: for every edge $e$ of $G$ we link the two new vertices in the faces incident with $e$ by an edge $e^$ crossing $e$; if $e$ is incident with only one face, we attach a loop $e^$ to the new vertex in that face, again crossing the edge $e$. The plane multigraph $G^$ formed in this way is then dual to $G$ in the following sense: if we apply the same procedure as above to $G^$, we obtain a plane multigraph very similar to $G$; in fact, $G$ itself may be reobtained from $G^$ in this way.
图论代考
数学代写|图论作业代写Graph Theory代考|Algebraic planarity criteria
平面图形$G$最显著的特征之一是它的面循环,即约束面的循环。如果$G$是2连接的,那么它就被它的面部循环所覆盖,所以在某种意义上,这些形成了一个“大”集。事实上,面部循环的集合很大,甚至在它们产生整个循环空间的意义上:$G$中的每个循环很容易被看作是面部循环的总和(见下文)。另一方面,面部循环只“薄”覆盖$G$,因为每条边缘最多位于其中两条。在本节中,我们的第一个目的是要证明这样一个庞大而稀疏分布的循环族的存在不仅是平面性的一个显著特征,而且是它的核心:它是平面性的特征。
设$G=(V, E)$为任意图形。我们称其边空间$\mathcal{E}(G)$的子集$\mathcal{F}$为简单,如果$G$的每条边最多位于两个$\mathcal{F}$集合中。例如,切割空间$\mathcal{C}^*(G)$有一个简单的基础:根据命题1.9.3,它是由给定顶点$v$上的所有边形成的切割$E(v)$产生的,并且一条边$x y \in G$只在$v=x$和$v=y$上位于$E(v)$。
定理4.5.1。(麦克莱恩1937)
一个图是平面的当且仅当它的循环空间有一个简单基。
证明。这个断言对于阶数最多为2的图是微不足道的,我们考虑阶数至少为3的图$G$。如果$\kappa(G) \leqslant 1$,则$G$是两个适当诱导子图$G_1, G_2$与$\left|G_1 \cap G_2\right| \leqslant 1$的并集。那么$\mathcal{C}(G)$是$\mathcal{C}\left(G_1\right)$和$\mathcal{C}\left(G_2\right)$的直接和,因此有一个简单的基础当且仅当$\mathcal{C}\left(G_1\right)$和$\mathcal{C}\left(G_2\right)$都是(证明?)此外,$G$是平面的当且仅当$G_1$和$G_2$都是平面的:这不仅是由库拉托夫斯基定理得出的,而且也是由简单的几何考虑得出的。因此,$G$的断言归纳地遵循$G_1$和$G_2$的断言。对于剩下的证明,我们现在假设$G$是2连通的。
数学代写|图论作业代写Graph Theory代考|Plane duality
在本节中,我们将使用MacLane定理来揭示平面性和代数结构之间的另一种联系:下面定义的平面图的对偶性与第1.9章和第2.4章暗示的循环和切空间的对偶性之间的联系。
平面多重图是一对(分别由顶点和边组成)满足以下条件的有限集合$G=(V, E)$:
(i) $V \subseteq \mathbb{R}^2$;
(ii)每条边要么是两个顶点之间的弧,要么是一个只包含一个顶点(其端点)的多边形;
(iii)一条边除了自己的端点外,不包含任何顶点,也不包含任何其他边的点。
对于平面多重图,我们将自由地使用为平面图定义的术语。注意,在抽象多图中,循环和双边都算作循环。
让我们考虑图4.6.1所示的平面多图$G$。让我们在$G$的每个面内放置一个新顶点,并将这些新顶点连接起来形成另一个平面多图$G^$,如下所示:对于$G$的每条边$e$,我们通过一条边$e^$穿过$e$将与$e$相关的面中的两个新顶点连接起来;如果$e$只与一个面相关,我们将一个循环$e^$附加到该面的新顶点上,再次穿过边$e$。以这种方式形成的平面多图$G^$在以下意义上对偶于$G$:如果我们对$G^$应用相同的过程,我们得到一个与$G$非常相似的平面多图;事实上,$G$本身可以通过这种方式从$G^$重新获得。
统计代写请认准statistics-lab™. statistics-lab™为您的留学生涯保驾护航。