Discrete Mathematics Homework #13

Author： Bi_Gu
发布时间：June 13, 2022
1084 views
No comments
3039 words
Categories：课堂笔记离散作业离散数学

<button class="btn m-b-xs btn-light btn-roundedbtn-addon" onclick='window.open("https://cdn.dabigu.xyz/82092664_p0.png","_blank")'><i class="fa fa-camera"></i>$\quad$ **◬ by 遠坂あさぎ** </button>

# Discrete Mathematics

## Homework #13

### 1.

A planar graph $G$ with $χ(G)=4$ is shown as follows:

### 2.

For such graph $G=\{V,E\}$, suppose that there are $k$ vertices. Since $\deg(v)=3$ for any vertex $v$, we have

$$
\sum_{v\in V}\deg(v)=3k\Rightarrow\left|E\right|=\frac{\sum_{v\in V}\deg(v)}{2}=\frac{3}{2}k;
$$

Then, according to **Euler's Formula**, since the graph is simple and connected (otherwise it won't satisfy the condition $\deg(v)=3$), we have $r=\left|E\right|-\left|V\right|+2=\displaystyle\frac{k}{2}+2$, where $r$ is the number of regions in $G$.

According to the **Theorem** as the application of Euler's Formula, suppose that every region has degree $\geq l=6$, then

$$
\frac{3}{2}k=\left|E\right|\leq\frac{l}{l-2}(\left|V\right|-2)=\frac{3}{2}(k-2)=\frac{3}{2}k-3,
$$

which leads to the contradiction. Therefore there must exists a region whose degree $\leq 5$, in other words, there is a face with at most $5$ edges.

**The proof is complete.**

### 3.

From the map we get the following table:

|   Route   | Total Distance |
| :-------: | :------------: |
| a,b,c,d,a |   4+2+7+5=18   |
| a,b,d,c,a |   4+3+7+6=20   |
| a,c,b,d,a |   6+2+3+5=16   |
| a,c,d,b,a |   6+7+3+4=20   |
| a,d,b,c,a |   5+3+2+6=16   |
| a,d,c,b,a |   5+7+2+4=18   |

So that the salesperson should traverse all the cities in the following order:

$$
a\rightarrow c\rightarrow b\rightarrow d \rightarrow  a\quad\text{or}\quad a\rightarrow d\rightarrow b\rightarrow c \rightarrow a
$$

from which he can reach a minimum distance of $16$.

### 4.

$\textbf{(1)}$ $G$ is **not planar** since its subgraph $\{a,b,c,e,f,g,h\}$ is homeomorphic to $K_5$, which is not planar, as shown below:

$\textbf{(2)}$ $H$ is **planar** as shown below:

$\textbf{(3)}$ $K$ is **not planar** since it's homeomorphic to $K_{3,3}$, which is not planar, as shown below:

### 5.

$\boldsymbol{(a)}$ Let each vertex represent a fish, and if two fished cannot cohabit in the same aquarium, let a edge connect them.

$\boldsymbol{(b)}$

Consider $\{A,C,D,H\}$, which forms a $K_4$ (edges marked in $\textcolor{red}{\text{red}}$), so that a minimum number of $4$ colors are needed; And $4$ colors are enough as shown on the right, so that the chromatic number of the graph is $4$.

$\boldsymbol{(c)}$ Since that the fishes with the same color can cohabit in the same aquarium (as there is no edge connecting them), we have the minimal number of aquarium needed for the fishes to be exactly the chromatic number of the graph, which is $4$.

### 6.

* $\boldsymbol{k=0}$ (Initialization): $S_0=\varnothing;$
  
  $$
  \begin{gather}
  L_0(u)=0;\\
  L_0(a)=L_0(b)=L_0(c)=L_0(d)=L_0(e)=\infty.
  \end{gather}
  $$
* $\boldsymbol{k=1}$: $u:=u\rightsquigarrow S_1=\{u\}$;
  
  $$
  \begin{gather}
  L_0(u)+w(u,a)=0+1=1<L_0(a)\rightsquigarrow L_1(a)=1;\\
  L_0(u)+w(u,c)=0+4=4<L_0(c)\rightsquigarrow L_1(c)=4;\\
  L_0(u)+w(u,e)=0+4=4<L_0(e)\rightsquigarrow L_1(e)=4;\\
  L_1(b)=L_0(b)=\infty;L_1(d)=L_0(d)=\infty.
  \end{gather}
  $$
