# 清大 107 軟體
###### tags: `NTHU` `107` `軟體`

1. (a) 120 (b) 1224
2. (a) 2 (b) 3
3.
所有的排列，可分成以下幾種情形
所有人都在自己的位置上的方法數: $\binom{n}{0}d_0$
有一個不在自己的位置上的方法數: $\binom{n}{1}d_1$
有二個不在自己的位置上的方法數: $\binom{n}{2}d_2$
以此類推，加總即為所有排列的總數。
4.
(a)
reflexive: a - a = 0 => $(a,a)\in R$
antisymmetric:
$(a,b)\in R$ && $(b, a)\in R$ => $a - b\ge 0$ && $b-a\ge 0$ => $a = b$
transitive: $(a,b)\in R$ && $(b,c)\in R$ => $a-b=2k_1$,$b-c=2k_2$ => $a-c=2k_1+2k_2$ => $(a,c)\in R$
(b)
如果 a-b 為奇數，則 (a,b) 和 (b,a) 皆不屬於 R。

5. FTFTFF
6. (a) 這三小？？？(b) 畫出來會是 $K_4$
7.
(a)

        10
       /  \
      20   15
       \   /
       25 30

(b)

              10
         65         70 
      45    15    20 15
    50 60  40 35

\(c\)

               X
      10              70
  15      30      60      40
20  25  30  35

(d)

              8
      9              10
  12      50     15
20  18  80

(e)

            30|40
20|25|_     35|36|37     45

(f) ...

8.
(a)
建立一個點 v，跟其它所有的點連接。若此圖存在 HC，則該 HC 必為此形式：
$<....,v_i,v,v_j,....>$
將 v 拿掉，就會是以 $v_i$ $v_j$ 為端點的 HP
反過來講，如果原圖存在 HP，則 v 可與該 HP 的兩端點連接，成為一個 HC。
(b)
在 G 中隨機挑選一個點 v，複製出另一個點 v'，v' 與所有與 v 連接的點相連。再建立額外兩個點 s, t，分別與 v, v' 連接。另此圖為 G'。

若 G 存在 HC:
$<...v_i,v,v_j,...>$
在 G' 中，將 $v_i$ 改連到 v'，即可得到一個 HP:
$<s,v,v_j....v_i,v',t>$

反過來講，若 G' 中存在一個 HP，則該 HP 必為以 s,t 為端點:
$<s,v,v_i....v_j,v',t>$
將 s,t 拿掉，將 $v_j$ 改連到 $v$，得一 HC:
$<v,v_i,...,v_j,v>$