[轉錄][試題] 94下 張鎮華 圖論一 期中考
※ [本文轉錄自 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.)
--
So, if you care to find me. Look to the western sky.
As someone told me lately, "Everyone deserves the chance to fly"!
If I'm flying solo... At least, I'm flying free.
And nobody in all of Oz. No Wizard that there is or was
Is ever gonna bring me down!
~ 節錄自 Defying Gravity, Wicked
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.228.94.29
--
◢◢◣◣
■■■■
◥■■◤
◣ ║ ◢
◥◣║◢◤ ~永遠盛開的紫色鬱金香~
◥║◤
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.28.154