Posted on Categories:Graph Theory, 图论, 数学代写

数学代写|图论代考GRAPH THEORY代写|CS150

avatest™

avatest™帮您通过考试

avatest™的各个学科专家已帮了学生顺利通过达上千场考试。我们保证您快速准时完成各时长和类型的考试，包括in class、take home、online、proctor。写手整理各样的资源来或按照您学校的资料教您，创造模拟试题，提供所有的问题例子，以保证您在真实考试中取得的通过率是85%以上。如果您有即将到来的每周、季考、期中或期末考试，我们都能帮助您！

•最快12小时交付

•200+ 英语母语导师

•70分以下全额退款

数学代写|图论代写GRAPH THEORY代考|Properties of a Tree

There are many different sets of properties of trees; any of these sets of properties can be taken as a definition of a tree. In this section, we discuss these properties of a tree. We first observe the following two trivial properties of a tree which play crucial roles while dealing with trees.
Lemma 4.2.1 Every tree with two or more vertices has at least two leaves.
Proof Let $T$ be a tree of two or more vertices and let $P$ be a maximal path in $T$. Then the end vertices $u$ and $v$ of $P$ have degree 1 (see Fig.4.1(f)), otherwise $P$ would not be a maximal path in $T$.

Lemma 4.2.2 Every edge in a tree is a cut edge.
Proof Immediate from Lemma 3.1.4.
The following lemma gives some characterization of trees.
Lemma 4.2.3 Let $G$ be a graph with $n$ vertices. Then, any two of the following three statements imply the third (and characterize a tree of $n$ vertices).
(a) $G$ is connected.
(b) $G$ contains no cycle.
(c) $G$ has $n-1$ edges.
Proof (a) \& (b) $\Rightarrow$ (c). We first prove that a connected and acyclic graph $G$ with $n$ vertices has $n-1$ edges. The claim is obvious for $n=1$ since a graph with a single vertex and no cycle has no edges. We thus assume that $n>1$ and the claim is true for any connected and acyclic graph with less than $n$ vertices. We now show that the graph $G$ with $n$ vertices has $n-1$ edges. Since $G$ contains no cycle, every edge $e$ of $G$ is a cut edge. Let $H_1$ and $H_2$ be the two connected components of $G-e$ with $n_1$ and $n_2$ vertices, respectively, where $n_1+n_2=n$. Since both $H_1$ and $H_2$ are acyclic and connected, they contain $n_1-1$ and $n_2-1$ edges respectively. Then the total number of edges in $G$ is $n_1-1+n_2-1+1=n-1$.

数学代写|图论代写GRAPH THEORY代考|Rooted Trees

A rooted tree is a tree in which one of the vertices is distinguished from the others. The distinguished vertex is called the root of the tree. The root of a tree is usually drawn at the top. In Fig. 4.3, the root is $v_1$. If a rooted tree is regarded as a directed graph in which each edge is directed from top to bottom, then every vertex $u$ other than the root is connected by an edge from some other vertex $p$, called the parent of $u$. We also call $u$ a child of vertex $p$. We draw the parent of a vertex above that vertex. For example, in Fig. 4.3, $v_1$ is the parent of $v_2, v_3$, and $v_4$, while $v_2$ is the parent of $v_5$ and $v_6 ; v_2, v_3$, and $v_4$ are the children of $v_1$, while $v_5$ and $v_6$ are the children of $v_2$. A leaf is a vertex of a tree that has no children. An internal vertex is a vertex that has one or more children. Thus every vertex of a tree is either a leaf or an internal vertex. In Fig. 4.3, the leaves are $v_4, v_5, v_6$, and $v_7$, and the vertices $v_1, v_2$, and $v_3$ are internal vertices.

The parent-child relationship can be extended naturally to ancestors and descendants. Suppose that $u_1, u_2, \ldots, u_l$ is a sequence of vertices in a tree such that $u_1$ is the parent of $u_2$, which is a parent of $u_3$, and so on. Then vertex $u_1$ is called an ancestor of $u_l$ and vertex $u_l$ a descendant of $u_1$. The root is ancestor of every other vertex in a tree and every other vertex is a descendant of the root. In Fig. 4.3, $v_1$ is an ancestor of all other vertices, and all other vertices are descendants of the root $v_1$. Note that the definition of ancestor (descendant) does not allow a vertex to be an ancestor (descendant) of itself. However, there are some definitions of ancestor (descendant) which allow a vertex to be an ancestor (descendant) of itself.

A rooted tree is called a binary tree if each vertex has at most two children. In general, a rooted tree is called a $k$-ary tree if each vertex has at most $k$ children. That is, the maximum number of children of a vertex in a $k$-ary tree is $k$.

An ordered rooted tree is a rooted tree in which the children of a vertex is somehow ordered. For example, in a ordered rooted binary tree the children of a vertex are ordered as the left child and the right child. The children of a vertex in a ordered rooted tree may also be ordered in a clockwise or in a counterclockwise order.

数学代写|图论代写GRAPH THEORY代考|Properties of a Tree

(a)连接$G$。
(b) $G$不包含循环。
(c) $G$有$n-1$条边。