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

\newcommand{\Q}{\bf}
\newcommand{\dfs}{{\it dfs}}

\begin{document}
\maketitle

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{ $6.8$ }
{\Q $B?^(B $6.38$ $B$GD:E@$N=g=x$r(B $a, b, \cdots, f$ $B$H$7$F!"?<$5M%@h$N6KBg?9$r:n$l!#(B
  $BLZ$N8L!"@h9T8L!"8eB`8L!"8r:98L$r6hJL$;$h!#(B
  $B3FD:E@$N?<$5M%@hC5:wHV9f$r<($;!#(B}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{tabular}{c|c|c}
\hline
$BD:E@(B & $BNY@\%j%9%H(B & $B?<$5M%@hC5:wHV9f(B \\
\hline
$a$ & $b, d, f$ & $1$ \\
$b$ & $c, f$    & $2$ \\
$c$ & $d$       & $3$ \\
$d$ & $b$       & $4$ \\
$e$ & $d, f$    & $6$ \\
$f$ & $d$       & $5$ \\
\hline
\end{tabular}

\begin{tabular}{c|c}
\hline
$B8L(B & $B8L$N<oN`(B \\
\hline
$a \rightarrow b$ & $BLZ$N8L(B \\
$a \rightarrow d$ & $B@h9T8L(B \\
$a \rightarrow f$ & $B@h9T8L(B \\
$b \rightarrow c$ & $BLZ$N8L(B \\
$b \rightarrow f$ & $BLZ$N8L(B \\
$c \rightarrow d$ & $BLZ$N8L(B \\
$d \rightarrow b$ & $B8eB`8L(B \\
$e \rightarrow d$ & $B8r:98L(B \\
$e \rightarrow f$ & $B8r:98L(B \\
$f \rightarrow d$ & $B8r:98L(B \\
\hline
\end{tabular}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{ $6.15$ }
{\Q $B?^(B $6.38$ $B$N6/@.J,$r5a$a$h!#(B}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{tabular}{c|c|c}
\hline
$BD:E@(B & $B:F5"8F=P$7$,=*$o$C$?=g(B & $G_r$ $B$NNY@\%j%9%H(B \\
\hline
$a$ & 5 & \\
$b$ & 4 & $a, d$ \\
$c$ & 2 & $b$ \\
$d$ & 1 & $a, c, e, f$ \\
$e$ & 6 & \\
$f$ & 3 & $a, b, e$ \\
\hline
\end{tabular}

\begin{tabular}{c|c}
\hline
$G_r$ $B$N8L(B & $B8L$N<oN`(B \\
\hline
$b \rightarrow a$ & $B8r:98L(B \\
$b \rightarrow d$ & $BLZ$N8L(B \\
$c \rightarrow b$ & $B8eB`8L(B \\
$d \rightarrow a$ & $B8r:98L(B \\
$d \rightarrow c$ & $BLZ$N8L(B \\
$d \rightarrow e$ & $B8r:98L(B \\
$d \rightarrow f$ & $BLZ$N8L(B \\
$f \rightarrow a$ & $B8r:98L(B \\
$f \rightarrow b$ & $B8eB`8L(B \\
$f \rightarrow e$ & $B8r:98L(B \\
\hline
\end{tabular}

$B$7$?$,$C$F!"?^(B $6.38$ $B$N6/@.J,$O!"(B
$$\{a\}, \{b, c, d, f\}, \{e\}$$
$B$H$J$j$^$9!#(B

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{ $6.19$ }
{\Q $e$ $BK\$NJU$H(B $n$ $B8D$ND:E@$r;}$DM-8~%0%i%U$K6/O"7k$N%"%k%4%j%:%`$rE,MQ$9$k$H!"(B
  $n \leq e$ $B$N$H$-(B $O(e)$ $B;~4V$+$+$k$3$H$r<($;!#(B}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

$B6/O"7k$N%"%k%4%j%:%`$O!"(B

\begin{description}
\item[$(1)$]
$BM?$($i$l$?M-8~%0%i%U(B $G$ $B$KBP$7$F?<$5M%@hC5:w$r9T$$!"(B
$B:F5"8F=P$7$,=*$o$C$?=g$GD:E@$KHV9f$r$D$1$k!#(B

\item[$(2)$]
$G$ $B$N$9$Y$F$N8L$r5U8~$-$K$7$??7$7$$M-8~%0%i%U(B $G_r$ $B$r:n$k!#(B

\item[$(3)$]
$B%9%F%C%W(B $1$ $B$G:G$bBg$-$JHV9f$r$D$1$?D:E@$r=PH/E@$H$7$F!"(B
$G_r$ $B$KBP$7$F?<$5M%@hC5:w$r9T$&!#(B
$B8L$NC5:w$GE~C#$G$-$J$$D:E@$,$"$C$?$i!"(B
$B$=$NCf$G:GBg$NHV9f$r$D$1$i$l$?D:E@$r=PH/E@$H$7$F!"(B
$B:FEY?<$5M%@hC5:w$r9T$&!#(B

\item[$(4)$]
$B$3$&$7$FF@$i$l$?6KBg?9$r9=@.$9$kLZ(B $1$$B$D(B$1$$B$D$,(B $G$ $B$N6/O"7k@.J,$G$"$k!#(B
\end{description}

$B$H$$$&$b$N$G$9!#(B

$B$^$:!"%9%F%C%W(B $1$ $B$G$9$,!"(B$n \leq e$ $B$NM-8~%0%i%U$KBP$7$F?<$5M%@hC5:w$r9T$&$H!"(B
$O(e)$ $B;~4V$+$+$j$^$9!#(B
$1$$B$D$ND:E@$K4X$7$F(B $0$$B2s$^$?$O(B $1$$B2s(B \dfs $B$r8F$S!"(B
\dfs (v) $B$O(B $O(|L[v]|)$ $B$J$N$G!"(B
$BA4BN$G(B $\sum_{i=1}^n O(|L[v_i]|) = O(e)$ $B$@$+$i$G$9!#(B
$B:F5"8F=P$7$,=*$o$C$?=g$GD:E@$KHV9f$r$D$1$k$N$O!"(B
$1$$B$D$ND:E@$K4X$7$F(B $O(1)$$B!"(B
$BA4BN$G(B $O(n)$ $B$G$9!#(B
$n \leq e$ $B$J$N$G!"A4BN$H$7$F(B $O(e+n) = O(e)$ $B;~4V$+$+$j$^$9!#(B

$B%9%F%C%W(B $2$ $B$b(B $O(e)$ $B$G$9!#(B
$G$ $B$N8L(B $v \rightarrow w$ $B$KBP$7$F!"(B
$G_r$ $B$O8L(B $w \rightarrow v$ $B$r;}$A!"(B
$BA4BN$G(B $e$ $BK\$N8L$r;}$C$F$$$^$9!#(B
$G$ $B$N8L$r(B $1$ $BK\$E$D8+$F$$$-!"(B
$G_r$ $B$N8L$r:n$k$N$K!"(B
$O(e)$ $B;~4V$+$+$j$^$9!#(B

$B%9%F%C%W(B $3$ $B$O!"%9%F%C%W(B $1$ $B$HF1$8?<$5M%@hC5:w$J$N$G!"(B
$O(e)$ $B;~4V$+$+$j$^$9!#(B

$4$ $B$O!"$9$G$K2r$,F@$i$l$F$$$k$N$G!"%9%F%C%W$G$O$"$j$^$;$s!#(B

$B$3$l$i$N7k2L$rAm9g$9$k$H!"(B
$O(e) + O(e) + O(e) = O(e)$ $B$G!"A4BN$H$7$F(B $O(e)$ $B;~4V$+$+$j$^$9!#(B

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{ $O(e)$ $B$N>r7o(B }
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

$B6/O"7k$N%"%k%4%j%:%`$,(B $O(e)$ $B;~4V$G=*$o$k$?$a$K$O!"(B
$B$$$/$D$+$N>r7o$,$"$j$^$9!#(B

$n \leq e$ $B$,@.$jN)$C$F$$$J$1$l$P!"(B
$B%9%F%C%W(B $1$ $B$O(B $O(n)$ $B;~4V$+$+$j$^$9!#(B
$BB?$/$ND:E@$r;}$A!"8L$,$[$H$s$I$J$$M-8~%0%i%U$KBP$7$F!"(B
$B6/O"7k$N%"%k%4%j%:%`$O(B $O(n)$ $B;~4V$+$+$C$F$7$^$$$^$9!#(B

$B%9%F%C%W(B $2$ $B$G$O!"(B
$G$ $B$r8+$F(B $G_r$ $B$N8L$r:n$k$N$K(B $O(e)$ $B;~4V$+$+$j$^$9!#(B
$B$?$@$7!"$3$l$O!"(B
$G$ $B$N8L(B $v \rightarrow w$ $B$r8+$F(B $G_r$ $B$N8L(B $w \rightarrow v$ $B$r:n$k$N$K(B $O(1)$ $B;~4V$7$+$+$+$i$J$$(B
$B$H2>Dj$7$?>l9g$G$9!#(B

$G$ $B$,NY@\9TNs$GI=8=$5$l$F$$$l$P!"E>CV9TNs$r5a$a$k$3$H$K$J$j$^$9!#(B
$n \times n$ $B$NE>CV9TNs$r5a$a$k$K$O(B $O(n^2)$ $B;~4V$+$+$j$^$9!#(B
$B$3$N>l9g!"(B
$n^2 \leq e$ $B$G$J$1$l$P!"%"%k%4%j%:%`A4BN$K(B $O(n^2)$ $B;~4V$+$+$C$F$7$^$$$^$9!#(B

$G$ $B$,NY@\%j%9%H$GI=8=$5$l$F$$$l$P!"8L$r(B $1$ $BK\$E$D8+$F$$$-!"(B
$G_r$ $B$NNY@\%j%9%H$r:n$k$3$H$K$J$j$^$9!#(B
$BNY@\%j%9%H$NBg$-$5$O(B $O(e)$ $B$G$9$,!"(B
$G_r$ $B$N8L(B $1$$BK\$K$D$-!"$=$l$>$l(B $O(1)$ $B;~4V$G%j%9%H$KDI2C$7$J$1$l$P$J$j$^$;$s!#(B
$B%j%9%H$NF,$KDI2C$7$?$j!"DI2C0LCV$N%]%$%s%?$rJ];}$7$?$j$9$l$PNI$$$N$G$9$,!"(B
$1$$BK\DI2C$9$k$4$H$K%j%9%H$NF,$+$iHx$^$G%]%$%s%?$r$?$I$k$h$&$JGO</$J<B8=K!$r:N$k$H!"(B
$B:G0-(B $O(n \times e)$ $B;~4V$+$+$C$F$7$^$$$^$9!#(B

\end{document}
