1 시작하면서 1.1 NIM NIM 은 일단의대상을두고두사람이번갈아가면서가져가는게임 이라했다. (p26) 정확한 수학적정의를내리지는않고 NIM 의예를몇개들면서알아보기로하겠다. 예제 1.1 (p25: 1.2.5) 16 개의동전이탁자위에놓여있다. 갑과을이게임을하는데갑부터

Transcription

1 이산수학 정주희경북대학교수학교육과 2018년 6월 17일 차례 1 시작하면서 NIM 순열과조합 순열과조합의기본 여러가지순열 조합 항계수와계차행렬 배열과분배 비둘기집의원리 포함배제의원리 분배와분할 그래프 기본개념 여러가지그래프 수형도 회로

2 1 시작하면서 1.1 NIM NIM 은 일단의대상을두고두사람이번갈아가면서가져가는게임 이라했다. (p26) 정확한 수학적정의를내리지는않고 NIM 의예를몇개들면서알아보기로하겠다. 예제 1.1 (p25: 1.2.5) 16 개의동전이탁자위에놓여있다. 갑과을이게임을하는데갑부터 시작하여번갈아한번에 4 개이하의동전을가지고갈수있다. 맨마지막동전을가지고 가는사람이이긴다고할때갑이이기기위한전략은? ( 풀이 ). 이게임의 상태 는현재까지가져간동전의개수로나타낼수있다. 상태들의전체집합은 S def = {0,..., 16} 이고 종료승리상태 는 w = 16 S 이다. 종료승리상태를만드는 사람이이긴다. 승리상태집합을 W = {16, 11, 6, 1} 로정의하면이집합은다음의성질을가진다 : (1) W 에 속하는상태를받은사람이 move 하면반드시 W 밖으로나간다. (2) W 의여집합에속하는 상태를받은사람은잘하면 W 안으로들어올수있다. (3) 종료승리상태 w 는 W 의원소이다. 처음에갑이받은상태 0 은 W 바깥의원소이므로 1 개를가져가서상태 1 W 를만들고, 이후로계속 W 의원소만상대방에게되돌려주면이긴다. NIM 게임에서의승리상태집합의성질 (1), (2), (3) 을좀더수학적으로정의하면다음과 같다. 함수 f : S P(S) 를 f(x) = {y y is obtined from x by single move} ( ) 로정의하면 (i) ( x W )(f(x) W = ) (ii) ( x W )(f(x) W ) (iii) w W ( ) 예제 1.2 위에서정의한 f에대하여 f(0), f(1), f(12) 를계산하고이들이 ( ) 를만족함을확인하여라. 예제 1.3 (p26: 게임 1) 2개의통에각각 m, n 개의동전이담겨있다. 갑과을이게임을하는데규칙은다음과같다. (1) 갑부터시작하여번갈아 1개이상의동전을가져간다. (2) 한번가져갈때는하나의통에서만가져간다. ( 한통에서 1개, 다른통에서 2개이런식으로가져갈수없다.) (3) 마지막동전을가져가는사람이이긴다. 승리전략을구하여라. ( ) 에서정의한 f에대하여 f(2, 3) 은무엇인가? 2

3 ( 풀이 ). S = {(i, j) 0 i m, 0 j n} W = {(i, i) 0 i min(m, n)} w = (0, 0) m n 이라면갑이이길수있다. f(2, 3) = {(0, 3), (1, 3), (2, 0), (2, 1), (2, 2)} 이다. 예제 1.4 (p27: 게임 2) 3 개의통에각각 n 1,..., n 개의동전이담겨있다. 규칙은게임 1 의경우와같다. ( 풀이 ). = 3, n 1 = 1 인경우를예로하여설명을시작하겠다. S = {(i, j, l) 0 i 1, 0 j n 2, 0 l n 3 } W = { x S ( m) ( x = (1, 2m, 2m + 1) or x = (1, 2m + 1, 2m) or x = (0, m, m) ) } w = (0, 0, 0) 승리집합조건 ( ) 이만족됨을확인할수있을것이다. 우리는승리집합조건을함수 f : S P(S) 를사용하여나타내었는데, 다음과같이 2 항관계 를사용하는방법도있다. 각 x, y S 에대하여 x y y is obtined from x by single move (1.1) 로정의하면 ( ) 는다음과같이쓸수있다. (i) ( x W )( y S)(x y y W ) (ii) ( x W )( y W )(x y) (iii) w W ( ) NIM 의예를하나더들어보겠다. = 3 이고 n 1 = 14, n 2 = 3, n 3 = 7 로둔다. S 와 w 는당연한방법으로정의하면되므로이들에대한정의는생략하기로하고, W 의정의는좀 복잡하다. 일단 (i, j, l) S 의각성분을 2 진법으로나타낸다. 예를들어초기상태 (14, 3, 7) 은 14 = = = 이다. 이표의오른쪽부분의 3 4 행렬에주목한다. 각열에대해서 1 의개수가짝수개인 것을짝수열, 홀수인것을홀수열이라고부른다. 위의행렬에서왼쪽에서 1 번째와 3 번째열이 홀수열이고, 2 번째와 4 번째열은짝수열이다. 이제 W 는 모든열이짝수열인상태 3

4 들의집합으로정의한다. 그러면 ( ) 의 (iii) 이만족됨은아주쉽게확인된다. (i) 이만족됨을확인해보기위하여위의예에서 14 개의동전이들어있는통에서 10 개를 꺼내보자. 결과로얻은상태 x 는다음과같다. 4 = = = x W 는쉽게확인된다. 이런승리상태에서어느통이든하나를골라몇개든동전을꺼내면 그결과로얻은상태는반드시홀수열을포함하게됨을보여야한다. 조금만생각해보면이 건지극히당연하다. 하나의행을골라그것의숫자를줄이면그행에속하는적어도하나의 열은바뀌어야한다. 0 이었다면 1 로, 그리고 1 이었다면 0 으로. 그러므로행렬에서그열은 1 이하나늘거나줄어들게되며, 따라서짝수열이었던것이홀수열로바뀌게될것이다. (ii) 가만족됨을보이는것이가장까다롭다. 홀수열이단하나만있는상태라면쉽다. 그 리고홀수열이여러개있다해도, 그모든홀수열들에서 1 을가지는행이존재한다면쉽다. 왜냐하면이런경우에는그행에속한홀수열들에있는숫자만 1 에서 0 으로바꾸면되기때 문이다. (14, 3, 7) T 에서 (4, 3, 7) T 를얻은것이바로이런경우에해당한다. (12, 3, 5) T W 같은 경우는조금더까다롭다. 12 = = = 첫째열과셋째열이홀수열인데, 이두열에서모두 1 을가지고있는행은없기때문이다. 그러나여기서잘생각해보면, 홀수열에서 1 을없애는것이아니라새로만들어내도된다! 그러므로첫째행에서첫째열은 1 을 0 으로바꾸고, 셋째열은 0 을 1 로바꾸면된다. 즉, 12 개의동전중에 6 개를꺼내서 6 개를남겨두면아래와같이 W 의원소를얻게된다. 6 = = = 이제일반적인비승리상태 x W 에서승리상태 x y W 를얻는방법을설명하겠다. x 를나타내는행렬에는반드시홀수열이있다. 홀수열중에가장왼쪽의것을골라거기서 1 을가진행을찾는다. 이행에서몇개의동전을빼서승리상태를얻을수있음을보이겠다. 홀수열들을왼쪽부터차례로 C 1,..., C m 이라하자. 그리고 C 1 은 2 d 1, C 2 는 2 d 2,..., C m 은 2 dm 에대응된다하자. 그러면 d 1 > d 2 > > d m 이성립할것이다. C 1 에서 1 인행이하나 이상있을것인데, 이행들중에서아무거나하나를골라그것을 R 이라하자. 거기서 2 d 1 동전을빼둔다. ( 빼서버리는것이아니라일단가지고있는다.) 그러면이제홀수열은하나 줄어들어 C 2,..., C m 가남아있을것이다. 이제 R 의 C 2 가 0 이라면 R 에 2 d 2 개의 개의동전을넣어 주고, R 의 C 2 가 1 이라면 R 에서 2 d 2 개의동전을더뺀다. 이제 C 2 는짝수열이되었을것이다. 이런식으로 C m 까지계속작업한다. 이러한작업은가능하다, 왜냐하면 2 d 1 은 2 d dm 보다크기때문이다. 연습문제 1.5 (13, 17, 35, 38) T 를승리상태로바꾸려면어떻게해야하겠는가? (14, 25, 40, 54) T 는어떠한가? 4

