19th Ave New York, NY 95822, USA

# 数学代写代考| Graph Colouring and Four-Colour Problem 离散数学

## 数学代写| Graph Colouring and Four-Colour Problem 代考

my-assignmentexpert愿做同学们坚强的后盾，助同学们顺利完成学业，同学们如果在学业上遇到任何问题，请联系my-assignmentexpert™，我们随时为您服务！

## 离散数学代写

It is very common for maps to be coloured in such a way that neighbouring states or countries are coloured differently. This allows different states or countries to be easily distinguished as well as the borders between them. The question naturally arises as to how many colours are needed (or determining the least number of colours needed) to colour the entire map, as it might be expected that a large number of colours would be needed to colour a large complicated map.

However, it may come as a surprise that in fact very few colours are required to colour any map. A former student of the British logician, Augustus De Morgan, had noticed this in the mid-1800s, and he proposed the conjecture of the four-colour theorem. There were various attempts to prove that 4 colours were sufficient from the mid-1800s onwards, and it remained a famous unsolved problem in mathematics until the late twentieth century.

Kempe gave an erroneous proof of the four-colour problem in 1879 , but his attempt led to the proof that five colours are sufficient (which was proved by Heawod in the late 1800 s). Appel and Haken of the University of Illinois finally provided the proof that 4 colours are sufficient in the mid-1970s (using over $1000 \mathrm{~h}$ of computer time in their proof).

Each map in the plane can be represented by a graph, with each region of the graph represented by a vertex. Edges connect two vertices if the regions have a common border. The colouring of a graph is the assignment of a colour to each vertex of the graph so that no two adjacent vertices in this graph have the same colour.
Definition
Let $\mathrm{G}=(\mathrm{V}, \mathrm{E})$ be a graph and let $\mathrm{C}$ be a finite set called the colours. Then, a colouring of $\mathrm{G}$ is a mapping $\kappa: \mathrm{V} \rightarrow \mathrm{C}$ such that if $u v \in \mathrm{E}$ then $\kappa(u) \neq \kappa(v)$.
That is, the colouring of a simple graph is the assignment of a colour to each vertex of the graph such that if two vertices are adjacent then they are assigned a different colour. The chromatic number of a graph is the least number of colours needed for a colouring of the graph. It is denoted by $\chi(G)$.

Example 9.2 Show that the chromatic colour of the following graph $G($ Fig. $9.9)$ is 3 (this example is adapted from [2]).
Solution
The chromatic colour of $\mathrm{G}$ must be at least 3 since vertices $p, q$ and $r$ must have different colours, and so we need to show that 3 colours are in fact sufficient to colour G. We assign the colours red, blue and green to $p, q$ and $r$ respectively. We immediately deduce that the colour of $s$ must be red (as adjacent to $q$ and $r$ ). From this, we deduce that $t$ is coloured green (as adjacent to $q$ and $s$ ) and $u$ is coloured blue (as adjacent to $s$ and $t$ ). Finally, $v$ must be coloured red (as adjacent to $u$ and $t$ ). This leads to the colouring of the graph $\mathrm{G}$ in Fig. 9.10.

Theorem $9.8$ (Four-Colour Theorem) The chromatic number of a planar graph $G$ is less than or equal to 4 .

Kempe 在 1879 年对四色问题给出了一个错误的证明，但他的尝试导致了五色足够的证明（Heawod 在 1800 年代后期证明了这一点）。伊利诺伊大学的 Appel 和 Haken 最终证明了 1970 年代中期 4 种颜色就足够了（在他们的证明中使用了超过 1000 美元的计算机时间）。

$\mathrm{G}$ 的颜色必须至少为 3，因为顶点 $p、q$ 和 $r$ 必须具有不同的颜色，因此我们需要证明 3 种颜色实际上足以为 G 着色。我们将红色、蓝色和绿色分别分配给 $p、q$ 和 $r$。我们立即推断出 $s$ 的颜色必须是红色（与 $q$ 和 $r$ 相邻）。由此，我们推断 $t$ 为绿色（与 $q$ 和 $s$ 相邻），$u$ 为蓝色（与 $s$ 和 $t$ 相邻）。最后，$v$ 必须为红色（与 $u$ 和 $t$ 相邻）。这导致图 $\mathrm{G}$ 在图 9.10 中着色。

## 密码学代考

• 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

## 编码理论代写

1. 数据压缩（或信源编码
2. 前向错误更正（或信道编码
3. 加密编码
4. 线路码