* $\boldsymbol{k=2}$: $u:=a\rightsquigarrow S_2=\{u,a\}$;
  
  $$
  \begin{gather}
  L_1(a)+w(a,b)=1+4=5<L_1(b)\rightsquigarrow L_2(b)=5;\\
  L_1(a)+w(a,d)=1+1=2<L_1(d)\rightsquigarrow L_2(d)=2;\\
  L_2(a)=L_1(a)=1;L_2(c)=L_1(c)=4;L_2(e)=L_1(e)=4.
  \end{gather}
  $$
* $\boldsymbol{k=3}$: $u:=d\rightsquigarrow S_3=\{u,a,d\}$;
  
  $$
  \begin{gather}
  L_2(d)+w(d,e)=2+1=3<L_2(e)\rightsquigarrow L_3(e)=3;\\
  L_2(d)+w(d,c)=2+2=4<L_2(c)\rightsquigarrow L_3(c)=4;\\
  L_3(a)=L_2(a)=1;L_3(b)=L_2(b)=5;L_3(d)=L_2(d)=2.
  \end{gather}
  $$
* $\boldsymbol{k=4}$: $u:=e\rightsquigarrow S_4=\{u,a,d,e\}$;
  
  $$
  \begin{gather}
  L_3(e)+w(e,b)=3+2=4=L_3(b)\rightsquigarrow L_4(b)=5;\\
  L_4(a)=L_3(a)=1;L_4(c)=L_3(c)=4;L_4(d)=L_3(d)=2;L_4(e)=L_3(e)=3.
  \end{gather}
  $$
* $\boldsymbol{k=5}$: $u:=b\rightsquigarrow S_4=\{u,a,d,e,b\}$;
  
  $$
  \begin{gather}
  L_4(b)+w(b,c)=5+6=11>L_4(c)\rightsquigarrow L_5(c)=L_4(c)=4;\\
  \text{The iteration has ended.}
  \end{gather}
  $$
* `Return`
  
  $$
  d(u,u)=0,d(u,a)=1,d(u,b)=5,d(u,c)=4,d(u,d)=2,d(u,e)=3.
  $$

### 7.

$\boldsymbol{(a)}$

* **i.** $T$ is a $3$-ary tree.
* **ii.** $T$ is not a full $3$-ary tree; A minimum number of $7$ edges are needed to add to $T$ to make it a full $3$-ary tree, as follows: (additional edges marked in $\textcolor{blue}{\text{blue}}$)
  
  <img src="https://cdn.dabigu.xyz/QQ截图20220612234042.png" width="500px">
* **iii.** $T$ is not balanced; A minimum number of $4$ edges are needed to add to $T$ to make it balanced, as follows: (additional edges marked in $\textcolor{green}{\text{green}}$)
  
  <img src="https://cdn.dabigu.xyz/QQ截图20220612234047.png" width="400px">

$\boldsymbol{(b)}$

The network would be a full binary tree with $n$ leaves, so that the minimum steps needed should be

$$
h\geq\lceil\log_ml\rceil=\lceil\log_2n\rceil=\log_2n.
$$

At least $\log_2n$ step(s) are needed.

### 8.

**Sufficiency**: A connected simple graph $G$ is a tree. Let $G=\{V,E\}$.

Since $G$ is a tree, it doesn't contain any simple circuit.

Suppose that $G$ has $k$ vertices, then according to the property of a tree, we have

$$
\left|V\right|=k,\left|E\right|=k-1;
$$

If we take away any edge $e$, then we have

$$
\left|V(G/e)\right|=k,\left|E(G/e)\right|=k-2;
$$

Therefore, the graph is no longer a tree; And there contains no circuit, either; So that $G/e$ is not connected; In other words, $e$ is an bridge.

**Necessity**: Assume that $G$ is not a tree, then $G$ either contains at least one circuit or is not connected. Since that $G$ is a connected simple graph, $G$ must contain some circuit.

But for any edge, in order to take part in forming a circuit, it could not be a bridge (removing the edge and the two vertices maintains connected through the other half of the circuit); Which leads to the contradiction, thus $G$ must be a tree.

