数学代写代考| Undirected Graphs 离散数学代写 - 代考代写：100%准时可靠您的作业代写专家

A directed graph (Fig. 9.4) is a pair of finite sets (V, E) where E is a binary relation (that may not be symmetric) on V. A directed acylic graph (dag) is a directed graph that has no cycles. The example below is of a directed graph with three edges and four vertices.

An edge $e \in \mathrm{E}$ consists of a pair $\langle x, y\rangle$ where $x, y$ are adjacent nodes in the graph. The degree of $x$ is the number of nodes that are adjacent to $x$. The set of edges is denoted by $\mathrm{E}(\mathrm{G})$, and the set of vertices is denoted by $\mathrm{V}(\mathrm{G})$.

A weighted graph is a graph $\mathrm{G}=(\mathrm{V}, \mathrm{E})$ together with a weighting function $w: \mathrm{E} \rightarrow \mathbb{N}$, which associates a weight with every edge in the graph. A weighting function may be employed in modelling computer networks: for example, the weight of an edge may be applied to model the bandwidth of a telecommunications link between two nodes. Another application of the weighting function is in determining the distance (or shortest path) between two nodes in the graph (where such a path exists).

For an directed graph, the weight of the edge is the same in both directions: i.e. $w\left(v_{i}, v_{j}\right)=w\left(v_{j}, v_{i}\right)$ for all edges $$ in the graph $\mathrm{G}$, whereas the weights may be different for a directed graph.

Two vertices $x, y$ are adjacent if $x y \in \mathrm{E}$, and $x$ and $y$ are said to be incident to the edge $x y .$ A matrix may be employed to represent the adjacency relationship.
150
9 Graph Theory
Example 9.1 Consider the graph $\mathrm{G}=(\mathrm{V}, \mathrm{E})$ where $\mathrm{E}={u=a b, v=c d, w=f g,$, $x=b g, y=a f}$.

An adjacency matrix (Fig. 9.5) may be employed to represent the relationship of adjacency in the graph. Its construction involves listing the vertices in the rows and columns, and an entry of 1 is made in the table if the two vertices are adjacent and 0 otherwise.

Similarly, we can construct a table describing the incidence of edges and vertices by constructing an incidence matrix (Fig. 9.6). This matrix lists the vertices and edges in the rows and columns, and an entry of 1 is made if the vertex is one of the nodes of the edge and 0 otherwise.

Two graphs $\mathrm{G}=(\mathrm{V}, \mathrm{E})$ and $\mathrm{G}^{\prime}=\left(\mathrm{V}^{\prime}, \mathrm{E}^{\prime}\right)$ are said to be isomorphic if there exists a bijection $f: \mathrm{V} \rightarrow \mathrm{V}^{\prime}$ such that for any $u, v \in \mathrm{V}, u v \in \mathrm{E}, f(u) f(v) \in \mathrm{E}^{\prime}$. The mapping $f$ is called an isomorphism. Two graphs that are isomorphic are essentially equivalent apart from a re-labelling of the nodes and edges.

Let $\mathrm{G}=(\mathrm{V}, \mathrm{E})$ and $\mathrm{G}^{\prime}=\left(\mathrm{V}^{\prime}, \mathrm{E}^{\prime}\right)$ be two graphs then $\mathrm{G}^{\prime}$ is a subgraph of $\mathrm{G}$ if $\mathrm{V}^{\prime} \subseteq \mathrm{V}$ and $\mathrm{E}^{\prime} \subseteq \mathrm{E}$. Given $\mathrm{G}=(\mathrm{V}, \mathrm{E})$ and $\mathrm{V}^{\prime} \subseteq \mathrm{V}$ then we can induce a subgraph $\mathrm{G}$ $^{\prime}=\left(\mathrm{V}^{\prime}, \mathrm{E}^{\prime}\right)$ by restricting $\mathrm{G}$ to $\mathrm{V}^{\prime}$ (denoted by $\left.\mathrm{G}\left|\mathrm{V}^{\prime}\right|\right)$. The set of edges in $\mathrm{E}^{\prime}$ is defined as
$$
\mathrm{E}^{\prime}=\left{e \in \mathrm{E}: e=u v \text { and } u, v \in \mathrm{V}^{\prime}\right}
$$
The degree of a vertex $v$ is the number of distinct edges incident to $v$. It is denoted by $\operatorname{deg} v$ where
$$
\begin{aligned}
\operatorname{deg} v &=\mid{e \in \mathrm{E}: e=v x \text { for some } x \in \mathrm{V}} \mid \
&=|{x \in \mathrm{V}: v x \in \mathrm{E}}|
\end{aligned}
$$
A vertex of degree 0 is called an isolated vertex.
Theorem 9.1 Let $G=(V, E)$ be a graph then
$$
\Sigma_{v \in \mathrm{v}} \operatorname{deg} v=2|\mathrm{E}| .
$$
Proof This result is clear since each edge contributes one to each of the vertex degrees. The formal proof is by induction based on the number of edges in the graph, and the basis case is for a graph with no edges (i.e. where every vertex is isolated), and the result is immediate for this case.

