\documentclass[a4j]{jarticle}

\newcommand{\Q}{\small}
\newcommand{\CLOSEST}{{\it CLOSEST}}
\newcommand{\LOWCOST}{{\it LOWCOST}}

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

\begin{document}
\maketitle

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{ 7.3
{\Q $B?^(B7.20$B$N%0%i%U$r9M$($k!#(B}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

$V = \{ a, b, c, d, e, f, g, h \}$

\begin{tabular}{c|cccccccc}
    & $a$ & $b$ & $c$ & $d$ & $e$ & $f$ & $g$ & $h$ \\
\hline
$a$ &     & $2$ & $3$ & no  & no  & no  & no  & no  \\
$b$ & $2$ &     & no  & $2$ & no  & no  & no  & no  \\
$c$ & $3$ & no  &     & $1$ & no  & no  & no  & no  \\
$d$ & no  & $2$ & $1$ &     & $2$ & $4$ & no  & no  \\
$e$ & no  & no  & no  & $2$ &     & $1$ & $2$ & no  \\
$f$ & no  & no  & no  & $4$ & $1$ &     & $2$ & $1$ \\
$g$ & no  & no  & no  & no  & $2$ & $2$ &     & $3$ \\
$h$ & no  & no  & no  & no  & no  & $1$ & $3$ &     \\
\end{tabular}

$BB3$/(B $2$ $BLd$O!"!V?<$5M%@h$N6KBgLZ$r5a$a$h!#!W$H$J$C$F$$$^$9$,!"(B
$B%3%9%H:G>.$N6KBgLZ$N4V0c$$$@$H;W$$$^$9!#(B
$B$7$?$,$C$F!"0J2<$N(B $2$ $BLd$G$O!"(B
$2$ $BDL$j$N%"%k%4%j%:%`$r;H$C$F!"%3%9%H:G>.$N6KBgLZ$r5a$a$^$9!#(B

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{ (a)
{\Q $B%W%j%`$N%"%k%4%j%:%`$r;H$C$F!"?<$5M%@h!J%^%^!K$N6KBgLZ$r5a$a$h!#(B}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

$B%W%j%`$N%"%k%4%j%:%`$G$O!"(B
$U$ $BFb$ND:E@$N(B \LOWCOST $B$KHVJ<$H$7$F(B $\infty$ $B$rF~$l$F$$$^$9!#(B
$B652J=q(B $207$ $B%Z!<%8$N?^(B7.8 (12)$B9TL\$G$9!#(B

(5)$B9TL\$+$i(B(10)$B9TL\$^$G!"(B
$U$ $B30$K$"$C$F(B $U$ $BFb$ND:E@$K:G$b6a$$D:E@(B $k$ $B$r5a$a$k$H$-$K!"(B
$\LOWCOST[k] < \infty$ $B$G$"$k$h$&$J(B $k$ $B$,B8:_$9$k$H$$$&A0Ds$KN)$C$F$$$^$9!#(B

$B$^$?!"(B(14)$B9TL\$N(B {\bf and} $(\LOWCOST[j] < \infty)$ $B$G!"(B
$j$ $B$,(B $U$ $B30$ND:E@$G$"$k$+$rH=Dj$7$F$$$^$9!#(B
$B$3$N$?$a!"(B
no $B$O(B $< \infty$ $B$+$D(B $> max\{ C[v,w] | v,w \in V \}$ $B$G$J$1$l$P$J$j$^$;$s!#(B

\begin{tabular}{l|ccccccc}
\hline
$U$ & \multicolumn{7}{c}{ $\CLOSEST[i], \LOWCOST[i]$ } \\
& $b$ & $c$ & $d$ & $e$ & $f$ & $g$ & $h$ \\
\hline
$\{ a               \}$ & $a,  2   $ & $a,  3   $ & $a$, no    & $a$, no    & $a$, no    & $a$, no    & $a$, no    \\
$\{ a,b             \}$ & $a,\infty$ & $a,  3   $ & $b,  2   $ & $a$, no    & $a$, no    & $a$, no    & $a$, no    \\
$\{ a,b,d           \}$ & $a,\infty$ & $d,  1   $ & $b,\infty$ & $d,  2   $ & $d,  4   $ & $a$, no    & $a$, no    \\
$\{ a,b,d,c         \}$ & $a,\infty$ & $d,\infty$ & $b,\infty$ & $d,  2   $ & $d,  4   $ & $a$, no    & $a$, no    \\
$\{ a,b,d,c,e       \}$ & $a,\infty$ & $d,\infty$ & $b,\infty$ & $d,\infty$ & $e,  1   $ & $e,  2   $ & $a$, no    \\
$\{ a,b,d,c,e,f     \}$ & $a,\infty$ & $d,\infty$ & $b,\infty$ & $d,\infty$ & $e,\infty$ & $e,  2   $ & $f,  1   $ \\
$\{ a,b,d,c,e,f,h   \}$ & $a,\infty$ & $d,\infty$ & $b,\infty$ & $d,\infty$ & $e,\infty$ & $e,  2   $ & $f,\infty$ \\
$\{ a,b,d,c,e,f,h,g \}$ & $a,\infty$ & $d,\infty$ & $b,\infty$ & $d,\infty$ & $e,\infty$ & $e,\infty$ & $f,\infty$ \\
\hline
\end{tabular}

\begin{tabular}{l}
\hline
$B0u:~$5$l$kJU(B \\
\hline
$(b, a)$ \\
$(d, b)$ \\
$(c, d)$ \\
$(e, d)$ \\
$(f, e)$ \\
$(h, f)$ \\
$(g, e)$ \\
\hline
\end{tabular}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{ (b)
{\Q $B%/%i%9%+%k$N%"%k%4%j%:%`$r;H$$!"?<$5M%@h!J%^%^!K$N6KBgLZ$r5a$a$h!#(B}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{tabular}{l|l}
\hline
ncomp, components & $T$, edges \\
\hline
$8, [a], [b], [c], [d], [e], [f], [g], [h]$ & $\emptyset, \;\;\; \{ (c,d), (e,f), (f,h), (a,b), (b,d), (d,e), (e,g), (f,g), (a,c), (g,h), (d,f) \}$ \\
$7, [a], [b], [c,d], [e], [f], [g], [h]$ & $\{ (c,d) \}, \;\;\; \{ (e,f), (f,h), (a,b), (b,d), (d,e), (e,g), (f,g), (a,c), (g,h), (d,f) \}$ \\
$6, [a], [b], [c,d], [e,f], [g], [h]$ & $\{ (c,d), (e,f) \}, \;\;\; \{ (f,h), (a,b), (b,d), (d,e), (e,g), (f,g), (a,c), (g,h), (d,f) \}$ \\
$5, [a], [b], [c,d], [e,f,h], [g]$ & $\{ (c,d), (e,f), (f,h) \}, \;\;\; \{ (a,b), (b,d), (d,e), (e,g), (f,g), (a,c), (g,h), (d,f) \}$ \\
$4, [a,b], [c,d], [e,f,h], [g]$ & $\{ (c,d), (e,f), (f,h), (a,b) \}, \;\;\; \{ (b,d), (d,e), (e,g), (f,g), (a,c), (g,h), (d,f) \}$ \\
$3, [a,b,c,d], [e,f,h], [g]$ & $\{ (c,d), (e,f), (f,h), (a,b), (b,d) \}, \;\;\; \{ (d,e), (e,g), (f,g), (a,c), (g,h), (d,f) \}$ \\
$2, [a,b,c,d,e,f,h], [g]$ & $\{ (c,d), (e,f), (f,h), (a,b), (b,d), (d,e) \}, \;\;\; \{ (e,g), (f,g), (a,c), (g,h), (d,f) \}$ \\
$1, [a,b,c,d,e,f,h,g]$ & $\{ (c,d), (e,f), (f,h), (a,b), (b,d), (d,e), (e,g) \}, \;\;\; \{ (f,g), (a,c), (g,h), (d,f) \}$ \\
\hline
\end{tabular}

$BD:E@$N=g=x$r(B $a, b, c, d, e, f, g, h$ $B$H$9$k$H!"(B
$B%W%j%`$N%"%k%4%j%:%`$b%/%i%9%+%k$N%"%k%4%j%:%`$bF1$87k2L$r=P$7$^$7$?!#(B

$B%/%i%9%+%k$N%"%k%4%j%:%`$O!"(B
$B$9$Y$F$NJU$r@0Ns$9$k$N$K;~4V$,$+$+$j$^$9$,!"$=$N8e$OB.$$$G$9!#(B
$B%W%j%`$N%"%k%4%j%:%`$O!"(B
\CLOSEST $B$H(B \LOWCOST $B$N99?7$K;~4V$,$+$+$j$^$9!#(B

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{ 7.5
{\Q $G = (V, E)$ $B$r%0%i%U$H$9$k!#(B
$R$ $B$r(B $V$ $B>e$N4X78$H$7$F!"(B
$u$ $B$H(B $v$ $B$,6&DL$NJDO)>e$K$"$k$3$H$r(B $u R v$ $B$G<($9$3$H$K$9$k!#(B
$R$ $B$,(B $V$ $B>e$NF1CM4X78$G$"$k$3$H$r>ZL@$;$h!#(B}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

$B7PO)(B $v_1, \ldots, v_n$ $B$,JDO)$G$"$k$H$O!"(B
$B0J2<$N(B $3$ $B$D$,@.$jN)$D$3$H$G$9!#(B

\begin{tabular}{ll}
$BD:E@$r<+J,<+?H$HO"7k(B & $(v_1 = v_n)$ \\
$BD9$5(B $3$ $B0J>e(B & $(n \geq 3)$ \\
$BC1=c(B & $\forall i, j \in [1,n-1] \; (i \neq j \Rightarrow v_i \neq v_j)$ \\
\end{tabular}

$u$ $B$H(B $v$ $B$,6&DL$NJDO)>e$K$"$k$H$O!"(B
$BJDO)(B $u, v_1, \ldots, v_i, v, v_{i+1}, \ldots, v_n, u$ $B$,B8:_$9$k$3$H$G$9!#(B

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

$B0lHL$K!"(B
$R$ $B$,(B $V$ $B>e$NF1CM4X78$G$"$k$H$O!"(B
$R$ $B$,(B $V$ $B>e$N4X78$G$"$C$F!"0J2<$N(B $3$ $B$D$,@.$jN)$D$3$H$G$9!#(B

\begin{tabular}{ll}
$BH?<MN'(B & $\forall v \in V (v R v)$ \\
$BBP>NN'(B & $\forall u, v \in V (u R v \Rightarrow v R u)$ \\
$B?d0\N'(B & $\forall u, v, w \in V (u R v \wedge v R w \Rightarrow u R w)$ \\
\end{tabular}

$B@_Ld$h$j!"(B
$R$ $B$,(B $V$ $B>e$N4X78$G$"$k$3$H$OJ,$+$C$?$N$G!"(B
$BH?<MN'!"BP>NN'!"?d0\N'$N(B $3$ $B$D$,@.$jN)$D$3$H$r<($7$^$9!#(B

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection*{ $BH?<MN'(B }
$\forall v \in V (v R v)$ $B$,@.$jN)$D$3$H$r<($7$^$9!#(B

\begin{itemize}
\item
$v$ $B$rDL$kJDO)$,B8:_$9$l$P!"L@$i$+$K(B $v R v$ $B$G$9!#(B
$v$ $B$H(B $v$ $B$O6&DL$NJDO)>e$K$"$k$+$i$G$9!#(B

\item
$v$ $B$rDL$kJDO)$,B8:_$7$J$$>l9g!"J,$+$j$^$;$s!#(B
$v R v$ $B$O@.$jN)$A$^$;$s!#(B
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection*{ $BBP>NN'(B }
$\forall u, v \in V (u R v \Rightarrow v R u)$ $B$,@.$jN)$D$3$H$r<($7$^$9!#(B

$u R v$ $B$h$j!"(B
$BJDO)(B $u, v_1, \ldots, v_i, v, v_{i+1}, \ldots, v_n, u$ $B$,B8:_$7$^$9!#(B

$B$3$NJDO)$O!"(B
$v, v_{i+1}, \ldots, v_n, u, v_1, \ldots, v_i, v$ $B$HI=$9$3$H$,$G$-$^$9!#(B
$B$9$J$o$A!"(B
$v R u$ $B$,@.$jN)$A$^$9!#(B

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection*{ $B?d0\N'(B }
$\forall u, v, w \in V (u R v \wedge v R w \Rightarrow u R w)$
$B$,@.$jN)$D$3$H$r<($7$^$9!#(B

$u R v$ $B$h$j!"(B
$BJDO)(B $u, v_1, \ldots, v_i, v, v_{i+1}, \ldots, v_n, u$ $B$,B8:_$7$^$9!#(B

\begin{itemize}
\item
$B$3$NJDO)>e$K(B $w$ $B$,$"$l$P!"L@$i$+$K(B $u R w$ $B$G$9!#(B
$B$9$J$o$A!"(B
$w \in \{ u, v_1, \ldots, v_i, v, v_{i+1}, \ldots, v_n \}$ $B$G$"$l$P!"(B
$u$ $B$H(B $w$ $B$O6&DL$NJDO)>e$K$"$j$^$9!#(B

\item
$B$3$NJDO)>e$N(B $v$ $B0J30$ND:E@$,!"(B
$BJDO)(B $v, w_1, \ldots, w_j, w, w_{j+1}, \ldots, w_m, v$ $B>e$K$"$k>l9g!"(B
$u R w$ $B$G$9!#(B
$B$9$J$o$A!"(B
$v_k = w_l$ $B$J$i$P!"(B

\begin{tabular}{ll}
$k<i, l<j$ $B$N>l9g(B & $u, v_1, \ldots, v_k=w_l, \ldots, w_j, w, w_{j+1}, \ldots, w_m, v, v_{i+1}, \ldots, v_n, u$ \\
$k<i, l>j$ $B$N>l9g(B & $u, v_1, \ldots, v_k=w_l, \ldots, w_{j+1}, w, w_j, \ldots, w_1, v, v_{i+1}, \ldots, v_n, u$ \\
$k>i, l<j$ $B$N>l9g(B & $u, v_1, \ldots, v_i, v, w_m, \ldots, w_{j+1}, w, w_j, \ldots, w_l=v_k, \ldots, v_n, u$ \\
$k>i, l>j$ $B$N>l9g(B & $u, v_1, \ldots, v_i, v, w_1, \ldots, w_j, w, w_{j+1}, \ldots, w_l=v_k, \ldots, v_n, u$ \\
\end{tabular}

$B$H$$$&JDO)$,B8:_$7!"(B
$u$ $B$H(B $w$ $B$,6&DL$NJDO)>e$K$"$j$^$9!#(B

\item
$u$ $B$rDL$kJDO)$H(B $w$ $B$rDL$kJDO)$K6&DL$JD:E@$,(B $v$ $B$N$_$N>l9g!"J,$+$j$^$;$s!#(B
$\{ u, v_1, \ldots, v_n \} \cup \{ w_1, \ldots, w_j, w, w_{j+1}, \ldots, w_m \} = \emptyset$ $B$N>l9g!"(B
$u R w$ $B$O@.$jN)$A$^$;$s!#(B
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{ $B7kO@(B }

$V$ $B>e$N4X78(B $R$ $B$K$D$$$F!"(B
$BBP>NN'$O@.$jN)$A$^$9$,!"(B
$BH?<MN'$H?d0\N'$OI,$:$7$b@.$jN)$A$^$;$s!#(B
$B$7$?$,$C$F!"(B
$R$ $B$O(B $V$ $B>e$NF1CM4X78$G$O$"$j$^$;$s!#(B

$B$3$NLdBj$,LdBj$H$7$F@.$jN)$D$?$a$K$O!"(B
$B@)Ls$r4K$a$J$1$l$P$J$j$^$;$s!#(B
$B0J2<$K!"@)Ls$r4K$a$?Nc$r$$$/$D$+5s$2$^$9!#(B

\begin{itemize}
\item $BLdBj<+BN$rJQ$($F$7$^$&!#(B
$B!V$G$"$k$3$H$r>ZL@$;$h!#!W$H$O!"(B
$B$G$J$$$3$H$r>ZL@$9$l$P2r7h$5$l$?$b$N$H$9$k!#(B

\item $BDj5A$rJQ$($F$7$^$&!#(B
$BF1CM4X78$NDj5A!"H?<MN'$H?d0\N'$rJQ$($k!#(B
$B$"$k$$$OJDO)$NDj5A!"D9$5(B $3$ $B0J>e$G$"$k$3$H!"C1=c$G$"$k$3$H$rJQ$($k!#(B

\item $B2r<a$rJQ$($k!#(B
$B!V(B$u$ $B$H(B $v$ $B$,6&DL$NJDO)>e$K$"$k!W$H$O!"(B
$u$ $B$H(B $v$ $B$rDL$kJDO)$,B8:_$9$k$3$H$G$O$J$/!"(B
$u$ $B$rDL$kJDO)$H(B $v$ $B$rDL$kJDO)$,6&M-E@$r;}$D$3$H$G$"$k$H$9$k!#(B

\item $BLdBjJ8Cf$N8@MU$rJQ$($k!#(B
$G$ $B$O(B $3$ $B$D0J>e$ND:E@$r;}$D40A4%0%i%U!"(B
$B$9$J$o$A$9$Y$F$ND:E@$NBP$,@\B3$5$l$?%0%i%U$G$"$k$H$9$k!#(B
$B$"$k$$$O(B $u$ $B$H(B $v$ $B$rO"7k$9$kC1=c$J7PO)$,B8:_$9$k$3$H$r(B $u R v$ $B$G<($9$b$N$H$9$k!#(B
\end{itemize}

$B>e$NJ}$OL5Cc$JOC$J$N$G!":G8e$N0F$r:N$k$N$,NI$$$G$7$g$&!#(B

\end{document}
