圖論及其應(yīng)用：第二次作業(yè)
1.題一 某醫(yī)院急診某夜有 169 名病人需要輸血，假設(shè)每人需要 1 個(gè)單位的血量，對(duì) A, B, O, AB
四種血型的需求分別是 39, 38, 42, 50 單位，醫(yī)院共有 170 單位的儲(chǔ)備，對(duì)應(yīng) A, B, O, AB 分別為
46, 34, 45, 45 單位。
（1）請(qǐng)用最大流模型求解最多可以滿足多少病人；
（2）找出一個(gè)容量小于 169 的割，并向精通醫(yī)學(xué)然而并不十分精通圖論的醫(yī)院工作人員用他們可
以理解的方式解釋為什么不能滿足所有病人。

題二 已知圖中任何兩條邊的權(quán)值不相等，證明以下兩個(gè)結(jié)論成立：

? 任何割中的最短的邊在所有的最小生成樹中；

? 任何圈中的最長(zhǎng)邊不在任何一棵最小生成樹中。

證明：

• （反證法）設(shè)一個(gè)割把圖G分為（S,T）,邊（u，v)是這個(gè)割中最短的邊且$u\in S,v\in T$，假設(shè)該邊不在G的一棵最小生成樹中,由生成樹的定義可得，必定存在一點(diǎn)$w\in S$,（w,v)在生成樹上且（w,v)比(u,v)短，與條件"(u,v)是該割中最短的邊矛盾"，所以邊(u,v),在該生成樹上。
• （反證法）由樹的定義（無圈連通圖）可知，任何圈都至少會(huì)被刪去一條邊，假設(shè)生成樹$T$包含了一條最長(zhǎng)的邊。將這條最長(zhǎng)邊除去，同時(shí)添加另一條之前被刪去的邊，則所得的生成樹的權(quán)值和更小，矛盾。

題三 給定任一有偶數(shù)條邊且每個(gè)頂點(diǎn)度數(shù)為偶數(shù)的連通圖 G，證明可以把每條邊染成黑白兩種顏色中的一種，對(duì)每個(gè)頂點(diǎn)，與之相連的黑邊與白邊一樣多。

因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$G$的頂點(diǎn)個(gè)數(shù)都是偶數(shù)，所以存在歐拉回路。從一個(gè)起點(diǎn)出發(fā)走這個(gè)歐拉回路，在這個(gè)過程中交替將邊染成黑色和白色，因?yàn)檫厰?shù)是偶數(shù)，所以起點(diǎn)發(fā)出的邊和終點(diǎn)發(fā)出的邊顏色一定相反。所以對(duì)起點(diǎn)來說黑色邊和白色邊一樣多，由于任意頂點(diǎn)都可以作為起點(diǎn)和終點(diǎn)，所以對(duì)每個(gè)頂點(diǎn)，與之相連的黑邊和白邊是一樣多的。

題四 G = (V, E) 為簡(jiǎn)單 Euler 圖，證明或推翻以下推斷：

1. 若 G 是偶圖，則 m = |E| 為偶數(shù)；

將偶圖$G$分為兩個(gè)部分$S$和$T$,由偶圖的定義可知，$S$和$T$內(nèi)部的節(jié)點(diǎn)都沒有直接相連的邊，從一個(gè)節(jié)點(diǎn)出發(fā)走歐拉回路，假如從$S$的一個(gè)頂點(diǎn)出發(fā)，則下一步一定是走到$T$的一個(gè)頂點(diǎn)，再下一步又是走回$S$的一個(gè)頂點(diǎn)，一次類推，則所形成的的歐拉回路一定是由從$S$到$T$的邊和從$T$到$S$的邊交替形成的回路,并最終回到起點(diǎn)。因此所以$m$為偶數(shù)。

? 若 n = |V | 是偶數(shù)，則 m 也是偶數(shù)；

假命題。

如下圖，該圖有歐拉回路$ABCDEFDA$, 并且有6個(gè)頂點(diǎn)(偶數(shù)個(gè))但有7條邊（奇數(shù)條）。

? e 與 f 為關(guān)聯(lián)的兩條邊，他們必然連續(xù)出現(xiàn)在某條 Euler 回路里。

假命題。

在下圖中，$AD$和$CD$相關(guān)聯(lián)，但他們?cè)谌我鈿W拉回路中都不連續(xù)出現(xiàn)。

題五 給定每邊長(zhǎng)度為一的連通偶圖 G 以及頂點(diǎn) v ∈ V (G)，證明對(duì) G 中所有的邊 xy ∈ E(G)， v到 x 的最短路不可能和 v 到 y 的最短路一樣長(zhǎng)。