The inductive step (strong induction) is to assume that the result is true for all graphs with $k$ or fewer edges. We then consider a graph $\mathrm{G}=(\mathrm{V}, \mathrm{E})$ with $k+1$ edges.
Choose an edge $e=x y \in \mathrm{E}$ and consider the graph $\mathrm{G}^{\prime}=\left(\mathrm{V}, \mathrm{E}^{\prime}\right)$ where $\mathrm{E}^{\prime}=\mathrm{E} \backslash$ ${e}$. Then, $\mathrm{G}^{\prime}$ is a graph with $k$ edges and therefore letting deg’ $v$ represent the degree of a vertex in $\mathrm{G}^{\prime}$ we have
$$
\Sigma_{v \in V}{ }^{\circ}{ }^{\prime} v=2\left|E^{\prime}\right|=2(|E|-1)=2|E|-2
$$
The degree of $x$ and $y$ are one less in $\mathrm{G}^{\prime}$ than they are in $\mathrm{G}$. That is,
$$
\begin{aligned}
& \Sigma_{v \in \mathrm{V}}^{\circ} v-2=S_{v \in \mathrm{V}}^{\circ \prime} v=2|E|-2 \
\Rightarrow & \Sigma_{v \in \mathrm{V}}{ }^{\circ} v=2|E|
\end{aligned}
$$
A graph $\mathrm{G}=(V, E)$ is said to be complete if all the vertices are adjacent: i.e. $\mathrm{E}=\mathrm{V} \times \mathrm{V}$. A graph $\mathrm{G}=(V, E)$ is said to be simple graph if each edge connects two different vertices, and no two edges connect the same pair of vertices. Similarly, a graph that may have multiple edges between two vertices is termed a multigraph.

有向图（图 9.4）是一对有限集（V，E），其中 E 是 V 上的二元关系（可能不对称）。有向无环图（dag）是没有环的有向图.下面的示例是具有三个边和四个顶点的有向图。

一条边 $e \in \mathrm{E}$ 由一对 $\langle x, y\rangle$ 组成，其中 $x, y$ 是图中的相邻节点。 $x$ 的度数是与 $x$ 相邻的节点数。边集记为$\mathrm{E}(\mathrm{G})$，顶点集记为$\mathrm{V}(\mathrm{G})$。

加权图是一个图 $\mathrm{G}=(\mathrm{V}, \mathrm{E})$ 和一个加权函数 $w: \mathrm{E} \rightarrow \mathbb{N}$，将权重与图中的每条边相关联。在对计算机网络建模时可以使用加权函数：例如，可以应用边的权重来对两个节点之间的电信链路的带宽进行建模。加权函数的另一个应用是确定图中两个节点之间的距离（或最短路径）（存在这样的路径）。

