※ [本文轉錄自 NTU-Exam 看板]
作者: TassTW (為文載道尊於勢) 看板: NTU-Exam
標題: [試題] 94下 張鎮華 圖論一 期中考
時間: Thu Nov 10 22:59:18 2005
課程名稱︰圖論一
課程性質︰選修
課程教師︰張鎮華 教授
開課系所︰數學系
考試時間︰2005/11/08 7:30-10:00
試題：
Examination 1 (Graph Theory I)
2005-11-8 (Gerard J.Chang)
[B1](14%) Prove that removing opposite corner squares from an 8-by-8
checkerboard leaves a sub-board that cannot bepartitioned into 1-by-2
and 2-by-1 rectangles.
[C1](4%) The square (i,j) in an 8-by-8 chessboard is the one in row i and
column j. Determine the conditions in terms of i,j,k,l for which the
removing of squares (i,j) and (k,l) from an 8-by-8 checkerboard leaves
a sub-board that can (respectively,can not) be partitioned into 1-by-2
and 2-by-1 rectangles. Give reasons.
[B2](14%) Let G be the graph whose vertex set is the set of n-tuple with
elements in {0,1}, with x adjacent to y if x and y differ in exactly two
positions. Determine the number of components of G. Give reasons.
[C2](4%) For positive integers n and k, let G_n,k be the graph whose verex
set of n-tuples with elements in {0,1}, with x adjacent to y if x and y
differ in exactly k positions. Determine the number of components in G.
Give reasons.
[B3](14%) Let d1,d2,...,dn be integers such that d1≧d2≧...≧dn. Prove that
there is a (loopless) multi-graph with degree sequence d1,d2,...,dn if and
only if Σdi is even and d1≦d2+d3+...+dn.
[B4](14%) For n≧1, let a_n be the number of spanning trees in the graph
formed from P_n (path with n vertices) by adding a vertex adjacent to all
verteices in P_n. (namely, Fan Graph) For example, a_1 = 1, a_2 = 3 and
a_3 = 8. Prove that a_n = 3*a_(n-1) - a_(n-2) for n≧3.
[C4](4%) Determine the a_n defined in problem B4.
[B5](14%) Let Gbe a connected graph with distinct edge weights. Without using
Kruskal's algorithm, prove that G has only one minimum-weight spanning
tree.
[B6](14%) A doubly stochastic matrix is a non-negative real matrix in which
every row and every column sums to 1. Prove that a doubly stochastic
matrix Q can be expressed Q = c1P1 + c2P2 + ... + cmPm where c1,c2,...,cm
are non-negative real nummbers summing up to 1 and P1,P2,...,Pn are
permutation matrices. For example,
┌1/2 1/3 1/6┐ 1┌1 0 0┐ 1┌0 1 0┐ 1┌0 0 1┐
│ 0 1/6 5/6│= ─│0 0 1│+ ─│0 0 1│+ ─│0 1 0│
└1/2 1/2 0 ┘ 2└0 1 0┘ 3└1 0 0┘ 6└1 0 0┘
[C6](4%) Suppose D_n is the set of all n-by-n doubly stochastic matrices.
Prove that D_n is a convex set in which an element is an extremal point if
and only if it is a permutation matrix. (Recall that D_n is convex if
λQ1 + (1-λ)Q2 belongs to D_n for any Q1,Q2 belong to D_n and 0≦λ≦1.
And Q is an extremal point of D_n if Q belongs to D_n and there do not
exist distinct Q1 and Q2 in D_n and 0 <λ< 1 s.t. Q = λQ1 + (1-λ)Q2.)