有偶圖的定義可知，可將圖$G$分為兩個(gè)部分$S$和$T$,$S$和$T$的內(nèi)部節(jié)點(diǎn)沒有直接相連的邊，對(duì)于任意邊$xy$,不妨設(shè)$x\in S,y\in T,V\in S$ ，由于偶圖中的路徑一定是交替從$S$到$T$和從$T$到$S$的，所以$vx$的長(zhǎng)度一定是偶數(shù)，$vy$的長(zhǎng)度一定是奇數(shù)，所以 v到 x 的最短路不可能和 v 到 y 的最短路一樣長(zhǎng)。

題六 證明 Peterson 圖不是 H 圖。

彼得森圖中沒有長(zhǎng)度為 3 或者 4 的回路。假設(shè)彼得森圖存在哈密頓回路，則哈密頓回路包含 10 條邊，而彼得森圖中剩余的 5 條邊分別連接該哈密頓回路中不相鄰的點(diǎn)。因?yàn)楸说蒙瓐D的圖中每個(gè)點(diǎn)的度數(shù)為 3，所以該哈密頓回路的每個(gè)點(diǎn)均管理一條剩余邊。每一條剩余邊的兩個(gè)端點(diǎn)的距離至少為 4，否則出現(xiàn)長(zhǎng)度為 3 或者4 的回路。并且至少存在一條剩余邊 e，它的兩個(gè)端點(diǎn)在哈密頓回路中距離為 4，否則 5 條剩余邊的端點(diǎn)距離均為 5，則出現(xiàn)長(zhǎng)度為4 的回路。設(shè)v是哈密頓回路中與e的一個(gè)端點(diǎn)距離為5 的點(diǎn)，則由v關(guān)聯(lián)的剩余邊和e可以找到長(zhǎng)度為3或者4的回路， 矛盾。

題七 對(duì) n ≥ 4，如果 n 階完全圖 Kn 可以被劃分成邊不交的長(zhǎng)度為 4 的圈，證明 n = 1 mod 8。

$n$階完全圖的邊數(shù)$|E|=\frac{n(n?1)}{2}$ ,假設(shè)該圖可以劃分為$k$個(gè)邊不交的長(zhǎng)度為4的圈，則有$E=4K$，所以有$\frac{n(n?1)}{2}=4k$ ,且該圖為歐拉圖，因此每個(gè)頂點(diǎn)的對(duì)數(shù)均為偶數(shù)，所以有$(n?1)mod2=0$ ,所以$n$為奇數(shù)，且$\frac{n(n?1)}{8}=k$ ,所以 $(n?1)mod8=0$ 所以$n=1mod8$ 。

題八 給定一棵樹 T 以及 T 的 k 棵子樹 $T_1,T_2,???,T_k$，已知這 k 棵子樹兩兩均有公共頂點(diǎn)，即對(duì)任意$ 1 ≤ i < j ≤ k$ 有 $V(T_i)\cap V(T_j)=?$，證明 $V (T_1) \cap V (T_2) \cap \dots \cap V (T_k) \neq \varnothing $。

反證法。若$V(T_1)\cap V(T_2)\cap ?\cap V(T_i)=?$，設(shè)$V(T_1)\cap V(T_2)\cap ?\cap V(T_{i?1})=S$，則$T_i$中一定不包含$S$中的頂點(diǎn)，因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$T$是一棵樹，所以$T?S$剩下的圖中至少有一個(gè)連通分支，且$T_i$只能位于其中一個(gè)連通分支中，設(shè)$x$表示$T$所在的連通分支中與S直接連接的那個(gè)點(diǎn)且$x\in /S$，因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$T_j\cap T_i=?,i=1,2,3..i?1$，令$T_j\cap T_i=M_j$，則每個(gè)$M_j$一定包含頂點(diǎn)$x$，否則這些子樹無法既與$T_i$有公共節(jié)點(diǎn)又包含$S$，因此與$x\in /S$產(chǎn)生矛盾。

因此當(dāng)$V(T_1)\cap V(T_2)\cap ?\cap V(T_{i?1})=?$時(shí)，有$V(T_1)\cap V(T_2)\cap ?\cap V(T_i)=?$，且$V(T_1)\cap V(T_2)=?$，那么不斷添加子樹即可得到$V (T_1) \cap V (T_2) \cap \dots \cap V (T_k) \neq \varnothing $ 。

題九 、$C$ 為簡(jiǎn)單圖 $G$ 的一個(gè)點(diǎn)不重復(fù)的圈，已知有一條長(zhǎng)度為 $k$ 的路 $P$ 連接 $C$ 上的兩個(gè)頂點(diǎn) $x$ 與 $y$，證明$G$ 包含一條長(zhǎng)度至少為 $\sqrt{2k}$ 的點(diǎn)不重復(fù)的圈 。

總結(jié)

以上是生活随笔為你收集整理的图论及其应用：第二次作业的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。