对于有向图，边在两个方向上的权重相同：即$w\left(v_{i}, v_{j}\right)=w\left(v_{j}, v_{i}\右）$ 对于图中 $\mathrm{G}$ 中的所有边 $$，而有向图的权重可能不同。

如果 $xy \in \mathrm{E}$ 两个顶点 $x, y$ 是相邻的，并且 $x$ 和 $y$ 被认为是与边 $xy 相关的。$ 可以使用矩阵来表示邻接关系。
150
9 图论
例 9.1 考虑图 $\mathrm{G}=(\mathrm{V}, \mathrm{E})$ 其中 $\mathrm{E}={u=ab, v=cd, w=fg,$, $x=bg, y=af}$。

可以使用邻接矩阵（图 9.5）来表示图中的邻接关系。它的构造包括列出行和列中的顶点，如果两个顶点相邻，则表中的条目为 1，否则为 0。

类似地，我们可以通过构造关联矩阵来构造一个描述边和顶点关联的表（图 9.6）。该矩阵列出了行和列中的顶点和边，如果顶点是边的节点之一，则输入 1，否则输入 0。

两个图 $\mathrm{G}=(\mathrm{V}, \mathrm{E})$ 和 $\mathrm{G}^{\prime}=\left(\mathrm{V}^{\prime}， \mathrm{E}^{\prime}\right)$ 被称为同构如果存在一个双射 $f: \mathrm{V} \rightarrow \mathrm{V}^{\prime}$ 使得对于任何 $ u, v \in \mathrm{V}, uv \in \mathrm{E}, f(u) f(v) \in \mathrm{E}^{\prime}$。映射 $f$ 称为同构。除了重新标记节点和边之外，两个同构的图基本上是等价的。

令 $\mathrm{G}=(\mathrm{V}, \mathrm{E})$ 和 $\mathrm{G}^{\prime}=\left(\mathrm{V}^{\prime}, \ mathrm{E}^{\prime}\right)$ 是两个图，则 $\mathrm{G}^{\prime}$ 是 $\mathrm{G}$ 的子图，如果 $\mathrm{V}^{\ prime} \subseteq \mathrm{V}$ 和 $\mathrm{E}^{\prime} \subseteq \mathrm{E}$。给定 $\mathrm{G}=(\mathrm{V}, \mathrm{E})$ 和 $\mathrm{V}^{\prime} \subseteq \mathrm{V}$ 那么我们可以归纳出一个子图 $\ mathrm{G}$ $^{\prime}=\left(\mathrm{V}^{\prime}, \mathrm{E}^{\prime}\right)$ 通过将 $\mathrm{G}$ 限制为$\mathrm{V}^{\prime}$（记为 $\left.\mathrm{G}\left|\mathrm{V}^{\prime}\right|\right）$。 $\mathrm{E}^{\prime}$ 中的边集定义为
$$
\mathrm{E}^{\prime}=\left{e \in \mathrm{E}: e=uv \text { and } u, v \in \mathrm{V}^{\prime}\right\ }
$$
顶点 $v$ 的度数是与 $v$ 相关的不同边的数量。它由 $\operatorname{deg} v$ 表示，其中
$$
\开始{对齐}
\operatorname{deg} v &=\mid{e \in \mathrm{E}: e=v x \text { for some } x \in \mathrm{V}} \mid \
&=|{x \in \mathrm{V}: v x \in \mathrm{E}}|
\end{对齐}
$$
度数为 0 的顶点称为孤立顶点。
定理 9.1 令 $G=(V, E)$ 为图，则
$$
\Sigma_{v \in \mathrm{v}} \operatorname{deg} v=2|\mathrm{E}| .
$$
证明这个结果很清楚，因为每条边对每个顶点度数贡献一个。正式证明是基于图中边数的归纳，基本情况是针对没有边的图（即每个顶点都是孤立的），这种情况下的结果是立即的。

归纳步骤（强归纳）是假设结果对于所有具有 $k$ 或更少边的图都是正确的。然后我们考虑一个图 $\mathrm{G}=(\mathrm{V}, \mathrm{E})$ 与 $k+1$ 个边。
选择一条边 $e=xy \in \mathrm{E}$ 并考虑图 $\mathrm{G}^{\prime}=\left(\mathrm{V}, \mathrm{E}^{\prime} \right)$ 其中 $\mathrm{E}^{\prime}=\mathrm{E} \backslash$ ${e}$。那么，$\mathrm{G}^{\prime}$ 是一个有 $k$ 个边的图，因此让 deg’ $v$ 表示 $\mathrm{G}^{\prime}$ 中一个顶点的度数有
$$
\Sigma_{v \in V}{ }^{\circ}{ }^{\prime} v=2\left|E^{\prime}\right|=2(|E|-1)=2|E |-2
$$
$x$ 和 $y$ 在 $\mathrm{G}^{\prime}$ 中的度数比它们在 $\mathrm{G}$ 中的度数小一。我

图论代考

自然数 $\mathbb{N}$ 由数字 $\{1,2,3, \ldots\}$ 组成。整数 $\mathbb{Z}$ 由 $\{\ldots-2,-1,0,1,2, \ldots\}$ 组成。有理数 $\mathbb{Q}$ 由 $\left\{{ }^{p} /_{q}\right.$ 形式的所有数字组成，其中 $p$ 和 $q$ 是整数，$ \left.q \neq 0\right\}$。实数 $\mathbb{R}$ 被定义为有理数收敛序列的集合，它们是有理数的超集。它们包含有理数和无理数。复数 $\mathbb{C}$ 由 $\{a+bi$ 形式的所有数字组成，其中 $a, b \in \mathbb{R}$ 和 $i=\sqrt{-} 1\}美元。毕达哥拉斯三元组（图 3.2）是满足毕达哥拉斯方程 $x^{2}+y^{2}=z^{2}$ 的三个整数的组合。有无数个这样的三元组，这种三元组的一个例子是 $3,4,5$，因为 $3^{2}+4^{2}=5^{2}$。毕达哥拉斯学派发现了音乐和数字之间的数学关系，他们的哲学是数字隐藏在从音乐到科学和自然的一切事物中。这导致了他们的哲学，即“一切都是数字”。

数学代写| DISCRETE MATHEMATICS代考请认准UprivateTA™. UprivateTA™为您的留学生涯保驾护航。

Cryptosystem
A system that describes how to encrypt or decrypt messages
Plaintext
Message in its original form
Ciphertext
Message in its encrypted form
Cryptographer
Invents encryption algorithms
Cryptanalyst
Breaks encryption algorithms or implementations

编码理论代写

编码理论（英语：Coding theory）是研究编码的性质以及它们在具体应用中的性能的理论。编码用于数据压缩、加密、纠错，最近也用于网络编码中。不同学科（如信息论、电机工程学、数学、语言学以及计算机科学）都研究编码是为了设计出高效、可靠的数据传输方法。这通常需要去除冗余并校正（或检测）数据传输中的错误。

编码共分四类：^[1]