5 연습문제 무더기의동전을가지고하는 NIM 게임의상태를 {n 1, n 2, n 3 } 로나타내었을때 n 1 = 1, n 2 = 2n이면 n 3 = 2n + 1로만들면승리상태가됨을보았다. 이를짝수열의개념을사용하여설명하여라. 만일 n 1 = 2, n 2 = 4n + 1이면 n 3 를어떻게만들어야승리상태가되겠는가? n 2 = 4n + 2 이면어떻게되는가? n 1 = 3인경우의승리상태집합 W 를기술하여라. 또한 n 1 = 4, n 1 = 5 인경우의승리상태집합도각각기술하여라. 2 순열과조합 2.1 순열과조합의기본집합 X의순열 (permuttion) 은 X의모든원소를 중복과누락없이일렬로나열한것 이다. 흔히순열을순열의개수와혼동하는데이는바람직하지않다. 또한 순열의개수 를 순열의수 라고쓰는경우도흔한데이것역시피해야할표현이다. 위의정의를엄격하게하자면집합 X의순열은 X의 crdinlity, 즉원소의개수를 κ라했을때 κ에서 X로가는전단사함수를뜻한다. 우리는 κ가유한한경우, 즉 κ = n N인경우만다룰것이다. X의일부원소만취하여일렬로나열한것도순열이라한다. 개의원소를취하여일열로배열한것을 X의 -순열이라고하며수학적으로는단사함수 σ : {1,..., } X로나타낼수있다. X = {, b, c} 일때 X의 3-순열중 2개를아래에보였다. σ 1 (1) =, σ 1 (2) = b, σ 1 (3) = c σ 2 (1) = b, σ 2 (2) = c, σ 2 (3) = 순열을나타낼때위와같이쓰는것은번거롭고불편하므로그대신통상아래와같이나타 낸다. σ 1 = bc, σ 2 = bc 순열을함수로보면순열의합성등을자연스럽게생각할수있다. 이에대한내용은교재의 pp46 50 에나오는데이것은통상추상대수학 (bstrct lgebr) 에서다루는토픽이다. 원소의개수가 n 인집합을 n- 집합이라고부르기로한다. n- 집합의 - 순열의개수는 np = 개 n! {}}{ (n )! = n(n 1) (n + 1) (2.1) 로주어지며이는교재에나와있는대로점화식 없다. np 0 = 1 np = n P 1 (n ( 1)) (2.2) 공리적집합론에서 κ = {α Ord α < κ} 이다. 따라서 n = {0, 1,..., n 1} 이다. 실은 σ : {0,..., 1} X 로나타내어야하겠지만순열 σ 의정의역을 {1,..., } 로두어도안될것은 5

6 을써서 (에대한수학적귀납법을이용하여 ) 증명할수있다. 점화식 (2.2) 가성립하는이유를수학적으로엄격하게설명하기위하여는, -순열들의집합에 순열의첫원소가동일함 이라는동등관계를주어분할하면동등류들의개수가 n P 1 이고각동등류의원소의개수는 n ( 1) 로일정하다는사실을이용하면된다. 이것보다좀더흥미로운점화식으로 np 0 = 1 np = n 1 P + n 1 P 1 (2.3) 가있다. 연습문제 2.1 위의 (2.3) 이성립하는이유를설명하고, 이점화식을이용하여 (2.1) 을증명하시오. ( 힌트 ). n을포함하는순열과그렇지않은순열들로나누어생각한다. 연습문제 2.2 점화식 np 0 = 1, np = n n 1 P 1 은어떤가? 집합의 - 부분집합은그집합의부분집합으로서원소의개수가 인것을말한다. 집합의 - 조합 (combintion) 은곧 - 부분집합을뜻한다. n- 집합의 - 조합의개수는 nc = ( ) n = n! (n )!! = n P! 로주어지며 이는교재의 (53 쪽, 정리 2.2.1) 에있듯이 n P = n C! 로부터유도할수도있 고, ( 교재 88 쪽, 강의노트 12 쪽 ) 에있듯이파스칼의삼각형에서ㄱ - 법칙이성립함을이용하여 수학적귀납법으로증명할수도있다. (2.4) 순열과조합의개수에서자주등장하는팩토리얼함수 n! 은 n 이커짐에따라대단히빨리 증가하는특성을가지고있는데, 큰 n 에대하여 n! 이몇자리수인가, 즉 n! = α 10 m, α < 1 으로두었을때 m 의대략적인값을 ( 계산기를써서 ) 알아보려면스털링의공식을쓰면된다. ( 교재 42 쪽 ) n! ( n ) n 2πn e (2.5) 예제 2.3 집합 {1, 2,..., n} 의모든 r- 부분집합들을생각하자. 각각의 r- 부분집합에서선택한 가장작은원소들의가중산술평균 (weighted rithmetic men) 은 n+1 r+1 임을증명하라. (p65, #10) ( 풀이 ). 가장작은원소가 1일때, 2일때,..., n r + 1일때각각에해당하는 r-부분집합의개수는 ( ) ( n 1 r 1, n 2 ) ( r 1,..., r 1) 개일것이므로원하는평균값은 =1 (n ) r 1 ( n r) n r+1 (2.6) 식 (2.4) 는 > n 인경우에는계산할수없는데이때는 nc = 0 로두기로한다. 6

7 이된다. 위식의분자를계산하기는쉽지않은데, (p107, #16) 에서힌트를얻을수있다. n 0인임의의두정수 n, 에대하여 ( ) ( ) ( ) ( ) n n 1 n (n + 1) = ( ) n (2.7) 이성립한다. ( 교재에나온식에는오타가 2 곳있다. 교재의식은 = 1, n = 2 일때성립하지않음이쉽게확인된다.) (2.7) 을증명해보자. 파스칼의삼각형과ㄱ - 법칙을이용하기위하여위식의좌변을다음 과같이배열한다. ( ) ) ( +1. ) ( n 1 ) ( n ) ( n 1 ( +1 ) ( ) 위삼각형의맨왼쪽열의합은 n ( i ) i= = n ( i ( i=0 ) = n+1 +1) 이다. (p94, 예제 (1) 참조 ) 왼쪽에서두번째열의합은 ( ) ( n +1 이다. 그리고맨오른쪽열의합은 +1) 이다. 일반적으로 i 번째열의합은 ( ) n i+2 +1 이고 i = 1,..., n + 1이므로결국삼각형전체의합은 n +1 i=1 ( ) n i + 2 = + 1 n+1 j=+1 ( ) j = + 1 n+1 j=0 ( ) j = + 1 ( ) n 가된다. 이것으로 (2.7) 의증명이완료되었다. (2.7) 을다시쓰면 n +1 i=1 ( ) n i + 1 i = ( ) n (2.8) 이다. (2.6) 의분자는 n r+1 =1 (n ) r 1 = n r+1 i=1 i (n i r 1) 인데이것은 (2.8) 에서 n을 n 1로, 를 r 1 로바꾼것이므로 (2.8) 의우변은 ( n+1 r+1) = (2.6) 의분자 가된다. 그러면이제 (2.6) 은 ( n+1 r+1 ( n r ) ) = (n + 1)!/((n r)!(r + 1)!) n!/((n r)!r!) = (n + 1)!r! n!(r + 1)! = n + 1 r + 1 이되어원하는결과를얻는다. 예제 2.4 자연수 n, m, 에대한다음의등식을조합론적방법으로증명하라. (p65, #13.(2), Newton 의항등식 ) ( ) n m ( ) m = ( ) n ( ) n m ( 풀이 ). 좌변의조합론적의미는왕의친위병 n 명중에서 m 명의경호대원을뽑고, m 명의경호 대원중에서다시 명의최측근경호대원을뽑는방법으로생각하면된다. 우변은 n 명중에서 정의 2.11 참조. 7

8 최측근경호대원 명을먼저뽑은다음에 n 명의남은친위병중에서일반경호대원 m 명을뽑는방법의개수이다. 이둘은서로같다. 2.2 여러가지순열 조합 이절에서우리는일반화된조합, 다중집합의순열, 중복순열, 중복조합등의개념들을공부할 것이다. 집합 X 의원소들을서로구별되는, 크기가정해진 개의상자에나누어넣은것 을 X 의일반화된조합이라고한다. (p70) 이정의에서겹따옴표안의내용을좀더수학적 으로엄격하게말해보자. X = n 으로두고, 각상자의크기를 n 1,..., n 라하자. n n = n 을만족하는음아닌정수 n 1,..., n 이주어졌을때집합 {(X 1,..., X ) n(x) = n, n(x i ) = n i, n i=1 X i = X} (2.9) 의원소들을일반화된조합이라하고, 이집합의원소의개수를 ( ) n = C(n; n 1,..., n ) n 1,..., n 로나타낸다. 집합 (2.9) 의조건으로부터 X i 들이쌍마다서로소임을알수있다. ( n n 1,...,n ) 의값을구하기위하여 = 4 인경우를생각해보면 ( ) ( )( )( )( ) n n1 + n 2 + n 3 + n 4 n2 + n 3 + n 4 n3 + n 4 n4 = n 1,..., n 4 n1 n 2 n 3 n 4 = (n 1 + n 2 + n 3 + n 4 )! (n 2 + n 3 + n 4 )! (n 3 + n 4 )! (n 4 )! n 1!(n 2 + n 3 + n 4 )! n 2!(n 3 + n 4 )! n3!(n 4 )! n 4!(0)! = (n 1 + n 2 + n 3 + n 4 )! (n)! = n 1!n 2!n 3!n 4! n 1!n 2!n 3!n 4! 를얻는다. 일반적으로 ( ) n = C(n; n 1,..., n ) = n 1,..., n n! n 1! n! (2.10) 이된다. 일반화된조합에서 = 2인경우는 X1 c = X 2이고 ( ) n n 1,n 2 = n! 통상적인조합이다. 즉, ( ) ( n r = n r, n r) 이다. (p66, p73) 원소의중복을허용하는집합을다중집합이라고하고 n 1 개 n 2 개 n 개 n 1! (n n 1 )! {}}{{}}{{}}{ { 1,..., 1, 2,..., 2,...,,..., } = {n 1 1, n 2 2,..., n } 이므로이것은곧 로나타낸다. 이다중집합의순열의개수를 P (n; n 1,..., n ) 로나타내며, 이것의값은 8

9 일반화된조합의경우와같다. 즉, P (n; n 1,..., n ) = C(n; n 1,..., n ) = n! n 1! n! (2.11) 이성립한다. 다중집합의순열을응용하는대표적인문제로바둑판도로망에서의 (2차원또는 3차원 ) 최단경로문제가있다. (p74) 다중집합에서 n i 들이모두 인경우를무한다중집합이라고부르고, 이경우에는집합전체의순열보다는 r개의원소만취한순열의개수에관심을둔다. 이것의값은앞서나왔던중복순열과정확히일치한다. 즉, 무한다중집합 { 1,..., n } 의 r-순열은 n-집합의 r-중복순열이라고부르고이것들의개수는 n Π r = r n 이다. (p67) (p75) 무한다중집합 { 1,..., n } 의 r-조합을 n- 집합의 r-중복조합이라고부르고이것들의개수를 n H r 로나타내며 ( ) n + r 1 nh r = (2.12) r 이성립한다. 위의식은디오판투스방정식의해의개수를세는문제에서유도할수있다. 예제 2.5 디오판투스방정식 x x n = r, (r 0, n 1) (2.13) 의음아닌정수해의개수를구해보자. 이것은구별되는, 크기가정해지지않은상자에구별 안되는바둑알을넣는문제로생각하수있다. 즉상자 1,..., 상자 n 에넣은바둑알의개수를 x 1,..., x n 으로보는것이다. 쉽게접근하기위하여 n = 3, r = 5 인경우를생각해보자. (p74, 예제 2.3.7) 각각의해를 다음과같은방법으로하나의 {5 o, 2 +}- 순열에대응시킨다. 예를들어해 = 5 는 ooo + o + o에대응되고, 해 = 5는 + oo + ooo로대응되게하는것이다. 이러한순열의개수는 P (7; 5, 2) = ( ) 이다. 우리의다중집합에는 o가 바둑알의개수 만큼있고, + 가 변수의개수 1 만큼있다. 그러므로일반적인경우에해의수는 ( ) ( ) n + r 1 r + (n 1) P (r + (n 1); r, n 1) = = r n 1 이다. ( ( ) n+r 1 n 1 은 r이변하여도 choose의아랫수 가일정하다는장점이있다.) nh r 은무한다중집합 A def = { 1,..., n } 의 r-조합의개수로정의되었다.(p75) A x 1 개 x n 개 {}}{{}}{의 r-조합은 { 1,..., 1,..., n,..., n }, (x x n = r) 형태이므로이러한것들의개수는 디오판투스방정식 (2.13) 의해의개수와일치한다. 디오판투스방정식의정의는유일하지않다. 정수해만찾는방정식을뜻하기도하고, 정수계수를가지는다항방정식 (polynomil eqution) 을뜻하기도한다. 여기서는후자의의미를사용하겠다. 9

10 위의논의에서 1대1 대응 의개념을여러번사용한것에주목하자. 우리는무한다중집합의 r-조합을디오판투스방정식의해와대응시키고, 다시이를다중집합의순열에대응시켰다. 좀더엄격하게말하자면 A = 무한다중집합의 r-조합들의집합 에서 B = 디오판투스방정식의해들의집합 으로가는전단사함수를구성하였고, 다시 B에서 C = 다중집합의순열들의집합 로가는전단사함수를구성하였다. 경우의수를센다는것은결국어떤집합의원소의개수를알아내는것이며, 집합 A의원소의개수는그것과 1대1 대응되는다른집합 B의원소의개수와같으므로, A의원소를세는것보다 B의원소의개수를세는것이쉽다면, 이러한 B를찾는것이우리가할일이된다. 예제 2.6 (p79, #2.3.13) 11권의책이책꽂이에나란히일렬로꽂혀있다. 이중 4권을뽑되뽑힌책들은서로인접하지않도록 ( 않았었도록 ) 하는방법의개수를구하여라. ( 풀이 ). 교재와다른각도에서접근하겠다. 11권의책들을집합 {1, 2,..., 11} 로나타내고뽑힌 4권의책들을 {1, 3, 8, 10}, {4, 7, 9, 11} 등의부분집합으로나타내기로한다. 그렇다면구하는답은아래의집합의원소의개수이다. {(x 1, x 2, x 3, x 4 ) 1 x 1, x 4 11, x < x 2, x < x 3, x < x 4 } (2.14) y 1 = x 1, y 2 = x 2 1, y 3 = x 3 2, y 4 = x 4 3 으로두면집합 (2.14) 는전단사함수 (x 1, x 2, x 3, x 4 ) (y 1, y 2, y 3, y 4 ) 에의하여집합 {(y 1, y 2, y 3, y 4 ) 1 y 1 < y 2 < y 3 < y 4 8} (2.15) 과 1 대 1 대응됨을알수있다. 그리고집합 (2.15) 는다시아래의집합과 1 대 1 대응된다. {{y 1, y 2, y 3, y 4 } 1 y 1, y 2, y 3, y 4 8, } (2.16) 그리고 (2.16) 의원소의개수는다름아닌 ( 8 4) = 70 이다. 연습문제 2.7 중복조합들의개수공식 n H r = n+r 1 C r 을아래의집합 A 와 1 대 1 대응되는집합 B 를찾아원소의개수를셈으로써얻어보라. A def = {(x 1,..., x r ) 1 x 1 x 2 x r n} 연습문제 2.8 다음의조건을만족하는함수 f 들의개수를구하여라. f : {1, 2, 3, 4, 5} {1, 2,..., 19} f(n + 1) f(n) + n, for n {1, 2, 3, 4} 연습문제 2.9 우리는 P (n; n 1,..., n ) 과 C(n; n 1,..., n ) 가유도과정은서로다르지만값은같음을안다. 다중집합의순열들의집합으로부터일반화된조합들의집합으로가는일대일대응함수를기술하여라. 파라메터 n, n 1,..., n 는물론동일하다고가정한다. ( 힌트 : C(8; 3, 2, 3) = 10

11 C 로두었을때 C 의원소중하나를예로들면 ({1, 3, 5}, {6, 8}, {2, 4, 7}) 이있다. P (8; 3, 2, 3) = P 로두었을때 P 의원소하나만예로들어보라.) 연습문제 2.10 답을식으로나타낼경우, 그식은 P, C, H, 등을사용할수있다. (1) p84, #1, #2 (2) p84 #3 ( 힌트 : p85, #16 을먼저푼다음에할것. 책의해답에서 r 의의미는무엇인가?) (3) 01 이꼭 m 번나타나는길이 n 의 {0, 1}- 수열의개수를구하라. (p84, #8, 책의해답은 틀림. n = 3, m = 1 인경우를생각해보라.) ( 힌트 ). 문제에서말하는수열들은 0- 블럭의시작위치와 1- 블럭의시작위치로써결정 된다. 수열의맨왼쪽위치를 1 이라하고맨오른쪽위치를 n 이라하자. 수열이 0 으로 시작하면 2m 개의위치를지정해야하고, 1 로시작하면 2m + 1 개의위치를지정해야 한다. 1 로끝나는경우와 0 으로끝나는경우로또나누어생각해도되겠지만, 위치 n+1 도존재하는것으로생각하면이렇게경우를나눌필요가없어편리하다. (4) 1, 2,..., 8 중 5 개를 1 번씩사용하여만들수있는 5 자리의정수를작은것부터크기순 서대로나열할때 은몇번째수인가? (p85, #9, 책의해답은틀림.) ( 힌트 ). 1 로시작하는모든수는 앞에나온다. 21, 22, 23, 24 로시작하는모든수는 앞에나온다. 이런식으로계속한다. (5) p85, #15, #16 (6) p86, #17 ( 책의해답에는오타가있음. 첨수 의의미를생각해보라.) ( 힌트 ). x 1 + x 2 + x 3 = 로두고각 = 0,..., 7 에대하여부등식 x 4 + x 5 + x 6 20 를생각한다. 이부등식의음아닌정수해의개수는 y + x 4 + x 5 + x 6 = 20 의음아닌 정수해의개수와같다. (7) p86, #20 ( 힌트 : 쉬운문제이다. 오타수정 : λ = λ λ n 이라고할때,.. ) (8) p86, #21 ( 힌트 : 이문제는 p79 의예제 과본질적으로같다. 책의해답에는오타가 있음.) (9) p86, #22 ( 힌트 : 연속한 m 개의정수의곱은 m! 의배수라는사실을이용한다. 이사실 및이사실의증명은암기할가치가있다.) m fctors m fctors {}}{{}}{ ( + 1) ( + m 1) = ( + m 1) = +m 1 P m = +m 1 C m m! (10) p86, #23 ( 힌트 : 하나의 방법 은 r,l,u,d 로이루어진길이 2n 의수열에대응된다. 이 수열에서 r 의개수 p 는 l 의개수와같고 u 의개수와 d 의개수는둘다 n p 가되어야 한다. p = 0, 1,..., n 일때의답을구하여모두더한다.) 11

12 2.3 2항계수와계차행렬정의 2.11 파스칼의행렬은오른편그림과같이 ( ) n 들의값을배열하여행렬로만든것이다. n은맨 위쪽행의 0 에서시작하여아래쪽행으로가면서 증가하며, 는맨왼쪽열의 0 에서시작하여오른 쪽으로가면서증가한다. n < 인경우에는행렬의 원소는 0 이므로, 원소가양수인부분만보면삼각 형이되는데이삼각형을파스칼의삼각형이라고 한다. (p88) 맨왼쪽열과대각선에놓인쎌들의값은모두 1임에주목하라. 그리고공식 ( ) ( n = n 1 ) ( 1 + n 1 ) 는이그림에서ㄱ-법칙으로암기하면편하다. ( n ) 는 2항정리 (x + y) n = (x + 1) n = n ( n n ( n =0 =0 ) x y n, (2.17) ) x. (2.18) 에서우변의다항식의항들의계수로나타나므로 2 항계수라고하기도한다. 2 항계수를포함 하는공식들중에중요한것들을알아보자. 예제 2.12 (1) n ( n =0 ) = 2 n (p91, 예제2.4.4) : (2.18) 의 x에 1을대입. (2) ( n ) ( odd = n even ) = 2 n 1 (p92, 예제2.4.5.(1)) : (2.18) 의 x에 1을대입하면간 def 단히증명된다. 또하나의증명방법이있는데이것은 X n = {1,..., n} 의부분집합중 원소의개수가짝수인것을 짝부분집합, 원소의개수가홀수인것을 홀부분집합 이 라고하고, 짝부분집합들의개수를 f(n), 홀부분집합들의개수를 g(n) 이라고둔다음, f(n) = g(n) = 2 n 1 임을 n 에대한수학적귀납법으로보이는것이다. 나머지부분은 ( 오타가많지만 ) 교재에나와있으며여기서는생략한다. (3) n =0 ( n ) 2 = ( 2n n ) (p92, 예제 (2)) : 이것은 Vndermonde 항등식에서 m = n 인경우이다. ( n n ) = ( n ) 임을이용한다. (4) n =0 ( n ) = n2 n 1 (p94, 예제 (1)) : (2.18) 의양변을 x 에대하여미분하고 x = 1 을대입한다. (5) n =0 2( n ) = n(n + 1)2 n 2 (p94, 예제 (2)) : (2.18) 의양변을 x 에대하여미분한식의양변에 x 를곱한다음한번더미분한다. 그리고 x = 1 을대입한다. (6) 0 < p < 1, q = 1 p 일때 n =0 ( n ) p q (n ) = np : (px + (1 p)) n 에대한 2 항정리를사용한다. 12

13 (7) 0 < p < 1, q = 1 p일때 n =0 ( np)2( ) n p q (n ) = n =0 2( n ) p q (n ) (np) 2 = npq : 위에나온예들의증명을잘응용한다. 예제 2.13 p94, 예제 ( 책의 (2), (3) 에는오타있음.) (1) (2) (3) n i=0 ( ) i = ( ) n ( ) ( ) n + i n = i i=0 n ( ) n i = g n 이라하면 (g n ) n 은피보나치수열이다. i i=0 위의 3 공식들은모두파스칼의삼각형을그리고ㄱ - 법칙을적용하여증명할수있다. 예제 i=0 3 j=0 ( i j) 의값을구해보자. (p97, 예제 2.4.8) 우선이것은 의순서를뒤바꾸어얻은 3 j=0 5 i=0 ( i j) 과값이같다는것을알아야한다. ( 일반적으로 2 개의 이있을때첨수변수의구간이상수들만으로이루어져있으면 의 순서를바꾸어도값이변하지않는다.) 이제예제 2.13.(1) 을이용하면답이쉽게구해진다. 단평 2.15 아래의토픽은 2 학기에다루게될것이며일단은생략한다. (1) p97: 이항계수의확장, 예제 (2) p99: 정리 ( 뉴턴의 2 항정리, 오타있음.) (3) p101: 예제 연습문제 2.16 n ( )( ) ( ) m n m + n (1) = 를증명하라. (p104, #3.(6). 힌트 : Vndermonde의항등식 ) i + i n i=0 (2) n ( n+1 ) =0 9 n 가 11의배수가되기위한자연수 n에대한조건은? (p105, #9) (3) ( ) n 0 1 n ) 2( n ) 3( 2 + ( 1) n 1 n n+1( n) 의값은? ( 힌트 ). (2.18) 의양변을부정적분하고 x = 1을대입한다. 단, 적분상수를잊지말아야한다. (p106, #11.(2)) 정의 2.17 수열 = ( 0, 1, 2,...) 이주어졌을때, 이것의계차수열은 = ( 0, 1, 2,...), where i = i+1 i 13

14 로정의된다. 이제귀납적으로 1 =, n+1 = ( n ), (n = 1, 2,...) 로정의하고 n, (n = 0, 1,...) 들을행으로가지는행렬을 의계차행렬이라하고아래의 그림과같이나타낸다. 계차행렬의 0 열에나타나는수열 d def = (d 0, d 1,..., d n ) def = ( 00, 10, 20,...) 를 의쌍대수 열 (dul sequence) 이라한다. 정리 2.18 수열 의제 n 항 n 은그것의쌍대행렬과파스칼의행렬의제 n 행과의내적이다. 즉, n = 이성립한다. ( ) n d ( ) n d ( ) n d ( 증명 ). 교재의 p110, #2.5.1 에나와있다. ( ) n d n (2.19) n 따름정리 2.19 { n } n 의쌍대수열이유한수열 (d 0, d 1,..., d, 0, 0,...) 이고 d 0 라면일반항 n 은 n 에대한 차다항식이다. 정리 2.20 (p113, #2.5.4) 수열 = ( 0, 1,...) 의쌍대수열을 d = (d n ) n 라놓았을때각 n = 0, 1,... 에대하여 n ( ) ( ) n + 1 n + 1 = d 0 + d =0 이성립한다. ( 증명 ). 의부분합 n =0 = s n 으로두고 x = (x 0, x 1,...) = (0, s 0, s 1,...) ( n ) d ( ) n + 1 d n (2.20) n + 1 로두면 는 x 의계차수열이다. x 의쌍대수열은 (0, d 0, d 1,...) 이므로정리 2.18 에의하여 ( ) ( ) ( ) ( n + 1 n + 1 n + 1 n + 1 x n+1 = 0 + d 0 + d 이다. 그런데 s n = x n+1 이므로우리가원하는 (2.20) 을얻는다. ) d ( ) n + 1 d n n

15 ~ 길이가 정리 2.21 수열 ~의 일반항 n 이 n에 대한 -차 다항식이라면 이 수열의 쌍대수열 d는 + 1이다. 즉, dn = 0, for n = + 1, + 2,...를 만족한다. (이것은 따름정리 2.19의 역이다.) (증명). 이것은 (p114, #2.5.5)의 따름정리이다. 예제 2.22 Pn =0 4을 n의 식으로 나타내어라. (p115, #2.5.6) 배열과 분배 비둘기집의 원리 정의 3.1 n+1 마리의 비둘기를 n 개의 비둘기집에 넣으면 2마리 이상 들어간 집이 하나 이상 존재한다. 이 사실을 비둘기집의 원리(Pigeonhole principle)라 한다. 연습문제 3.2 비둘기집의 원리를 증명하여라. (힌트: 수학적귀납법) (정리 3.1.6) (p144) 일단의 실수들 중에는 그들의 산술평균 이상의 수가 존재한다. (증명). 주어진 일단의 실수 x1,..., xn 의 평균을 라 하면 = x1 + + xn n 이다. 모든 xi 가 미만이라고 가정하면 n = x1 + + xn < + + = n 라는 모순을 얻는다. 연습문제 3.3 (1) 비둘기집의 원리(정의 3.1)를 수학적 귀납법을 쓰지 않고 증명하여라. (2) 일단의 실수들 중에는 그들의 산술평균 이하의 수가 존재함을 증명하여라. 비둘기집의 원리는 이해하기는 대단히 쉽지만 활용하기는 쉽지 않을 수 있다. 무엇을 비 둘기로 보고 무엇을 비둘기집으로 보느냐가 관건이다. 연습문제 3.4 (p151, #13) 한 변의 길이가 1인 정삼각형의 내부에 있는 점들에 대하여 다음을 증명하여라. (1) 17개의 점 중에는 거리가 1 4 이하인 두 점이 존재한다. (힌트: 예제 p142) (2) 33개의 점 중 적어도 세 점은 반지름이 3 20 인 원의 내부에 있다. (힌트: 16개의 작은 정 삼각형의 외접원의 반지름은 얼마인가?) 연습문제 3.5 (p151, #14) 한 변의 길이가 1인 정사각형 내부에 있는 9개의 점 중 적어도 세 점은 넓이가 1 8 이하인 삼각형의 꼭짓점이 됨을 증명하여라. 단, 어느 세 점도 한 직선 위에 있지 않다고 한다. (힌트: 4개의 비둘기집을 만들어 보자.) 15

16 연습문제 3.6 (p152, #15) 다음을증명하여라. (1) 가로, 세로의길이가각각 5, 6인직사각형의내부에있는 8개의점중에는거리가 10 이하인두점이존재한다. ( 힌트 : 직사각형을 7개의구역으로나누어야한다. 각구역에서두점간의거리의최댓값이 10 이하가되도록한다.) (2) 좌표평면상의 5개의격자점중에는, 그점들을양끝점으로하는선분의중점도격자점인두점이존재한다. ( 힌트 : 1 4개의조각으로이루어진격자점들의 분할 을생각해야한다. 2 선분의중점의 x-좌표가정수이기위한조건은? y-좌표에대한조건은?) (3) 평면위에있는임의의볼록오각형에대하여 ABC 36 o 인세개의꼭짓점 A, B, C 가존재한다. ( 힌트 : 그림을그려보라. 별모양도형의꼭짓각들의합이 180 o 임을이용한다. 또는, 인접한두변을품는삼각형의꼭짓각중에서찾으려면, 이때는내각중에 540 o /5 = 108 o 이상인것이존재한다는것을이용한다.) 연습문제 3.7 집합 X = {0, 1, 2,..., 2n} 의임의의 (n + 2)-부분집합의원소중에는합이 2n인두수가존재함을증명하여라. X에서 0을빼면문제가어떻게달라질까? ( 힌트 : p142, 예제 3.1.2, p150 #3) 연습문제 이하의자연수중에서 n개를택하면그중하나는다른하나의약수임이보장되는최소의 n을구하여라. ( 힌트 : p150 #1) 연습문제 3.9 (p150, #5) 다음을증명하여라. (1) 13개의정수중에는차가 12의배수가되는두수가존재한다. ( 힌트 : 12로나눈나머지들을 12개의비둘기집으로본다.) (2) 5개의정수중에는합이 3의배수인세수가존재한다. ( 힌트 : 법 3으로생각한다. 4개의정수중에는합이 3의배수인세수가존재하지않을수있음을보인다.) (3) 100 이하의자연수 53개중에는 1 차가 12가되는두수는존재하지만, 2 차가 11이되는두수가반드시존재하지는않는다. ( 힌트 : 100 이하의자연수중에 12로나눈나머지가 1인 6개의숫자중에는차이가 12인두수가존재한다. 나머지가 2, 3, 4일때도마찬가지. 나머지가 5 이상또는 0인경우에는 5개의숫자로충분하다. 2에대한답은 1 11, 23 33,...) (4) n 2일때 (n + 2) 개의 3n 이하의자연수중에는그차가 n보다크고 2n보다작은두수가존재한다. ( 힌트 : n + 1로나눈나머지가 로동일한두수가존재한다. 이두수의차이가 n+1이면문제가없다. 와 2n++2의두수가뽑혔을경우만해결하면된다. 뽑힌수중에 +3,..., 2n+ 1가하나라도있으면문제가없다. +1, +2, 2n+, 2n++1 중에기껏해야 2개밖에뽑힐수없다. 이제남은 1,..., 1, 2n + + 3,..., 3n을다뽑아도 n 3개다. 지금까지총 n + 1개를뽑았는데마지막남은 1개는어디서도뽑을수없다.) (5) 2n 이하인 (n+1) 개의서로다른자연수중에는서로소인두수가존재한다. ( 힌트 : 차이가 1인두수는서로소이다. 왜냐하면두자연수의선형조합은최대공약수의배수이기때문이다.) 16

17 (6) 1, 4, 7,..., 100에서임의로택한 20개의수중에는그합이 104인수의쌍이적어도 2개존재한다. ( 힌트 : 연습문제 3.7) 연습문제 3.10 (p150, #6) n 2 + 1개의서로다른수로이루어진수열은길이 n+1인증가또는감소하는부분수열을가짐을증명하여라. ( 힌트 : 1,..., n 2 +1이길이 n + 1인증가하는부분수열을가지지않는다고가정한다. 각 = 1,..., n 2 + 1에대하여 에서시작하는가장긴증가하는부분수열의길이를 m 라하면 m n이다. m 의값이같은 를 n + 1개취할수있다. 1,..., n+1 은감소수열이다.) 연습문제 3.11 (p151, #8) 임의로주어진서로다른 11개의정수중에는적당한연산부호로연결하면그결과가 1155의배수가되는 8개의정수가존재함을증명하여라. ( 힌트 : 1155 = 이므로 11개의정수중에 2개를취하여차이가 3의배수가되도록할수있고,...) 연습문제 3.12 (p151, #10) 10시간동안 45m를걸어간어떤사람이첫한시간에는 6m를걷고마지막한시간에는 3m를걸었다고한다. 이사람은어떤연속된 2시간동안 9m 이상걸었음을증명하여라. ( 힌트 : 원래는 ( i 9)(x i +x i+1 = 6) 을증명하는문제인데이보다조금쉬운문제인 ( i 4)(x 2i + x 2i+1 = 6) 을풀도록한다.) 연습문제 3.13 (p151, #11) 어떤운동선수는매일한번이상, 일주일에 12번이하의연습을 12 주간 (84일) 계속하였다고한다. 이선수가곡 23회연습한연속된몇날이있음을증명하여라. ( 힌트 : p143, 예제 이것과예제 3.1.3의차이점에대해서말해보라.) 연습문제 3.14 (p151, #12) 원탁에 10명의손님의자리가명찰과함께놓여있다. 10명의손님이명찰을확인하지않고아무렇게나앉았는데, 제자리에않은손님이 1명도없었다. 이때명찰이놓인원탁을적당히회전시키면적어도 2명의손님이제자리에앉게됨을보여라. ( 힌트 : p145, 예제 3.1.7과비슷하나조금쉽다.) 3.2 포함배제의원리 이절에서사용하는모든집합은유한집합이다. 집합 X 의원소의개수를 X 로나타내기로한다. 우리는다음의사실을잘알고있다. A B = A + B A B, A B C = A + B + C A B B C C A + A B C. 포함배제의원리는위의사실을아래와같이일반화한것이다. I = {1, 2,..., n} 이라하고각 i I에대하여집합 A i 가존재할때 A i = i I n ( 1) 1 β, where =1 β = J I, J = j J A j. (3.1) 17

18 즉, β 1 = A 1 + A A n, β 2 = A 1 A A n 1 A n, β 3 = A 1 A 2 A A n 2 A n 1 A n, 이다. 일반적으로 β 는 ( n ) 개의항의합임을알수있다. 그리고거의모든문제에서이항들의값은동일하다. 예제 3.15 (p160, 3.2.6) n- 집합에서 r- 집합으로가는전사함수의개수를 T (n, r) 이라했을때 이다. T (n, r) = r ( ) r ( 1) (r ) n (3.2) =0 ( 풀이 ). {1,..., n} 에서 {1,..., r} 로가는함수의개수는, f 에아무런조건이없다면 r n 이다. f가전사함수라는것은모든 i = 1,..., r에대해서 f가 i를함수값으로가진다는것이므로, 이러한 f들의집합을 B i 라하면 r i=1 B i 가곧우리가원하는 T (n, r) 이될것이다. 문제는 r i=1 B i 의값을구하기가쉽지않다는것이다. 이문제를해결하기위하여각 i = 1,..., r에 def 대하여 A i = Bi c로두면 r r B i = i=1 i=1 A c i ( r ) c = A i = r n r A i i=1 이다. 여기서 r i=1 A i 의값을구할때포함배제의원리를사용하게된다. (3.1) 에서의 β 는각 = 1,..., r 에대하여 ( r ) (r ) n 이므로 를얻는다. T (n, r) = r n r ( ) r ( 1) 1 (r ) n = =1 i=1 r ( ) r ( 1) (r ) n =0 {1,..., n} 의순열 σ 중에 i. σ(i) i 를만족하는것들의개수를 n- 번째교란수라고하고 D n 으로나타낸다. 정리 3.16 (p162, 3.2.7) n ( 1) D n = n!! =0 (3.3) ( 풀이 ). {1,..., n} 의순열 σ 중에 σ(i) = i 를만족하는것들의집합을 A i 라하고 n! n i=1 A i 18

19 를포함배제의원리를사용하여계산하면된다. 각 = 1,..., n 에대하여 이므로 β = 가된다. D n = n! ( ) n (n )! = n!! ( 1) i=1 1 n! n! = n! ( 1)! =0 연습문제 3.17 p166, #1, #2, #4 연습문제 3.18 (p166, #5) 집합 X 에대해서 σ(x) def = P(X) 로정의한다. X = Y = 100, σ(a)+σ(b)+σ(c) = σ(a B C) 일때 A B C 의최솟값을구하여라. ( 힌트 : 2 A +2 B + 2 C = 2 A B C, C = 2 A B C. 그런데일반적으로 2 x + 2 y = 2 z 이면 x = y = z 1 이 성립함. C = 101, A B C = 102. A B C 에서 C 의원소가아닌것은단하나뿐임.) 연습문제 3.19 (p166, #7) 갑식이는어느일주일동안매일 8 명의친구중 2 명씩을저녁식사 에초대한다는계획을세웠다. 8 명모두를적어도한번이상올수있도록초대하는방법의 개수를구하여라. ( 힌트 : 각 = 1,..., 7에대하여친구 명을빼고초대하는방법의개수를구한다음전체방법의개수 ( 8 7 2) 에서이들의합집합의원소의개수를빼면된다. 특정한친구 명을초대하지않는방법의수는 ( ) 이다. 그리고친구 명을선택하는방법의수는당연히 ( 8 ) 이다. 이방법의정당성을확인하기위하여답을다른방법으로구하여맞춰보아야한다. 초대기간을 4일로줄이면다른방법으로구할수있을것이다. 또는친구가 4명이고 3 일간초대하는경우를생각해보라.) 연습문제 3.20 (p166, #8) 1 학년부터 6 학년까지한학년에한반씩 6 개반과, 한반에한명씩 6 명의교사로구성된어느초등학교가있다. 다음해에학생들이한학년씩진급을하는데, 각 학년의학생들이모두새로운담임을만나도록교사를배정하는방법의수를구하여라. ( 힌트 : σ(i) i + 1 for i = 1,..., 5. 6 학년담임선생님은어떤학년을맡게되든상관없음.) 연습문제 3.21 (p166, #9) 1 에서 9 까지의자연수를배열하는데, 1 이 2 의오른쪽에또는 2 가 3 의오른쪽에또는 3 이 4 의오른쪽에있도록배열하는방법의수를구하여라. 단, 여기서 오 른쪽 이라고해서인접할필요는없다. ( 힌트 : 3 개의조건중특정한하나의조건을만족하는 배열의수 = 9! 9! 2!. 특정한두조건을만족하는배열의수 = 3!.) 연습문제 3.22 (p167, #10) (1) 1 어떤모임에온 n쌍의부부가서로동시에악수하는방법의수를구하여라. 2 ( )( 2n 2n 2 ) ( ) 2 는왜틀린답인지설명하여라. ( 힌트 : 1 첫사람이악수할수있는사람은 2n 1. 남은사람들중에첫사람이악수할수있는사람은 2n 3. 2 중복이 있다. ) 19

20 (2) n쌍의부부가서로동시에악수하되어느누구도자신의배우자와는악수하지않는방법의수를구하여라. ( 힌트 : 포함배제의원리사용 ) 연습문제 3.23 (p167, #12) 디오판투스방정식 x 1 + x 2 + x 3 + x 4 = 25, x 1 > x 4 의음아닌정수해의개수를구하여라. ( 힌트 : = 0, 1,..., 12에대해서 x 1 = x 4 = 인해를제외한다.) 연습문제 3.24 (p168, #17) 0, 1,..., 9의순열중첫번째숫자는 1보다크고마지막숫자는 8 보다작은것의개수를구하여라. ( 힌트 : 두집합의교집합의원소의개수를구하는문제이다. 포함배제의원리 ( 혹은드모르강의법칙 ) 를사용한다.) 3.3 분배와분할 0 n 라할때, n 개의대상을 개의상자에넣는방법으로다음과같은 8 가지경우를생각 할수있다. 이경우들을 대상 - 상자조합 이라고부르기로한다. 맨오른쪽열에보인 방법의 수 에대하여는이섹션에서상세히설명할것이다. 대상구별상자구별빈상자없음방법의수 T (n, ) n S(n, ) i=0 S(n, i) H n H n p(n, ) i=0 p(n, i) 경우의수를구하는문제에서대상을구별하는지그렇지않은지가명시되어있지않은 경우가많다. 명시되어있지않은경우에는사람, 카드, 편지등은구별되는것이고바둑돌, 구슬등은 ( 색깔이같다면 ) 구별되지않는것으로보는것이보통이다. 상자는방, 우체통등대부분의경우구분이되는것으로보며, 예외로구분되지않는것 으로보는상자는 그룹 이다. 8 가지의대상 - 상자조합중에서먼저 111 과 110 에대해서생각해보자. 대상을상자에넣 는방법의수를알고자할때, 대상과상자는그것들의내용은상관없이개수만알면되므로 대상들을 {1,..., n}, 상자들을 {1,..., } 로둔다. 대상을상자에넣는것을함수 f : {1,..., n} {1,..., } 로보고논의하기로한다. 즉, 대상 x를상자 y에넣는것을 f(x) = y로생각한다. 그리고이러한함수의개수가몇개인지를알아내는것이우리가할일이다. 대상과상자의차이는, 하나의대상은단하나의상자에들어가야하지만, 하나의상자는여러개의대상을받아들일수있다는것이다. 이것이바로함수의개념과일치한다. 함수의값 f(x) 는 x가정해지면이것에따라서유일하게정해지지만, 함수의값이 y라하면 ( 즉, 20

21 공역의원소를하나취하여그것을 y 로나타낸다면 ) f(x) = y 가되는 x 들의집합을 f 1 (y) {1,..., n} 로나타내기로할때, f 1 (y) 는 2 n 개의부분집합중어떤것도될수있다는것이다. 빈상자를허용하지않는다는것은모든 y에대해서 f 1 (y) 라는뜻이며, 이는곧 f 가전사함수라는것을의미한다 이것은대상-상자조합 111에해당한다. 빈상자를허용하는것, 즉대상-상자조합 110은 f 1 (y) 에대해아무런조건이없다는뜻이다. f에대한조건은정의역이 {1,..., n} 이고공역이 {1,..., } 라는것뿐이다. 이러한함수 f는유한열 f(1), f(2),..., f(n) 으로나타낼수있다. 각 f(i) 들은 1,..., 중어느하나의값을가진다. n = 1이라면이러한 f는 개존재한다. 길이가 n + 1인유한열은길이 n의유한열에 개의가능한값중에서어느하나를골라덧붙이는것이므로, 이러한유한열의개수는 ( 길이 n의유한열의개수 ) 가될것이다. 길이가 n인유한열의개수는귀납가설에의하여 n 이므로이제수학적귀납법에의하여 110 대상-상자조합에서 방법의수 는 n 이됨을알수있다. 111 대상-상자조합에서의방법의수 T (n, ) 는포함배제의원리를이용하여 (3.2) 에서알아낸바있다. 이제 101 조합, 즉대상은구별되고, 상자는구별되지않으며빈상자는없는경우에대하여알아보자. 이때의 방법의수 를 S(n, ) 로나타내고제2종스털링수라고부른다. 그리고이렇게대상을상자에넣는것을 그룹으로나누었다 고말한다. 왜냐하면그룹은통상서로구별하지않기때문이다. ( 그룹 은비어있지않고구별되지않는상자를뜻한다고보면된다. 물론그룹은그안의원소들에의하여는구별된다.) S(n, ) 는 111 조합에대한답, 즉 T (n, ) 를이용하여쉽게구할수있다. 전사함수 f : {1,..., n} {1,..., } 가주어지면 f 1 (1) 은상자1에넣고, f 1 (2) 는상자2에넣고,... 이런식으로상자에넣는다. 이제상자에붙은번호 1,..., 를모두지워버려 ( 그리고상자들의위치를뒤섞어놓아 ) 상자들을구별하지않기로한다. 그러면원래는다른함수였으나이제는구별되지않는것들이생길것인데, 정확히! 개의 ( 원래는달랐던 ) 함수들이서로구별되지않을것이다. 구별되지않는함수 들을분할이라고한다. 역으로생각하면, {1,..., n} 를 개의그룹으로나눈뒤에, 각그룹에번호를 1,..., 로주고그룹 i에들어있는 x들에대하여 f(x) = i로줌으로써전사함수 f를만들어낼수있다. 그러므로아래의식을얻는다. S(n, ) = T (n, )! (3.4) 제 2 종스털링수 S(n, ) 를 T (n, ) 를사용하지않고직접얻는방법이있다. 이방법은ㄱ - 열법칙 이라고부르며, 이것으로닫힌식은얻을수없지만점화식을얻을수있다. 21

22 ㄱ - 열법칙은아래의식을말한다. S(n, ) = S(n 1, 1) + S(n 1, ) ( 열 ) 그림에서는 ( 가 ) + ( 나 ) ( 열번호 ) = ( 다 ) 를뜻한다. ( 열 ) 이성립하는이유는 n이혼자서그룹을이루는경우와그렇지않은경우로나누어생각하면알수있을것이다. 다음의정리는스털링에의하여밝혀진것으로증명없이명제만제시한다. 정리 3.25 n x n = S(n, )[x] =0 제2종스털링수를알았으니이제는제1종스털링수에대하여알아보자. 이수는 s(n, ) 로나타내며 n명을 개의원탁에않히는방법의수를뜻한다. s(n, ) 에대한점화식은ㄱ-행법칙에의하여얻을수있다. ㄱ-행법칙은아래의식을말한다. s(n, ) = s(n 1, 1) + (n 1) s(n 1, ) ( 행 ) 그림에서는 ( 가 ) + ( 나 ) ( 행번호 ) = ( 다 ) 를뜻한다. ( 행 ) 이성립하는이유는 n이혼자서한원탁을독차지하고앉는경우와그렇지않은경우로나누어생각하면알수있을것이다. 22

23 정리 3.26 n [x] n = ( 1) n+ s(n, )x =0 이제 4 번째대상 - 상자조합 100, 즉 n 명을몇개의그룹으로나누는방법의수에대해서 알아보자. 이수는 B n, 벨수라고하는데 S(n, ) 를이용하여아주쉽게구할수있다. n 명을 개의그룹으로나누었다면 는 1 부터 n 사이의자연수가될것이므로 B n = n S(n, ), n = 0, 1,... =0 = 0 를넣은것은 B 0 = 1 로정의했기때문이다. n > 0 인경우는 S(n, 0) = 0 이므로아무문제 없다. B n 은 n명을 n개이하의그룹으로나누는방법의수인데, 우리가대상-상자조합 100 에서우리가원하는것은 n명을 개이하의그룹으로나누는방법의수이므로 i=0 S(n, i) 가된다. 지금까지는대상이구별되는경우에대하여공부하였다. 이제대상이구별되지않는경우 에대해서알아보자. n 개의바둑돌을구별되는 개의통에넣는방법의수는디오판투스방정식의음아닌해의 개수와같다. x x = n (3.5) x i 를 i번째통에들어간바둑돌의개수로보는것이다. 이때해의개수가 H n 임은앞서구한바있다. x i = 0를허용하는것은빈상자가있을수있다는뜻이다. 즉, H n 은대상-상자조합 010에서방법의수이다. 011 조합, 즉빈상자를허용하지않는경우는 (3.5) 에서 x i > 0 조건을만족하는해만인정하는것으로보면된다. x i 1 = y i 로두면 (3.5) 는 y y n = n 가되므로, 이때구하는방법의수는 H n 가됨을쉽게알수있다. 이제 n개의바둑돌을 개의그룹으로나누는대상-상자조합, 즉 001에대해서방법의수를구해보자. 이방법의수는 p(n, ) 로나타내며 n의 -분할수 (prtition number) 라고한다. p(n, ) 는자연수 n을 개의자연수의합으로나타내는방법의수와같다. 예를들면 7을 3개의자연수의합으로나타내는방법은 7 = = = = 의 4 가지이므로 p(7, 3) = 4이다. 디오판투스방정식에서는 (x 1, x 2, x 3 ) = (5, 1, 1) 과 (x 1, x 2, x 3 ) = (1, 5, 1), (x 1, x 2, x 3 ) = (1, 1, 5) 를 3개의해로구별하여본다는점이지금과다르다. p(n, ) 는 n > 0인경우에대해서만생각한다. 우선 p(n, n) = p(n, 1) = 1임을알수있다. > n > 0인경우에는 p(n, ) = 0로둔다. 그리고 n > > 0에대한 p(n, ) 는아래정리의점화식을사용하여구할수있다. 23

24 정리 3.27 p(n, ) = p(n, 1) + p(n, 2) + + p(n, ) (3.6) ( 증명 ). n개의바둑돌을구별이안되는 개의통에빈통이없도록넣는방법의수를구하면된다. 빈통을없애기위하여먼저각통에 1개씩넣는다. 그리고남은 n 개의바둑돌을 개의통에넣을것인데, 이번에는바둑돌을배정받지못하는통이있어도된다. 즉, i = 1,..., 개의통에빈통이없도록넣으면된다. (3.6) 을이용하여 p(n, ) 표를채우는과정을보자. 아래의 3개표중왼쪽표는 p(n, n) = p(n, 1) = 1을이용하여만든것이다. 가운데표는 p(n, 2) = p(n 2, 1)+p(n 2, 2) 를 n = 3,..., 6에대해서계산한것이다. n = 3 에대한계산은붉은색으로나타내었고, n = 4에대한계산은보라색으로나타내었다. 오른쪽표는 p(n, 3) = p(n 3, 1) + p(n 3, 2) + p(n 3, 3) 에대해서계산한것이다. n = 5 에대한계산을붉은색으로나타내었다. n\ n\ n\ 대상 - 상자의마지막조합인 000 은 n 개의바둑돌을구별안되는 개의통에빈통을허 용하여넣는것을뜻한다. 이것은 n 개의바둑돌을구별안되는 개이하의통에빈통이 없도록넣는것과같다. 따라서이렇게넣는방법의수를 p (n) 이라하면 p (n) = p(n, 1) + + p(n, ) (3.7) 가된다. p n (n) def = p(n) 을 n 의분할수라고정의한다. n 을 개이하의자연수의합으로 ( 순서를고려하지않고 ) 나타내는방법수를 p (n) 이라 하였는데, 이번에는 n 을 이하의자연수의합으로나타내는방법수를생각해보자. 이수를 q (n) 으로나타내면 q (n) = p (n) 임을패러즈다이어그램 (Ferrers digrm) 을통하여보일수 있다. 예를들어 21 = 은오른쪽그림과같이나타낼수있다. 이그림은 21 을 5 개이하의그룹으로분할한하나의예를보여준다. 그런데이그림은, 8 개의열각각에있는점들의개수를세어 보면, 21 을 5 이하의자연수들로분할한하나의예, 즉 21 = 를보여주는것으로해석할수도있다. 일반적으로 n 을 개이하의그룹으로분할한것은, 페레즈다 이어그램을통하여, n 을 이하의자연수들로분할한것과 1 대 1 대응이된다. 따라서 q (n) = p (n) 이다. 24

25 연습문제 3.28 (p191, #1) 7 명의사람을 4개의그룹으로가르는방법의수를구하여라. ( 힌트 : 공식하나로해결된다.) 연습문제 3.29 (p191, #2) 수의집합 X의원소의합을 σ(x) 로나타내기로하자. 집합 {1, 2,..., 101} 을조건 σ(x +1 ) = σ(x ) + 6, ( = 1, 2, 3, 4, 5) 를만족하는 6개의부분집합 X 1,..., X 로분할하는것이가능한가? ( 힌트 : 이문제는이섹션에서공부한내용과무관하다. 단순한등차수열문제임.) 연습문제 3.30 (p191, #3) n 개의서로다른소수의곱으로표현되는자연수를 n 개의인수의곱으로나타내는방법의수를구하여라. ( 힌트 : p172 # 인수 1 허용?) 연습문제 3.31 (p191, #6) 자연수 n을 1과 2의합으로나타내는방법 ( 더하는순서를바꾸는것은다른방법인것으로간주 ) 의개수를 A(n) 이라하고, 2 이상의자연수들의합으로나타내는방법 ( 더하는순서를바꾸는것은다른방법인것으로간주 ) 의기수를 B(n) 이라고하면 A(n) = B(n + 2) 임을증명하라. ( 힌트 : n = 1, 2, 3, 4, 5, 6에대해서 A(n) 과 B(n + 2) 을각각구하여값이같음을확인한다. 이때각방법, 즉수열들을모두나열하고관찰하여문제풀이에유용한패턴을찾는다. A(n) 중에 2의개수가 인것들의개수를구하는식은비교적쉽게구할수있다. 이것이 B(n + 2) 중에 + 1개의합인것들의개수 +1 H n+2 2(+1) 와같음을계산에의하여확인한다.) 연습문제 3.32 (p192, #9) 제1 스털링행렬의제n행의합을구하여라. ( 힌트 : 행렬을그리고값을유추하여 n의식으로나타낸다. 그리고ㄱ-행법칙과수학적귀납법을사용하여이것이옳음을증명한다.) 연습문제 3.33 (p193, #14) 집합 X = {1, 2,..., 14} 에대하여다음을구하여라. (1) X를공집합이아닌 4개의부분집합으로분할하는방법의수. ( 힌트 : 대상-상자조합 101) (2) X를크기가 2, 3, 4, 5인 4개의부분집합으로분할하는방법의수. ( 힌트 : p70, 일반화된조합 ) (3) X를크기가 3, 3, 4, 4인 4개의부분집합으로분할하는방법의수. ( 힌트 : 일반화된조합과약간다름.) 연습문제 3.34 (p193, #15) 아래의문제에서자연수는 1 이상의정수를뜻한다. (1) 합이 n인자연수열의개수를구하여라. ( 힌트 : 길이가 인경우에는디오판투스방정식을활용하면된다. = 1,..., n에대한개수를구하여모두더하면된다.) (2) 합이 n인단조증가자연수열의개수를구하여라. ( 힌트 : 분할수 ) 연습문제 3.35 (p193, #18) n-집합에서 -집합으로가는함수로서변역의원소의개수가 r인것들의개수는 P r S(n, 4) 임을증명하여라. ( 힌트 : T (n, r) 과 S(n, 4) 의관계를이용한다.) 25

26 4 그래프 기본 개념 4.1 그래프는 꼭짓점과 그들을 잇는 변으로 이루어진 도형이며 집합론적으로는 다음과 같이 정 의된다. 정의 4.1 그래프 G는 순서쌍 G = (V, E)로 정의된다. 단, V 는 공아닌 유한집합, E는 V 의 2중복조합의 다중집합이다. V 의 원소를 꼭짓점(vertex ), E의 원소를 변(edge)이라 한다. {x, y} E는 꼭짓점 x와 y를 잇는 변을 의미하며 이를 [x, y]로 나타낸다. 정의 4.2 꼭짓점의 개수를 vg, 변의 개수를 eg 로 나타낸다. vg 를 G의 위수라고 한다. 혼동의 우려가 없을 때는 vg 와 eg 를 간단히 v와 e로 나타낸다. def [x, y] = E일 때 x와 y는 인접하다고 한다. 이때 는 x, y에 물려있다고 하고 x와 y는 를 물고있다고 한다. 꼭짓점 x와 인접한 모든 꼭짓점들의 집합을 NG (x)로 나타내고 x의 이웃(neighborhood )이 라고 부른다. x와 y를 잇는 변이 2개 이상 있을 때는 이 변들을 다중변이라고 하고 [x, y]1, [x, y]2 등으 로 나타낸다. {x, x} 형태의 변을 고리라고 한다. 다중변과 고리가 없는 그래프를 단순그래프라 한다. 정의 4.3 G = (V, E)가 그래프라 하자. x V 일 때 G x는 V 에서 x를 제거하고 E에서 x에 물려있는 모든 변을 제거하여 얻은 그래프를 G x로 나타낸다. W V 일 때 G W 는 V 에서 W 의 모든 원소를 제거하고 E에서 W 의 원소에 물려있는 모든 변을 제거하여 얻은 그래프를 G W 로 나타낸다. F E일 때 G F 는 (V, E F )를 뜻한다. G {}는 간단히 G 로 나타낼 수 있다. 정의 4.4 꼭짓점 x에 물려있는 변의 개수를 x의 차수(degree)라고 하고 d(x)로 나타낸다. 차 수가 0인 꼭짓점을 고립점이라고 한다. 차수가 1인 꼭짓점을 단말점이라고 한다. 고리 하나는 그것을 물고 있는 꼭짓점의 차수에 2만큼 기여한다. 그래프 G의 차수의 최솟값을 δg 로 나타낸다. 차수가 짝수인 꼭짓점을 짝수점, 차수가 홀수인 점을 홀수점이라 한다. 정리 4.5 위수 2인 단순그래프에서는 차수가 같은 꼭짓점 2개 이상 존재한다. (증명). n에 대한 귀납법을 사용한다. n = 2인 경우에는 e = 0 또는 e = 1일 것인데 두 경우 모두 두 꼭짓점의 차수는 같다. 차수가 0인 꼭짓점이 있을 때는 귀납가설에 의하여 G x에 차수가 같은 꼭짓점이 2개 이상 존재하므로 wlog 차수는 모두 양수라고 가정한다. V = {x1,..., xn }으로 놓으면 각 xi 는 자기 자신을 제외한 꼭짓점 하나 이상과 인접하므로 1 d(xi ) n 1이다. d(x1 ),..., d(xn )은 모두 {1,..., n 1}의 원소이므로 비둘기집의 원리에 의하여 d(xi ) = d(xj )인 i 6= j가 존재한다. 26

27 정리 4.6 모든 그래프에서 꼭짓점의 차수의 합은 변의 개수의 2배이다. 즉 X d(x) = 2e x V 이다. (증명). 각 변은 차수의 합에 2씩 기여한다. (변이 고리일 때와 아닐 때로 나누어 생각하여 확인한다.) 그러므로 차수의 합은 2e이다. 정리 4.7 모든 그래프에서 홀수점의 개수는 짝수이다. (증명). 홀수 개의 홀수를 더하면 홀수이다. 따라서 홀수점의 개수가 홀수라면 모든 차수의 합은 홀수가 된다. 하지만 모든 차수의 합은 2e이므로 홀수일 수 없다. def def 정의 4.8 그래프 G1 = (V1, E1 )에서 G2 = (V2, E2 )로 가는 동형사상이란 전단사함수 f : V1 V2 로서 ( x, y V1 )([x, y] E1 [f (x), f (y)] E2 ) 를 만족하는 것을 말한다. 두 그래프 사이에 동형사상이 존재할 때 이 두 그래프를 서로 동형 이라 한다. 단평 4.9 그림으로 나타낸 두 그래프가 동형임을 보일 때는 다음과 같이 한다: 하나의 그래프 의 꼭짓점들을 x1,..., xn 으로 이름 붙이고, 다른 그래프의 꼭짓점들에 적당히 x01,..., x0n 으로 이름을 붙여 xi 와 xj 가 인접할 때면이 x0i 와 x0j 가 인접하도록 하면 된다. 동형이 아님을 보일 때는 모든 전단사함수가 동형사상이 아님을 보이는 것은 작업량이 너무 많으므로 좋은 방법이 아니다. 그것보다는 한 그래프가 가지는 어떤 성질 이 다른 그 래프에는 없음을 보이도록 한다. 성질 의 예로는 아주 간단한 것으로는 v, e 등이 있으며, 조금 복잡한 것으로는 차수가 인 꼭짓점이 m개 존재한다., 고리의 개수가 이다., 중변의 개수가 m이다., 삼각형이 개 있다., 임의의 두 변이 인접하다 등이 있다. 그래프의 성질을 나타내는 것으로 유용한 것 중 하나가 차수열이다. 이것은 그래프의 곡 짓점을의 차수를 내림차순으로 배열한 수열이다. 동형인 그래프는 동일한 차수열을 가지지만 이것의 역은 일반적으로 참이 아니다. (예: p279 하단) 정의 4.10 음아닌 정수로 이루어진 내림차순 수열은 그것을 차수열로 가지는 단순그래프가 존재할 때 그래프적이라고 한다. 음아닌 정수로 이루어진 내림차순 수열이 그래프적인지를 판단하는 가장 간단한 방법은 홀수의 개수를 세는 것이다. 이것이 홀수라면 그래프적이 아니다. 이것이 짝수라면 다른 방 법을 사용해야 한다. def 정리 4.11 = d1 d2 dn 0인 정수 di 들에 대하여 수열 d~ = (d)1,..., dn 이 그래프적일 필요충분조건은 def d~0 = (d2 1,..., d+1 1, d+2,..., dn ) 27

28 이 그래프적인 것이다. (d2 에서 시작하여 d1 개의 원소에서 1을 뺀다.) 단, d1 n이면 그래프 적일 수 없고, d2,..., d+1 중에 0이 있어 이들 중에 1로 바뀌는 것이 있어도 역시 안 된다. (증명). 책에 나온 증명 참조. 주어진 수열이 그래프적인지 알려면 먼저 홀수의 개수를 세고, 그것이 짝수라면 위의 정 리를 이용하여 더 작은 수열로 변환한다. 이를 반복하여 충분히 작은 수열(모든 원소가 1 또는 0인 수열)을 얻게 되면 쉽게 답을 할 수 있을 것이다. 그래프적인 것으로 판명된 수열이 주어졌을 때 이것을 차수열로 가지는 그래프를 구성할 줄 알아야 한다. p283의 예는 그림이 조금 틀려있지만 아이디어는 맞다. 정의 4.12 그래프의 변 [x, y]에 [x y] 또는 [x y]와 같이 방향을 준 것을 유향변이라 하고, 모든 변이 유향변인 그래프를 유향그래프라고 한다. (주의: 하나의 변에 방향을 양쪽으로 다 줄 수는 없다.) 두 유향변이 형태로 이어져 있을 때 이 두 유향변은 순접한다고 말한다. def def 정의 4.13 G = (V, E)가 주어졌을 때, 어떤 V 0 V, E 0 E에 대해서 G0 = (V 0, E 0 )이 그래프라면 이 G0 을 G의 부분그래프라고 한다. 부분그래프의 개념은 유향그래프에도 그대로 적용된다. V 0 = V 인 부분그래프를 생성부분그래프라고 한다. 정의 4.14 그래프에서 경로(pth)란 인접한 변들의 열을 뜻한다. 유향그래프에서 경로란 순접 한 변들의 열을 뜻한다. 경로의 길이는 경로를 이루는 변의 개수를 말하며 이때 동일한 변이 두 번 이상 나타나면 모두 카운트한다. 길이가 0인 경로는 허용하지 않는다. 꼭짓점 x에서 출발하여 y에서 끝나는 경로를 (x, y)-경로라고 한다. 출발점이 끝점과 일치하는 경로를 폐로(closed pth)라고 한다. 동일한 변이 두 번 이상 나타나지 않는 폐로를 회로(circuit)라고 한다. 동일한 꼭짓점이 두 번 이상 나타나지 않는 회 로를 바퀴(cycle)라고 한다. 양 끝점을 포함한 모든 꼭짓점이 다른 경로를 직선경로(line pth) 라고 한다. 정리 4.15 단말점이 없는 그래프는, 아래의 조건 중 어느 하나가 충족된다면, 회로를 가진다. 고립점이 없다. e 1 연결그래프이고 v 2 (증명). 책의 증명을 참조할 것. (위의 3 조건은 증명의 어느 부분에 사용되는가?) 연습문제 4.16 (p286) () #1 (b) #2 (1), (2)의 명제들이 필요이상으로 복잡하다. 동등하고 더 간단한 명제로 바꾸어 증 명할 것. (c) #3 부등식만 가지고는 답이 되지 않는다. 그래프의 예를 들어야 한다. P (1) x V d(x) = 2e를 이용할 것. 28

29 (2)는 최대값을 최솟값으로 바꿀 것. (힌트: 주어진 위수 v를 가지는 그래프가 변을 최대 몇 개까지 가질 수 있겠는가?) (d) #9, #10, # 여러가지 그래프 정의 4.17 임의의 두 꼭짓점이 인점한 단순그래프를 완전그래프라고 하고 위수가 n 1인 완 전그래프를 Kn 으로 나타낸다. (K1 은 변을 가지지 않는다.) 모든 꼭짓점의 차수가 동일한 그래프를 정칙그래프라고 한다. 꼭짓점의 차수가 r로 일정한 그래프를 r-정칙그래프라고 한다. 정의 4.18 임의의 두 꼭짓점 x 6= y에 대하여 (x, y)-경로가 존재하는 그래프를 연결그래프(con- nected grph)라고 한다. def 그래프 G = (V, E)의 연결부분그래프 G0 (V 0, E 0 )로서 더 이상의 꼭짓점을 추가하면 연결성 이 깨지는, 그리고 E의 원소 중에 V 0 에 물려있는 모든 변이 E 0 에 속하는 것을 G의 연결성분(connected component)이라 한다. (책에서는 최대 의 연결부분그래프라고 했지만 최대보다는 극 대 가 옳은 표현이다. 왜냐하면 최대라는 단어는 유일하다는 것을 암시하기 때문이다. 연결 성분은 당연히 여러 개 있을 수 있다.) 유향그래프에는 강연결그래프라는 개념이 있다. 임의의 서로 다른 두 점 x, y에 대해서 (x, y)-경로와 (y, x)-경로가 모두 존재한다는 뜻이다. 정의 4.19 연결그래프 G에서 적당한 꼭짓점 n개를 제거함으로써 연결성이 깨지거나 K1 으로 완원되었을 때, 이러한 최소의 n을 점연결도라 하고 κ(g)로 나타낸다. 연결그래프가 아닌 그 래프의 점연결도는 0으로 정의한다. 비슷한 방법으로 변연결도를 정의하고 κ0 (G)로 나타낸다. 정리 4.20 G가 단순연결그래프라고 한다. 그러면 (1) κ(g) κ0 (G) δg, (2) κ(g) 2e v. (증명). 책의 증명 참조. def 정의 4.21 그래프 G = (V, E)의 V 가 X, Y 의 두 부분으로 분할되어 모든 변에 대해서 그것을 물고있는 양끝점이 하나는 X에 다른 하나는 Y 에 속할 때 이 G를 2분그래프라고 한다. 이때 (X, Y )를 V 의 2분할이라고 한다. 이때 X의 임의의 원소와 Y 의 임의의 원소가 인접하다면 G를 완전2분그래프라고 한다. X = m, Y = n인 완전2분그래프를 Km,n 으로 나타낸다. 정리 4.22 그래프 G가 2분그래프일 필요충분조건은 G의 각 회로의 길이가 짝수일 것이다. (증명). 책의 증명 참조. 정의 4.23 모든 변들이 서로를 교차하여 지나가는 일이 없도록 평면 내에 그릴 수 있는 그래 프를 평면그래프라고 한다. 평면그래프 G에 의하여 분할되는 평면의 구역들을 G의 면( fce)이라고 한다. 면의 개수는 fg 로 나타낸다. 29

30 평면그래프의정의는기하적인직관을이용한것이다. Kurtowsi( 폴란드의수학자, ) 는평면그래프의집합론적정의가가능하도록하는정리를증명하였다. (p297, 정리 ) 연결평면그래프에대하여는중요한 2개의정리가있다. 정리 4.24 ( 오일러의공식 ) 연결평면그래프에서는다음등식이성립한다. v + f = e + 2 ( 증명 ). e에대한귀납법을사용한다. 책의증명참조. 평면그래프에서는각변의날 (blde) 이라는개념이존재한다. 변의양쪽가장자리를날이라고한다. 면 F 와인접한날의개수를 F 의 ( 면 ) 차수라고한다. 평면그래프외부도하나의면이므로그것의차수를생각할수있다. (p295의그림을볼것 ) 꼭짓점의차수의합이 2e이듯이평면그래프에서차수의합은 2e이며이사실은날의개념을사용하여쉽게증명된다. 정리 4.25 G가위수 3 이상의연결평면단순그래프이면 v e 이며더욱이 G 가 2 분그래프이면 v e 가성립한다. ( 증명 ). 모든면의차수가 3 이상이라는사실과오일러의정리를이용한다. 책의증명참조. 위의정리는쉽게말하자면변의수가결정되면꼭짓점의개수는어느한계이상작아질수는없다는것이다. 왜냐하면연결평면단순그래프에서는꼭짓점의개수가줄어들면차수가늘어나면서변들이서로를교차하게되기때문이다. 위의정리를이용하면 K 5 와 K 3,3 는평면그래프가아님을쉽게보일수있다. 쿠라토우스키는이명제의역으로볼수있는정리를증명하였다. 따름정리 4.26 평면단순그래프에서는차수가 5 이하인꼭짓점이존재한다. ( 주의 ). 책의명제에는 단순 성이빠져있다. 연결성은 wlog 가정할수있으므로여기서는생략하였다. 증명중에정리 4.25를사용하기위수가 3 이상임을가정해야하는데이것은 wlog 가능하다. p300의 #7에보면이따름정리보다더강력한명제를증명하도록되어있다. 연습문제 4.27 (p300) () #1 답이너무많으므로 단순그래프 등다양한조건을넣어서답의개수를줄여풀어보라. (b) #2 30

31 (c) #3에서 v2 v2 2 는 4 로 바꾸어도 된다. (d) #4 (e) #5에서 (1), (2) 중 어느 하나의 조건만 가지고도 주어진 명제를 증명할 수 있다. Wlog 연결그래프를 가정해도 됨을 먼저 보일 것. (f ) #7 (g) #8 단순성을 가정해야 한다. 단순그래프가 아닌 경우에는 반례가 있다. 수형도 4.3 정의 4.28 회로가 없는 연결그래프를 수형도(tree)라 한다. (K1 도 수형도이다.) 보조정리 4.29 다음에 나오는 중요한 정리를 증명할 때 필요하다. (1) 위수 2 이상의 수형도는 단말점을 가진다. (2) e = v 1 1인 연결그래프는 2개 이상의 단말점을 가진다. (책에서는 연결성이 빠져 있는데, 연결성을 가정하거나 아니면 고립점이 없음을 가정해야 한다.) (증명). 책의 증명 참조. 정리 4.30 연결그래프 G에 대하여 아래의 명제들은 모두 동등하다. (1) G는 수형도이다. (2) e = v 1 (3) G는 각 변이 다리이다. (4) G의 임의의 두 꼭짓점을 잇는 경로가 유일하게 존재한다. (증명). 책의 증명을 참조한다. 단, 책에 빠져있는 연결그래프 조건이 사용되는 부분에 유의 해야 한다. 그리고 (1) (2)의 증명에서 vh = v = 1은 vh = v 1의 오타이다. 그래프 G의 생성부분그래프로서 수형도인 것을 생성수형도라고 한다. 만일 G가 연결그래프라면 연결성이 깨지지 않는 범위내에서 변을 최대한 제거하면 이 생 성부분그래프는 회로가 없을 것이다. 왜냐하면 회로의 한 변을 제거해도 연결성은 깨지지 않 기 때문이다. 그렇다면 이 생성부분그래프는 수형도이다. 따라서 연결그래프는 생성수형도를 가진다는 결론을 얻는다. 수형도에서 특정한 하나의 꼭짓점을 지정한 것을 유근수형도(rooted tree)라 한다. 왜냐하 면 이 꼭짓점을 집어서 들어 올리면 이 그래프는 뒤집힌 나무 형택다 되기 때문이다. 유근 수형도에는 (반)순서관계가 존재한다. 이 순서관계에서 한 꼭짓점 x와 인접하여 아래에 있는 꼭짓점들을 자녀(id )라고 한다. 단말점이 아닌 각 점이 모두 일정하게 m개의 자녀를 가지는 유근수형도를 m-진수형도 라 한다. 유근수형도에서 뿌리도 아니고 단말점도 아닌 꼭짓점들을 중간점(혹은 내부점)이라 한다. p309의 예제 6.3.5를 꼭 읽어 볼 것. 31

32 연습문제 4.31 (p316) () #1 (b) #2 (2)에 오타가 있다 P di 3 (di 2)가 맞다. 위수에 대한 귀납법으로 증명된다. 회로 p319의 아래 부분에 있는 깊이 우선 검색(depth first serch)에 의하여 주어진 연결그래프의 생성수형도를 찾는 과정을 이해해야 한다. 그래프의 각 변에 적당하게 방향을 주어 강연결 유향그래프로 만들 수 있을 때 이 그래프 를 강연결화 가능이라 한다. p320의 강연결화 가능성을 설명하는 그림은 화살표의 일부가 방향이 틀려 있다. 정리 4.32 연결그래프 G가 강연결화 가능일 필요충분조건은 G가 다리를 가지지 않을 것이다. (증명). ( ) 증명의 첫부분에 wlog 고리를 갖지 않음을 가정해야 한다. p321의 상단 그림에 서 (x, y)-경로 γ와 (x, z)-경로 δ를, 이 두 경로가 공유하는 변이 없도록 잡을 수 없다는 것은 다리를 가지지 않는다 는 조건에 의한 것이라고 설명하고 있는데 이것은 아래의 보조정리를 필요로 한다. 보조정리 4.33 G가 다리가 없는 연결그래프라면 G의 임의의 서로 다른 세 꼭짓점 x, y, z에 대해서 y에서 출발하여 x를 거쳐 z로 가는, 변을 중복하여 사용하지 않는 경로가 존재한다. (증명). (이 증명은 한 수강학생이 제공한 것입니다.) 두 꼭짓점 사이의 거리 는 두 꼭짓점을 잇는 최단 경로의 길이인 것으로 정의한다. 단, 두 꼭짓점이 일치할 때는 거리가 0인 것으로 한다. 최단 경로는 변이나 꼭짓점을 중복 사용하지 않음에 주목하라. 꼭짓점 w와 경로 p 사이의 거리 는 p 상에 있는 꼭짓점들과 w 사이의 거리 중 가장 작은 값을 말한다. 이제 다음의 주장을 증명하면 충분하다. Clim: 변을 중복하여 사용하지 않는 (y, z)-경로 중에 x 까지의 거리가 0인 것이 있다. 변을 중복하여 사용하지 않는 (y, z)-경로 중에 x까지의 거리가 최소인 것울 pyz 라 하자. x와 p 간의 거리가 d > 0이라고 가정하고 모순을 유도하면 된다. pyz 위의 점 중에 x까지의 거리 가 d인 것을 취하여 w라 둔다. x에서 w까지의 최단경로를 pxw 라 하자. 이 경로는 길이가 d 이다. pxw 위의 꼭짓점 중에 w와 인접한 것을 v라 하자. pxw 는 변이나 꼭짓점을 중복사용하지 않으므로 v 6= w이고, x와 v 사이의 거리는 d 1임을 알 수 있다. 따라서 v는 pyz 에 속하지 않는다. [v, w]는 다리가 아니므로 G [v, w]는 연결그래프이다. 따라서 pyz 위의 각 꼭짓점마다 v 에서 이 꼭짓점에 이르는 G [v, w] 경로가 존재한다. 이들 중에 가장 길이가 작은 것을 취 하고, 그때의 pyz 위의 꼭짓점을 w0 으로 둔다. 이때 v와 w0 을 잇는 경로를 pvw0 으로 둔다. 이 경로의 변들과 [v, w]와 pyz 의 변들 중에 중복되는 것은 하나도 없다. 이때 w0 이 w, y, z 중의 어느 것과 일치할 수도 있지만 이것은 하등의 문제를 일으키지 않음에 주목하라. pyz 에서 (w0, w)-경로를 제거하고, pvw0 과 [v, w]를 넣으면 이것은 G 내에서의 (y, z)-경로가 된다. 이 경로는 변을 중복 사용하지 않으며 x까지의 거리가 d 1 이하이다. 이는 d의 최소 성에 모순된다. 32

33 정의 4.34 그래프 G의각변을단한번씩만지나는 ( 그리고모든변을지나는 ) 경로를 G의오일러경로라고한다. 오일러경로중에회로인것을오일러회로라고한다. 오일러회로를가지는그래프를오일러그래프라고한다. 정리 4.35 연결그래프 G가오일러그래프일필요충분조건은 G의모든꼭짓점이짝수점일것이다. ( 증명 ). 책의증명을참조한다. 단, 증명중에각 G i 가 C와 1개이상의꼭짓점을공유해야하는이유는, 만일그렇지않다면 G의연결성이깨지기때문이다. 예제 4.36 위수가 3 이상의홀수인완전그래프는오일러그래프이다. ( 증명 ). 책의증명을참조한다. 따름정리 4.37 연결그래프가오일러회로가아닌오일러경로를가질필요충분조건은홀수점이딱 2개일것이다. 이때이두홀수점이오일러경로의양끝점이된다. ( 증명 ). 책의증명을참조한다. 정의 4.38 그래프 G의각꼭짓점을모두지나되단한번씩만지나는회로를 G의해밀터회로라고한다. 해밀턴회로를가지는그래프를해밀터그래프라한다. 단평 4.39 해밀턴회로를가질여러조건들이책에나와있으나오일러회로에대한것보다훨씬더복잡하다. 연습문제 4.40 p335 #1 -end- 33