台灣大學數學系

九十二學年度第二學期博士班資格考試題

離散數學

May 9, 2004

[回上頁]

1.

(20 %) (a) Suppose that $(A_1, A_2, \ldots, A_n)$ is a family of sets such that $\vert A(J)\vert \ge \vert J\vert$    for all $J \subseteq \{1, 2, \ldots, n\},$ where $A(J)=\cup_{j\in J} A_j$. Prove that if $\vert A_i\vert \ge r$ for $1 \le i \le n$, then the number of SDRs for this family is at least $r!$ if $r \le n$, and is at least $r(r-1)\ldots(r-n+1)$ if $r > n$.

(b)

Given a $k \times n$ Latin rectangle with $k < n$, prove that there are at least $(n-k)!$ ways to add a row to form a $(k+1) \times n$ rectangle.

2.

(20 %) (a) Suppose $(A_{ij})$ is an $n \times n$ real matrix whose entries satisfy $\vert a_{ij}\vert \le 1$ for all $i,j$. Prove that $\vert\det(A)\vert \le n^{n/2}$; and the equality holds if and only if $a_{ij}= \pm 1$ for all $i,j$ and $A A^{\tt T} = n I$. (Such a matrix is called an Hadamard matrix.)

(b)

Prove that if a Hadamard matrix of order $n$ exists, then either $n=1$ or $n=2$, or $n \equiv 0$ (mod 4).

3.

(20 %) Let $A$ and $B$ be two $m \times n$ matrices with entries in $\{0,1\}$. An exchange operation substitutes a submatrix of the form $\left( \begin{array}{cc} 0& 1 \\ 1 &0 \end{array}\right)$ for a submatrix of the form $\left( \begin{array}{cc} 1& 0 \\ 0 &1 \end{array}\right)$ or vice versa. Prove that if $A$ and $B$ have the same list of row sums and have the same list of column sums, then $A$ can be transformed into $B$ by a sequence of exchange operations. Interpret this conclusion in the context of bipartite graphs.

4.

(20 %) Let $G$ be a connected graph of $n$ vertices. Define a new graph $G'$ having one vertex for each spanning tree of $G$, with vertices adjacent in $G'$ if and only if the corresponding trees have exactly $n-2$ common edges. Prove that $G'$ is connected. Determine the diameter of $G'$.

5.

(20 %) The $k$th power of a simple graph $G$ is the simple graph $G^k$ with vertex set $V(G)$ and edge set $\{uv: 1 \le d_G(u,v)\le k\}$. (a) Suppose that $G-x$ has at least three nontrivial components in each of which $x$ has exactly one neighbor. Prove that $G^2$ is not Hamiltonian. (b) Prove that the cube of each connected graph (with at least three vertices) is Hamiltonian. (HINT: Reduce this to the special case of trees, and prove a stronger result that if $xy$ is an edge of the tree $T$, then $T^3$ has a Hamiltonian cycle using the edge $xy$.)

[回上頁]