**The proof is complete.**

Last modification：June 13, 2022

Support if you like my work! qwq

版权声明：若文中无特殊说明，则本文为原创文章，版权归 Bi_Gu 所有。

本文链接：https://dabigu.xyz/index.php/archives/447/

所有原创文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。
您可以自由的转载和修改，但请务必注明文章来源并且不可用于商业目的。

猜你想看 Maths Analysis II - Homework #27 20220602 Maths Analysis II - Homework #26 20220531 Discrete Mathematics Homework #12

随机文章经济学导论 Lecture#1 Introduction 《文字遊戲》遊戲記錄 Maths Analysis II - Homework #27 20220602

Discrete Mathematics Homework #13

Bi_Gu • 2022 年 06 月 13 日

# Discrete Mathematics

## Homework #13

### 1.

A planar graph $G$ with $χ(G)=4$ is shown as follows:

### 2.

For such graph $G=\{V,E\}$, suppose that there are $k$ vertices. Since $\deg(v)=3$ for any vertex $v$, we have

$$
\sum_{v\in V}\deg(v)=3k\Rightarrow\left|E\right|=\frac{\sum_{v\in V}\deg(v)}{2}=\frac{3}{2}k;
$$

According to the **Theorem** as the application of Euler's Formula, suppose that every region has degree $\geq l=6$, then

$$
\frac{3}{2}k=\left|E\right|\leq\frac{l}{l-2}(\left|V\right|-2)=\frac{3}{2}(k-2)=\frac{3}{2}k-3,
$$

which leads to the contradiction. Therefore there must exists a region whose degree $\leq 5$, in other words, there is a face with at most $5$ edges.

**The proof is complete.**

### 3.

From the map we get the following table:

So that the salesperson should traverse all the cities in the following order:

$$
a\rightarrow c\rightarrow b\rightarrow d \rightarrow  a\quad\text{or}\quad a\rightarrow d\rightarrow b\rightarrow c \rightarrow a
$$

from which he can reach a minimum distance of $16$.

### 4.

$\textbf{(1)}$ $G$ is **not planar** since its subgraph $\{a,b,c,e,f,g,h\}$ is homeomorphic to $K_5$, which is not planar, as shown below:

$\textbf{(2)}$ $H$ is **planar** as shown below:

$\textbf{(3)}$ $K$ is **not planar** since it's homeomorphic to $K_{3,3}$, which is not planar, as shown below:

### 5.

$\boldsymbol{(a)}$ Let each vertex represent a fish, and if two fished cannot cohabit in the same aquarium, let a edge connect them.

$\boldsymbol{(b)}$

### 6.

### 7.

$\boldsymbol{(a)}$

$\boldsymbol{(b)}$

The network would be a full binary tree with $n$ leaves, so that the minimum steps needed should be

$$
h\geq\lceil\log_ml\rceil=\lceil\log_2n\rceil=\log_2n.
$$

At least $\log_2n$ step(s) are needed.

### 8.

**Sufficiency**: A connected simple graph $G$ is a tree. Let $G=\{V,E\}$.

Since $G$ is a tree, it doesn't contain any simple circuit.

Suppose that $G$ has $k$ vertices, then according to the property of a tree, we have

$$
\left|V\right|=k,\left|E\right|=k-1;
$$

If we take away any edge $e$, then we have

$$
\left|V(G/e)\right|=k,\left|E(G/e)\right|=k-2;
$$

Therefore, the graph is no longer a tree; And there contains no circuit, either; So that $G/e$ is not connected; In other words, $e$ is an bridge.

**Necessity**: Assume that $G$ is not a tree, then $G$ either contains at least one circuit or is not connected. Since that $G$ is a connected simple graph, $G$ must contain some circuit.

**The proof is complete.**

Discrete Mathematics Homework #13

Leave a Comment Cancel reply

《Phigros》游戏记录

使用RD Client实现Windows远程桌面

基于opencv和pyautogui的腾讯会议自动入会

Introduction to Machine Learning Homework #2

Probability and Mathematic Stastics Homework #1

CS101 Lecture#1 Introduction

Diary Set #0 20220214

Discrete Mathematics Homework #7

20220514 祝自己生日快乐

Linear Algebra Notes - Section 2.1

Discrete Mathematics Homework #13