% Homework 7, CSCE 235, spring 2007
% Assigned 10 April 2007; due 18 April 2007

\pdfpagewidth=8.5truein \pdfpageheight=11truein
\hsize=5.5truein \vsize=8.5truein
\pdfhorigin=1.5truein \pdfvorigin=1.25truein

% MetaPost stuff
\input supp-pdf
\def\fig#1{\convertMPtoPDF{#1}{1}{1}}
\def\midfig#1{{%
	\setbox0=\hbox{\fig{#1}}%
	\dimen0=0.5\ht0%
	\advance\dimen0 by-0.3\ht\strutbox
	\lower\dimen0\box0%
}}

\headline={\hfil}
\footline={\hfil Page~\folio\hfil}

\newcount\pno
\pno=0
\def\problem{\advance\pno by1 \noindent{\bf Problem~\the\pno.} }
\def\problemno#1. {\noindent{\bf Problem~\hbox{#1}.} }
\def\solution{\nobreak\medskip\noindent{\bf Solution.} }
\def\part#1{\medskip\indent\llap{#1\enspace}\ignorespaces}
\def\mathpart#1#2\par{{%
	\abovedisplayskip=-\ht\strutbox \advance\abovedisplayskip by-\dp\strutbox %
	\abovedisplayshortskip=-\ht\strutbox \advance\abovedisplayshortskip by-\dp\strutbox %
	\part{#1}#2\par}}

\def\implies{\;\Longrightarrow\;}
\def\N{\mathord{\bf N}}  \def\Z{\mathord{\bf Z}}
\def\Q{\mathord{\bf Q}}  \def\R{\mathord{\bf R}}
\def\labs{\mathopen|}  \def\rabs{\mathclose|}

\centerline{CSCE~235: Introduction to Discrete Structures}
\centerline{{\bf Homework assignment~7} (115~points)}
\centerline{Assigned Tuesday, April~10, 2007}
\centerline{Due Wednesday, April~18, 2007}

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (18~points) Make a list of drawings of all the simple graphs with at
most four vertices. The list should not contain any isomorphic pairs of graphs.
(You should get a list of 18~graphs.)

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (8~points) Draw a graph with exactly five vertices, each of degree~5,
or explain why such a graph does not exist.

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (10~points) Draw $Q_4$. Is this graph bipartite?

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (24~points) For each of the graphs below, determine whether it has an
Euler circuit, and construct such a circuit if one exists. If the graph has no
Euler circuit, explain why. Also determine whether the graph has a Hamiltonian
circuit, and either construct such a circuit if one exists or justify your
claim that there is no Hamiltonian circuit.

$$\matrix{
	\hbox{(a)}&\midfig{homework-7.1}&\hskip1in&\hbox{(c)}&\midfig{homework-7.3}\cr
\noalign{\vskip0.3in}
	\hbox{(b)}&\midfig{homework-7.2}&&\hbox{(d)}&\midfig{homework-7.4}\cr
}$$

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (12~points) In graph models of saturated hydrocarbons, each carbon
atom is represented by a vertex of degree~4, and each hydrogen atom is
represented by a vertex of degree~1. (See Example~5 on page~688 of the
textbook.) The nonisomorphic trees with $n$~vertices of degree~4 and
$2n+2$~vertices of degree~1 represent the different isomers of ${\rm C}_n{\rm
H}_{2n+2}$. How many isomers are there of
\smallskip
\item{(a)} propane ($\rm C_3H_8$)?
\item{(b)} pentane ($\rm C_5H_{12}$)?
\item{(c)} hexane ($\rm C_6H_{14}$)?

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (10~points) Build a binary search tree for the words in the sentence
``now is the time for all good men to come to the aid of their party'',
inserting the words into the tree in the order they appear in the sentence. Do
not insert duplicate words more than once.

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (21~points) Consider the following tree~$T$.
$$\fig{homework-7.5}$$
Form an ordered rooted tree~$T'$ from~$T$ by choosing $d$ as the root and
ordering the children of each internal vertex alphabetically. Draw~$T'$. In
what order are the vertices encountered in the preorder traversal of~$T'$? in
the inorder traversal of~$T'$? in the postorder traversal of~$T'$? Answer the
same questions if $j$ is chosen as the root, and if $f$ is chosen as the root.

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (12~points) Find a spanning tree for the graph shown below by
beginning at~$a$ and using
\smallskip
\item{(a)} depth-first search.
\item{(b)} breadth-first search.
$$\fig{homework-7.6}$$

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bye