\documentclass[a4j]{jarticle}

\newcommand{\Q}{\small}

\title{ $B%"%k%4%j%:%`@_7W!&2r@OFCO@(B $BBh(B$4$$B2s%l%]!<%H(B }
\author{ 600P031-4 $B9bLZM42p(B }
\date{ $BDs=PF|(B 2000-06-27 }

\begin{document}
\maketitle

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{ 7.12
{\Q $G = (V, E)$ $B$r40A4%0%i%U$H$9$k!#(B
$B$9$J$o$A$I$N(B $2$$BD:E@$N4V$K$bJU$,$"$k$h$&$J%0%i%U$H$9$k!#(B
$E$ $B$N3FJU$KG$0U$NJ}8~$r;XDj$7$F$G$-$k(B $E'$ $B$K$h$C$F!"(B
$BM-8~%0%i%U(B $G' = (V, E')$ $B$r:n$k!#(B
$G'$ $B$K$O$9$Y$F$ND:E@$r$A$g$&$I(B $1$$B2s$:$DDL$kM-8~O)$,$"$k$3$H$r<($;!#(B}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

$n$ $B$K$D$$$F$N?t3XE*5"G<K!$K$h$C$F!"(B
$BG$0U$N(B $n$ $B$K$D$$$FBj0U$,@.$jN)$D$3$H$r<($7$^$9!#(B

$n = 0$ $B$N$H$-!"(B
$V = \{\}$ $B$G$9!#(B
$BB8:_$7$J$$D:E@$rDL$kM-8~O)$,$"$k$b$N$H$7$^$9!#(B

$n = 1$ $B$N$H$-!"(B
$E = \{\}$ $B$G$9!#(B
$BM#0l$ND:E@$r(B $1$ $B2s$@$1DL$kM-8~O)$,$"$k$b$N$H$7$^$9!#(B

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{ $n = 2$ $B$N$H$-(B }
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

$V = \{ v_1, v_2 \}$ $B$N$H$-!"(B
$E = \{ (v_1, v_2) \}$ $B$G$"$j!"(B
$B0J2<$N(B $2$ $B$D$N>l9g$,$"$j$^$9!#(B

\begin{itemize}
\item
$E' = \{ v_1 \rightarrow v_2 \}$ $B$N$H$-!"(B
$B$9$Y$F$ND:E@$r(B $1$ $B2s$:$DDL$kM-8~O)(B $v_1, v_2$ $B$,$"$j$^$9!#(B

\item
$E' = \{ v_2 \rightarrow v_1 \}$ $B$N$H$-!"(B
$B$9$Y$F$ND:E@$r(B $1$ $B2s$:$DDL$kM-8~O)(B $v_2, v_1$ $B$,$"$j$^$9!#(B
\end{itemize}

$B$$$:$l$G$b$J$$>l9g$H$$$&$N$O$"$jF@$^$;$s!#(B
$B$$$:$l$N>l9g$G$b!"$9$Y$F$ND:E@$r(B $1$ $B2s$:$DDL$kM-8~O)$,$"$j$^$9!#(B

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{ $n = k+1$ $B$N$H$-(B }
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

$BBj0U$,(B $n = k$ $B$N$H$-$K@.$jN)$D$H$9$k$H!"(B
$n = k+1$ $B$N$H$-$K$b@.$jN)$D$3$H$r<($7$^$9!#(B

$V = \{ v_1, \ldots, v_k, v_{k+1} \}$ $B$N$H$-!"(B

\begin{tabular}{ll}
$V_k$ & $= \{ v_1, \ldots, v_k \}$ \\
$V'_k$ & $= \{ v'_1, \ldots, v'_k \} = V_k$ \\
\\
$E'$   & $= E'_k \cup E'_f \cup E'_t$ \\
$E'_k$ & $= \{ v'_i \rightarrow v'_{i+1} | v'_i, v'_{i+1} \in V'_k \}$ \\
$E'_f$ & $= \{ v'_i \rightarrow v_{k+1} | v'_i \in V'_k \}$ \\
$E'_t$ & $= \{ v_{k+1} \rightarrow v'_i | v'_i \in V'_k \}$ \\
\end{tabular}

$B$H$7$^$9!#(B
$E'_f, E'_t$ $B$N(B f, t $B$O!"$=$l$>$l(B from, to $B$rI=$7$^$9!#(B

$G$ $B$+$i(B $v_{k+1}$ $B$r=|$$$?M6F3ItJ,%0%i%U(B $G_k = (V_k, E_k)$ $B$O!"(B
$n = k$ $B$N40A4%0%i%U$G$"$j!"(B
$E_k$ $B$N3FJU$KG$0U$NJ}8~$r;XDj$7$F$G$-$k(B $E'_k$ $B$K$h$C$F(B
$G'_k = (V_k, E'_k)$ $B$r:n$k$H!"(B
$G'_k$ $B$K$O$9$Y$F$ND:E@$r$A$g$&$I(B $1$ $B2s$:$DDL$kM-8~O)(B
$v'_1, \ldots, v'_k$ $B$,$"$k$HDj5A$7$^$7$?!#(B
$B!J(B$V'_k = V_k$ $B$G$9$,!"(B
$v'_i = v_i$ $B$H$O8B$j$^$;$s!#!K(B

$B$3$N$H$-!"0J2<$N(B $3$ $B$D$N>l9g$,$"$j$^$9!#(B

\begin{enumerate}
\item
$(v'_k \rightarrow v_{k+1}) \in E'_f$ $B$N$H$-!"(B
$B$9$Y$F$ND:E@$r(B $1$ $B2s$:$DDL$kM-8~O)(B $v'_1, \ldots, v'_k, v_{k+1}$ $B$,$"$j$^$9!#(B

\item
$(v_{k+1} \rightarrow v'_1) \in E'_t$ $B$N$H$-!"(B
$B$9$Y$F$ND:E@$r(B $1$ $B2s$:$DDL$kM-8~O)(B $v_{k+1}, v'_1, \ldots, v'_k$ $B$,$"$j$^$9!#(B

\item
$B>e(B $2$ $B$D$N$$$:$l$b@.$jN)$?$J$$$H$-!"(B
$(v'_i \rightarrow v_{k+1}) \in E'_f \: \wedge \:
 (v_{k+1} \rightarrow v'_{i+1}) \in E'_t$
$B$G$"$k$h$&$J(B $i$ $B$,B8:_$7!"(B
$B$9$Y$F$ND:E@$r(B $1$ $B2s$:$DDL$kM-8~O)(B
$v'_1, \ldots, v'_i, v_{k+1}, v'_{i+1}, \ldots, v'_k$ $B$,$"$j$^$9!#(B
\end{enumerate}

$(v'_1 \rightarrow v_{k+1}) \in E'_f \: \wedge \:
 (v_{k+1} \rightarrow v'_k) \in E'_t$ $B$N$H$-!"(B
$(v'_i \rightarrow v_{k+1}) \in E'_f \: \wedge \:
 (v_{k+1} \rightarrow v'_{i+1}) \in E'_t$
$B$G$"$k$h$&$J(B $i$ $B$,B8:_$7$J$$$b$N$H$7$^$9!#(B

$(v'_1 \rightarrow v_{k+1}) \in E'_f$ $B$h$j!"(B
$(v'_2 \rightarrow v_{k+1}) \in E'_f$ $B$G$J$1$l$P$J$j$^$;$s!#(B
$B$J$<$J$i!"(B
$(v_{k+1} \rightarrow v'_2) \in E'_t$ $B$J$i$P!"(B
$v'_1$ $B$+$i(B $v_{k+1}$ $B$rDL$C$F(B $v'_2$ $B$X9T$/$h$&$JM-8~O)$,$"$j!"(B
$i = 1$ $B$,B8:_$7$F$7$^$&$+$i$G$9!#(B

$BF1MM$K!"(B
$(v'_i \rightarrow v_{k+1}) \in E'_f$ $B$J$i$P!"(B
$(v'_{i+1} \rightarrow v_{k+1}) \in E'_f$ $B$G$J$1$l$P$J$j$^$;$s!#(B

$B?t3XE*5"G<K!$K$h$C$F!"(B
$(v'_k \rightarrow v_{k+1}) \in E'_f$ $B$G$J$1$l$P$J$j$^$;$s!#(B
$B$3$l$OA0Ds$G$"$k(B
$(v_{k+1} \rightarrow v'_k) \in E'_t$ $B$KH?$7$F$$$^$9!#(B

$B$h$C$F!"(B
$B@h$K5s$2$?(B $3$ $B$D$N>l9g$G$9$Y$F$r?T$/$7$F$$$^$9!#(B
$B$$$:$l$N>l9g$b$9$Y$F$ND:E@$r(B $1$ $B2s$:$DDL$kM-8~O)$,$"$j$^$9!#(B

$BG$0U$N(B $n = k$ $B$K$D$$$FBj0U$,@.$jN)$D$3$H$r<($7$^$7$?!#(B

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{ 7.13
{\Q $n$$BD:E@$N40A4%0%i%U$K$O!"(B$n^{n-2}$$BDL$j$N6KBgLZ$,$"$k$3$H$r<($;!#(B}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

$n = 5$ $B$^$G<j$G?t$($?$N$G$9$,!"(B
$BG$0U$N(B $n = k$ $B$K$D$$$F$N>ZL@$OJ,$+$j$^$;$s$G$7$?!#(B

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{ $BAH$_9g$o$;(B }
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

$m$$B8D$N$b$N$+$i(B $n$$B8D$N$b$N$rA*$VAH$_9g$o$;$,2?DL$j$"$k$+$r!"(B
$B$3$N%l%]!<%H$G$O(B $C(m, n)$ $B$GI=$7$^$9!#(B

$C$ $B$O(B Combination $B$N(B $C$ $B$G$9!#(B

$B0lHL$K!"(B
$C(m, n) = \frac{ m! }{ n! (m-n)! }$ $B$G$9!#(B
$B$3$3$G!"(B
$!$ $B$O3,>h$rI=$7!"(B
$n! = \prod_{i=1}^n = 1 \times 2 \times \cdots \times n$ $B$G$9!#(B

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{ $B40A4%0%i%U(B }
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

$B40A4%0%i%U$H$O!"$I$N(B $2$$BD:E@$N4V$K$bJU$,$"$k$h$&$J%0%i%U$G$9!#(B

$B40A4%0%i%U$ND:E@$N?t$HJU$N?t$H$r$=$l$>$l(B $n, e_c$ $B$GI=$9$H!"(B
$BJU$N?t$O!"(B
$n$$B8D$ND:E@$+$i(B $B@\B3$9$k(B$2$$B8D$rA*$VAH$_9g$o$;$G$9$+$i!"(B
$e_c = C(n,2) = n(n-1)/2$ $BK\$G$9!#(B

$c$ $B$O(B complete $B$N(B $c$ $B$G$9!#(B

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{ $B6KBgLZ(B }
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

$BO"7k%0%i%U(B $G = (V, E)$ $B$,M?$($i$l$?$H$-!"(B
$V$ $B$N$9$Y$F$ND:E@$rO"7k$9$k<+M3LZ$r(B $G$$B$N6KBgLZ$H$$$$$^$9!#(B

$B<+M3LZ$O!"JDO)$N$J$$O"7k%0%i%U$G!"(B
$BD:E@$HJU$N?t$r$=$l$>$l(B $n, e_s$ $B$GI=$9$H!"(B
$e_s = n-1$ $B$G$9!#(B

$s$ $B$O(B spanning tree $B$N(B $s$ $B$G$9!#(B

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{ 7.13
{\Q $n$$BD:E@$N40A4%0%i%U$K$O!"(B$n^{n-2}$$BDL$j$N6KBgLZ$,$"$k$3$H$r<($;!#(B}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

$n = k$ $B$N$H$-!"(B
$k$$BD:E@$N40A4%0%i%U$K$O!"(B
$k ^ {k-2}$$BDL$j$N6KBgLZ$,$"$k$3$H$r(B
$B$=$l$>$l$N(B $k$ $B$K$D$$$FD4$Y$^$9!#(B

$n = 0$ $B$N40A4%0%i%U$K$O!"6KBgLZ$,$"$j$^$;$s!#(B
$0^{-2} = 0$ $B$G@.$jN)$C$F$$$^$9!#(B

$n = 1$ $B$N40A4%0%i%U$O!"M#0l$ND:E@$H(B $0$$BK\$NJU$r;}$A$^$9!#(B
$BM#0l$ND:E@$H(B $0$$BK\$NJU$+$i$J$k(B $1$$BDL$j$N6KBgLZ$,$"$j$^$9!#(B
$1^{-1} = 1$ $B$G@.$jN)$C$F$$$^$9!#(B

$n = 2$ $B$N40A4%0%i%U$O(B $1$$BK\$NJU$r;}$A$^$9!#(B
$2$$B$D$ND:E@$r@\B3$9$kM#0l$NJU$+$i$J$k(B $1$$BDL$j$N6KBgLZ$,$"$j$^$9!#(B
$2^0 = 1$ $B$G@.$jN)$C$F$$$^$9!#(B

$n = 3$ $B$N40A4%0%i%U$O(B $3$$BK\$NJU$r;}$A$^$9!#(B
$B6KBgLZ$O(B $2$$BK\$NJU$r;}$A$^$9!#(B
$3$$BD:E@$r$=$l$>$l@\B3$9$k$HJDO)$,$G$-$F$7$^$&$N$G!"(B
$3$$BJU$N$&$A!"$$$:$l$+(B $1$$BK\$r>C$5$J$1$l$P$J$j$^$;$s!#(B
$C(3,1) = 3$$BDL$j$N6KBgLZ$,$"$j$^$9!#(B
$3^1 = 3$ $B$G@.$jN)$C$F$$$^$9!#(B

$n = 4$ $B$N40A4%0%i%U$O(B $6$$BK\$NJU$r;}$A$^$9!#(B
$B6KBgLZ$O(B $3$$BK\$NJU$r;}$A$^$9!#(B
$6$$BJU$N$&$A(B $3$$BK\$rA*$VAH$_9g$o$;$O(B
$C(6,3) = (6 \times 5 \times 4) / (3 \times 2 \times 1) = 20$ $BDL$j$G$9$,!"(B
$B$3$NCf$K$O!"(B
$1$$BD:E@$@$1Cg4V$O$:$l$H(B $3$$BD:E@$r$=$l$>$l@\B3$7$?JDO)$H$+$i$J$k!"(B
$B6KBgLZ$G$J$$%0%i%U$,4^$^$l$F$$$^$9!#(B
$4$$BD:E@$+$iCg4V$O$:$l$N(B $1$$BD:E@$rA*$VAH$_9g$o$;$G!"(B
$C(4,1) = 4$ $BDL$j$N6KBgLZ$G$J$$%0%i%U$,$"$k$N$G!"(B
$B6KBgLZ$O(B $20 - 4 = 16$ $BDL$j$G$9!#(B
$4^2 = 16$ $B$G@.$jN)$C$F$$$^$9!#(B

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection*{ $n = 5$ $B$N$H$-(B }
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

$n = 5$ $B$N40A4%0%i%U$O(B $10$$BK\$NJU$r;}$A$^$9!#(B
$B6KBgLZ$O(B $4$$BK\$NJU$r;}$A$^$9!#(B
$4$$BJU$r;}$D(B $5$$BD:E@$N%0%i%U$O(B
$C(10,4) = (10 \times 9 \times 8 \times 7) /
  (4 \times 3 \times 2 \times 1) = 210$ $BDL$j$G$9$,!"(B
$B$3$N$&$A6KBgLZ$G$J$$$N$O!"(B

\begin{itemize}
\item
$2$$BD:E@$H(B $1$$BJU$r;}$DO"7k@.J,$H!"(B
$3$$BD:E@$H(B $3$$BJU$r;}$DJDO)$H$+$i$J$k%0%i%U(B

\item
$BCg4V$O$:$l$N(B $1$$BD:E@$H!"(B
$4$$BD:E@$H(B $4$$BJU$r;}$DO"7k@.J,$H$+$i$J$k%0%i%U(B
\end{itemize}

$B$N(B $2$$B<o$KJ,N`$G$-$^$9!#(B

$BA0<T$O!"(B
$2$$BD:E@$H(B $1$$BJU$r;}$DO"7k@.J,$b!"(B
$3$$BD:E@$H(B $3$$BJU$r;}$DJDO)$b!"(B
$B$=$l$>$l(B $1$$BDL$j$7$+$J$$$N$G!"(B
$BA4BN$G(B $C(5,2) = (5 \times 4) / 2 = 10$ $BDL$j$G$9!#(B

$B8e<T$O!"(B
$4$$BD:E@$H(B $4$$BJU$r;}$DO"7k@.J,$,!"(B
$C(6,4) = (6 \times 5 \times 4 \times 3) /
  (4 \times 3 \times 2 \times 1) = 15$ $BDL$j$J$N$G!"(B
$BA4BN$G(B $15 \times 5 = 75$ $BDL$j$G$9!#(B

$n = 5$ $B$N$H$-!"(B
$210 - (10 + 75) = 125$ $BDL$j$N6KBgLZ$,$"$j!"(B
$5^3 = 125$ $B$G@.$jN)$C$F$$$^$9!#(B

\begin{tabular}{cccc}
\hline
$n$ & $e_c$ & $e_s$ & $B6KBgLZ(B \\
\hline
$0$ & $0$ & $0$ & $0$ \\
$1$ & $0$ & $0$ & $1$ \\
$2$ & $1$ & $1$ & $1$ \\
$3$ & $3$ & $2$ & $3$ \\
$4$ & $6$ & $3$ & $16$ \\
$5$ & $10$ & $4$ & $125$ \\
\hline
\end{tabular}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection*{ $n = k$ $B$N$H$-(B }
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

$B?t3XE*5"G<K!$K$h$C$F!"(B
$n < k$ $B$N$H$-(B $n$$BD:E@$N40A4%0%i%U$K$O(B $n^{n-2}$$BDL$j$N6KBgLZ$,$"$k$H$9$k$H!"(B
$n = k$ $B$N$H$-$b@.$jN)$D$3$H$r<($7$^$9!#(B

$BJ,$+$j$^$;$s$G$7$?!#(B

\end{document}
