주메뉴바로가기.. 본문바로가기

Problems

폴리매스 문제 보기

문제

[대한수학회] 대12. 그래프의 a-넘버①

2017.11.30

같이 풀어볼까?

네이버밴드 구글플러스

이번 대한수학회 문제는 2달에 걸쳐 진행됩니다. 같은 주제의 내용으로 12월에 4문제, 1월에 3문제를 함께 풀어볼 예정입니다. 출제자인 최수영 아주대학교 교수님은 1월에 공개할 7번 문제를 풀기 위한 과정으로 1번~6번 문제를 봐달라고 이야기했습니다. 그럼 문제 나갑니다.

 

대한수학회 12월, 1월 문제에서는 그래프로부터 정의되는 재미있는 불변값에 대해 이야기하려고 한다. 이 값을 계산하기 위해서는 약간의 그래프에 관한 기초 용어를 이해할 필요가 있다. 물론 여기서 필요한 용어는 직관적으로 이해할 수 있기 때문에 그래프 이론의 기초개념을 배운 적이 있는 사람은 아래 ⓵, ⓶, ⓷은 넘어가도 무방하다.

 

⓵ (유한)그래프는 유한한 점의 집합에 대해서 각 점의 쌍을 서로 변으로 연결한 것이다. 이때 어떤 두 점도 많아야 한 개의 변으로 연결돼 있고, 각 변은 항상 서로 다른 두 점을 잇는다면 이 그래프를 ‘단순그래프’라고 한다. 즉 단순그래프 \large G=(V, E)는 유한한 점의 집합  \large V와 서로 다른 두 점의 쌍으로 이뤄진 변의 집합 \large E로 구성돼 있다. 가령 집합 \large V=\left \{ 1, 2, 3, 4 \right \}와 \large E=\left \{ \left \{ 1, 2 \right \}, \left \{ 2,3 \right \},\left \{ 3,4 \right \} \right \}로 구성된 그래프 \large P_4는 다음 모양과 같은 그래프다. 

\large P_4 = 

 

⓶ 그래프가 연결돼 있다는 것은 그래프의 임의의 점의 쌍에 대해서 한 점에서 출발해 변으로만 이동해서 다른 점으로 갈 수 있다는 뜻이다. 그래프  \large G가 연결된 몇 개의 성분으로 나눠질 때, 각 성분을 ‘그래프  \large G의 연결성분’이라 부르자.

 

⓷ 단순그래프  \large G=(V_G, E_G)의 부분유도그래프  \large H=(V_H, E_H)란  \large G에 포함되는 점의 부분집합에 대해 그 부분집합으로 구성되는 모든 변을 다 모은 것이다. 즉  \large V_H\subset V_G이고,  \large E_H=\left \{ \left \{ v,w \right \} \in E_V |v,w\in V_H \right \}를 만족하는 그래프다. 그래프  \large H가  \large G의 부분유도그래프일 때 간단히 \large H\subset G로 표현하자.

 

이제 그래프의 불변값을 정의할 준비가 되었다. 각각의 단순그래프  \large G에 대해서 다음과 같은 귀납적인 방법으로  \large a(G)를 정의하자.

 

(1) \large a(\varnothing )=1 (집합 \large V가 공집합인 경우는 \large G=\varnothing으로 표현한다.)

(2) \large G가 홀수 개수의 점을 가지는 연결 성분을 가진다면 \large a(G)=0

(3) 

 

예를 들어 

이다. 또 다른 예로 만약 그래프가 홀수 개수의 점을 가진다면 반드시 어떤 연결 성분의 크기는 홀수여야 하므로  \large a값은 항상 0이 돼야 한다.

 

문제1. 점의 개수가 4개인 그래프를 모두 찾고, 이 그래프들의  \LARGE a값을 구하여라.

 

문제2. 그래프  \LARGE G가 두 개의 연결성분  \LARGE H_1, H_2 으로 구성돼 있을 때,  \LARGE a(G)=a(H_1)\times a(H_2)가 성립함을 보여라. 일반적으로 그래프  \LARGE G가  \LARGE k개의 연결성분  \LARGE H_1, \cdots , H_k로 구성돼 있을 때 다음이 성립함을 보여라.

\LARGE a(G)=a(H_1)\times \cdots\times a(H_k)

 

문제3. (1) ⓵에서 주어진  \LARGE P_4를 일반화해 경로그래프  \LARGE P_n=(V, E)를 다음과 같이 정의할 수 있다. 

\LARGE V=\left \{ 1, 2, \cdots, n \right \}\LARGE E=\left \{ \left \{ 1,2 \right \}, \left \{ 2, 3 \right \}, \cdots , \left \{ \left \ n-1, n \right \} \right \}

경로그래프  \LARGE P_2_m에 대해  \LARGE a(P_2_m)을  \LARGE m에 대한 수열로 나타내고, 이 수열이 가진 성질에 대해 조사해 봐라.

 

(2) 자기가 관심 있는 여러 그래프에 대해  \LARGE a값을 계산해 봐라.

 

문제4. 단순그래프  \LARGE G의 점의 개수가  \LARGE 2m일 때,  \LARGE a(G)의 부호가  \LARGE (-1)^m과 같음을 증명 혹은 반증하여라.

 

※알립니다.

12월 28일 현재 소문제 1, 2, 3번이 풀렸습니다. 출제자인 최수영 교수님께 확인한 결과 1번은 수학장, 2번은 구머와 수학장, 3번은 구머 선수가 문제 해결에 기여했습니다. 여백 패르마 선수도 열심히 했는데, 아쉽다고 평해주셨습니다. 4번은 아직 해결되지 않았는데요. 최수영 교수님은 다음과 같이 조언을 해주셨습니다.

 

"그래프의 a-넘버는 어떤 특정한 위상공간의 불변값과 관련이 있습니다. 해당 위상공간의 성질을 사용하면 4번 성질을 쉽게 증명할 수 있습니다. 

하지만 위상적 증명이 아닌 순수 조합적인 방법을 사용한 증명은 아직 알려져 있지 않습니다. 어떤 참인 수학 명제에 대해 다양한 방법을 사용해 새로운 증명을 찾는 것은 언제나 가치가 있습니다. 

새로운 증명은 수학 명제 속에 숨어 있던 수학 구조를 드러나게 해줄 수 있기 때문입니다. 비록 이번 달에는 이 증명을 완전히 찾지는 못하였지만, 언젠가는 새로운 증명을 찾을 수 있기를 바랍니다."

 

여러분, 4번 문제의 조합적인 증명을 찾아주세요!

댓글 131

  • 구머 2017.11.30 19:14:21

    '그래프 G의 연결성분'이 정확하게 어떤 것인지 잘 이해되지 않네요.. 혹시 예시나 좀더 구체적인 정의를 알 수 있을까요? 

     

    좋아요0 댓글수2
    • 수학동아 2017.12.01 09:38:34

      그래프 G가 위와 같은 모습이라면 연결 성분이 두 개입니다. H_0와 H_1이 그래프 G의 연결 성분입니다. 

      좋아요1
    • 구머 2017.12.01 16:12:52

      아..G가 항상 연결그래프여야 하는건 아니군요! 감사합니다

      좋아요0
  • 여백 패르마 2017.12.01 19:48:44

    좋아요0 댓글수6
    • 여백 패르마 2017.12.01 19:49:11

      2번 증명입니다.

      오류 찾으신 분께서는 대댓글 올려주시길 바랍니다.

      좋아요0
    • 여백 패르마 2017.12.03 11:41:07

      이렇게 일찍 나온 것 보면 심각한 오류가 있을 듯 하네요.

      좋아요0
    • 구머 2017.12.03 12:04:10

      잘 푸신 것 같은데요? 오류가 생길만한 부분이 없는 것 같아요.

      좋아요0
    • 여백 패르마 2017.12.03 13:28:41

      다행이군요..... 봐주셔서 감사드려요~^^

      좋아요0
    • 여백 패르마 2017.12.09 13:09:20

      또, 베타를 더하지 말고 곱해도 같은 결과가 나옵니다.

      좋아요0
    • 수학장 2017.12.12 20:14:46

      여백 페르마님 저희가 아래에 증명했습니다

      좋아요0
  • 수학장 2017.12.07 19:35:05

    문제4

    G의 점의 개수가 2일 때 부호가 -이므로 성립한다

    G의 모양은 하나의 연결성분으로 되어 있는 경우와, 두 개 이상의 연결성분으로 나뉘어 있을 경우로 나눌 수 있다.

    G가 두 개 이상의 연결 성분으로 나뉘어 있으면 홀수 개수의 점으로 된 연결성분이 있을 때와 없을 때로 나눌 수 있다.

    좋아요0 댓글수0
  • 수학장 2017.12.07 20:26:18

    문제 4  구머님이 알려주신 심각한 오류 발생 문제를 풀 아이디어 있으면 알려주세요

    좋아요0 댓글수2
    • 구머 2017.12.07 21:49:55

      점의 개수가 6일때는

      다음과 같은 경우도 고려해주셔야 합니다.

      좋아요0
    • 수학장 2017.12.07 22:17:40

      아 그렇군요 다시 풀어봐야겠군요 문제를 너무 쉽게 봤나봐요

      좋아요0
  • 여백 패르마 2017.12.08 15:30:06

    그런데 3번에서의 P가 공차가 1인 등차수열 아닌가요??

    좋아요0 댓글수5
    • 수학장 2017.12.08 18:31:20

      계산 결과 P2=-1, P4=2 P6=-5입니다. 등차수열은 아니예요.

       

      좋아요0
    • 여백 패르마 2017.12.08 20:36:44

      풀이 과정을 보여주실 수 있나요???

      좋아요0
    • 수학장 2017.12.08 20:50:36

      P2=-1 P4=-(-1x3+1)=2

      P6=-(2x3-1x5+1x3+1) P6부터는 구머님이 말해주셨듯이 연결성분이 두 개 이상인 부분유도그래프도 계산해야 합니다.

      P8부터는 각각의 숫자가 뭘 의미하는 지 적기는 좀 복잡해서 그냥 수만 보여드리겠습니다.

      P8=-(-12-1+10-15+10-7+1)=14

      P10=-(21-10+12+30+6+42-25+14-9)=-81

      P12부터는 구하지 못했습니다.

      좋아요0
    • 데넵 2017.12.15 06:50:54

      수학장님 P_10 계산이 잘못 된 것 같습니다.

      좋아요0
    • 수학장 2017.12.15 17:29:02

      데넵님 10일 때 몇인데요? 10 이상은 좀 복잡해서 틀렸을 수도 있는 건 맞아요

      좋아요0
  • 여백 패르마 2017.12.09 14:18:20

    좋아요0 댓글수3
    • 여백 패르마 2017.12.09 14:19:12

      4번 풀이입니다. 오류 찾으신 분들은 대덧글을 올려주시기 바랍니다.^^

      좋아요0
    • 수학장 2017.12.09 14:59:40

      특정 단순그래프가 아닌 모든 단순그래프에 대해 계산해야 합니다

      그리고 P4이상의 부분유도그래프도 생각해야죠

      좋아요0
    • 수학장 2017.12.09 15:01:33

      P2가 3개 이상인 부분유도그래프도 생각하셔야 합니다

      이 문제는 그렇게 간단한 문제가 아니예요

      좋아요0
  • 여백 패르마 2017.12.09 19:01:34

    1,2번이 풀렸다면 부분 해결 아닌 가요????

    좋아요0 댓글수7
    • 수학장 2017.12.09 19:59:09

      그러게요 부분해결 딱지 붙여주세요

      좋아요0
    • 구머 2017.12.09 21:14:43

      아직 2번이 확인이 정확히 된 것이 아니라서 그런 듯 하네요...

      좋아요1
    • 수학장 2017.12.09 23:18:04

      저 2번 증명이 이해가 안 되는데 여기에 글로 써 주실 수 있나요?

      좋아요0
    • 구머 2017.12.09 23:21:26

      음..사실 저도 중간 부분까지 읽다가 영감을 얻어서 그 뒷부분은 페르마님이 잘 해결했다고 생각하고 대충 맞은 것 같다 했어요.

      좋아요0
    • 여백 패르마 2017.12.10 09:02:48

      헉 헉 ㅠㅠ 그런것 이였나요???

      좋아요0
    • 수학장 2017.12.10 10:02:41

      각 a값을 시그마를 사용해서 쓴 다음 그걸 다시 덧셈으로 풀어서 서로 같음을 증명하는 건 어떨까요

      좋아요0
    • 구머 2017.12.10 10:05:33

      네 저도 그렇게 했어요.

      좋아요0
  • 수학장 2017.12.11 17:44:09

    /resources/comment/2017/12/60e9fff2e5acb40dee14523520848c9d.hwp 여기서 H알파, H베타... 등은 Ga에 속하지 않고, Gb에도 속하지 않는 그래프들입니다.

    이제 저 파일에 마지막 문장만 증명하면 됩니다. 그런데 이 부분에서 자꾸 막히네요 풀 수 있는 분들은 풀어주세요

    (아, 그리고 수학동아님 폴리매스 댓글에 그리스 문자 쓸 수 있게 해주세요)

    좋아요0 댓글수4
    • 구머 2017.12.11 23:42:47

      수식 입력기에 그리스 문자 입력란도 있습니다.

      좋아요0
    • 구머 2017.12.12 00:44:13

      2번!! (수학적 귀납법) 점의 개수가 k<=v인 그래프 G가 있고, G는 2개의 연결성분 G_{1}과 G_{2}로모든 그래프에 대해서, 2번의 조건을 만족한다고 가정하자. v=1일때는 자명하게 성립하므로, G의 점의 개수가 v+1개일때 2번 조건이 성립함을 보이면 된다.

      증명에 앞서 몇가지 정의와 성질들을 살펴보자. 먼저 그래프 G가 2개의 연결성분 G_{1}과 G_{2}로 이루어져 있다고 가정하자. 또, G_{1}의 모든 부분유도그래프들을 크기순으로\sigma_{1}, \sigma_{2}, ....., \sigma_{n}이라고 정의하고, G_2의 모든 부분유도그래프들을 크기순으로 \varphi_1, \varphi_2,....,\varphi_m라 가정하자.('크기순'이라는 말이 애매할 수 있는데, 이 정의는 \small \sigma _n=G1\small \varphi _m=G2라고 정의하기 위함이므로 그냥 넘어가도 무관할 듯 하다) 이때, G의 모든 부분유도그래프들은 \sigma_i \cup\varphi_j(1\leq i\leq n, 1\leq j \leq m)꼴로 나타내지고, 각각의 부분유도그래프마다 i와 j는 유일하게 결정된다. 반대로, 범위에 맞는 i와 j가 주어지면 그에 해당하는 부분유도그래프가 유일하게 주어진다. 따라서, G의 모든 부분유도그래프는 X(i,j)꼴로 나타낼 수 있다. 그런데, 가정에 의해 점의 개수가 k<=v인 모든 그래프는 2번의 조건을 만족하므로, G를 제외한 임의의 G의 부분유도그래프 X(i,j)에 대해, a(X_{(i,j)})=a(\sigma _i)\times a(\varphi _j)가 성립한다. 

      이제 모든 정의가 끝났다. 문제의 정의에 의하여 

        a(G)=-(a(X_{(1,1)})+a(X_{(1,2)})+.....+a(X_{(n,m-1)}))=-(a(\sigma_1)a(\varphi _1)+.....+a(\sigma_n)a(\varphi_{m-1}))

      가 성립하고,

       \small a(\sigma_1)a(\varphi _1)+.....+a(\sigma_n)a(\varphi_{m-1})=(a(\sigma _1)+...+a(\sigma _n))(a(\varphi _1)+...+a(\varphi_m))-a(\sigma_n)a(\varphi_m)

      임을 알 수 있다. 그런데 

       \small (a(\sigma _1)+...+a(\sigma _n))=-a(G_1)+a(\sigma_n)=-a(G_1)+a(G_1)=0, (a(\varphi _1)+...+a(\varphi_m))=-a(G_2)+a(\varphi_m)=-a(G_2)+a(G_2)=0

      이므로, a(G)=\small a(\sigma_n)a(\varphi_m)=a(G_1)a(G_2)가 만족한다.><

      좋아요0
    • 수학장 2017.12.12 17:11:33

      오!! 잘 증명하셨네요. (내가 증명하고 싶었는데ㅠ) 그런데 뭔가 2개의 연결성분이 증명되었다고 k개의 연결성분도 성립하는 건 아닌 것 같네요. 이것도 증명해야 할 것 같아요

      좋아요0
    • 구머 2017.12.12 17:37:58

      그냥 귀납법으로 하면 될 것 같은데요..?

      좋아요0
  • 수학장 2017.12.12 17:56:31

    으악 젠장 쓰다가 날아갔다. 다시! 그래프 G가 G1, G2, ..... ,Gk로 이루어져 있다고 하자. 또 G_{n}의 부분유도그래프를 크기순으로  \alpha _{n,1}, \alpha _{n,2}, ....., \alpha _{n,N}라고 놓자. 그러면a(\alpha _{1,1})a(\alpha _{2,1})....a(\alpha _{k,1})+......+a(\alpha _{1,p})a(\alpha _{2,q})....a(\alpha _{k,K-1})=(a(\alpha _{1,1})+....+a(\alpha _{1,p}))...(a(\alpha _{k,1})+....+a(\alpha _{k,K}))-a(\alpha _{1,p})a(\alpha _{2,q})....a(\alpha _{k,K})

    가 성립하고,

    a(\alpha _{n,1})+...+a(\alpha _{n,N})=-a(G_{n})+a(\alpha _{n,N})=-a(G_{n})+a(G_{n})=0

    이므로

    a(\alpha _{1,1})a(\alpha _{2_{1},1})....a(\alpha _{k,1})+......+a(\alpha _{1,p})a(\alpha _{2,q})....a(\alpha _{k,K-1})=-a(G)=-a(\alpha _{1,p})a(\alpha _{2,q})...a(\alpha _{k,K})=-a(G_{1})a(G_{2})...a(G_{k})

    즉, a(G)=a(G_{1})a(G_{2})...a(G_{k})이다.

    구머님 아이디어를 따라해보았습니다. 이렇게 문제 2증명 완료

    좋아요1 댓글수2
    • 구머 2017.12.12 17:58:06

      굿굿

      좋아요0
    • 수학장 2017.12.12 18:05:58

      부분해결 딱지 붙여주세요

      좋아요0
  • 수학장 2017.12.12 17:59:42

    이제 3번하고 4번 증명하러 갑시다.(Q:어떻게? A:모름)

    좋아요0 댓글수0
  • 수학장 2017.12.12 18:29:54

    하나의 연결성분으로 된 G의 부호가 (-1)m일 때, 여러 개의 연결성분 G_{1}, G_{2}, ... ,G_{k}로 된 G가 있다고 하자. 이 때 G의 a값은 a(G_{1})a(G_{2})...a(G_{k})이다. 연결성분 G_{1}, G_{2}, ... ,G_{k}의 점의 개수가 2a, 2b, .......라고 하자. 그러면 G의 점의 개수는 2a+2b+....이다. G_{1}, G_{2}, ... ,G_{k}의 부호가 (-1)^{a}, (-1)^{b}......이므로 G의 부호는 (-1)^{a+b+.....}=(-1)^{\frac{2a+2b+...}{2}}여러 개의 연결성분으로 된 G의 a값의 부호는 (-1)m과 같다.

    따라서, 우리는 4번 문제를 증명하기 위해 단순그래프 G가 하나의 연결성분으로 이루어져 있을 때만 증명하면 된다. 이 때 하나의 연결성분으로 된 경우는, 일자 모양과 고리 모양이 있다. 이 2가지 경우에서 a(G)의 부호가 (-1)m인 경우를 증명하면, 우리는 4번 문제를 증명할 수 있다.

    좋아요0 댓글수3
    • 여백 패르마 2017.12.13 13:34:17

      좋아요0
    • 여백 패르마 2017.12.13 13:34:45

      일직선일 때는 증명 했습니다.

      좋아요0
    • 구머 2017.12.13 15:10:42

      좋아요0
  • 수학장 2017.12.13 17:55:14

    일자 모양 그래프일 때 관찰: 먼저, 그래프G와 그 부분유도그래프의 a값의 합을b(G)라고 합시다. 그리고 그래프G의 점을 각각 \alpha _{1}, \alpha _{2}, ..... ,\alpha _{2m}라고 합시다. 여기서 부분유도그래프 G _{1}의 점은 \alpha _{3},.....,\alpha _{2m}이라고 하고, 다른 부분유도 그래프 G_{2}의 점은  \alpha _{1}, ..... ,\alpha _{2m-2}합시다. 그 때 G _{1}G _{2}의 교집합을 G _{3}이라고 합시다. G _{1}의 공집합을 제외한 부분유도 그래프를 \beta _{1}, .... , \beta _{m}이라고 하면 a(\beta _{1})+.... + a(\beta _{m})+a(G_{1})=-1 따라서  그리고 G_{2}, G_{3}과 그 부분유도 그래프도 마찬가지입니다. 그러면 이 그래프의 a값은 -(b(G_{1})+b(G_{2})-b(G_{3})+a(H_{\alpha })+..+a(H_{\omega })+1)=-(-1-1+1+1+a(H_{\alpha })+..+a(H_{\omega })=-(a(H_{\alpha })+..+a(H_{\omega }))여기서 H_{\alpha }등의 그래프 G의 부분유도그래프는 G_{1}G_{2}에 모두 속하지 않은 그래프로, 그래프의 연결성분의 점의 개수는 2 이상이어야 하므로(공집합 제외)이 H_{\alpha }는 항상 점\alpha _{2}와 점\alpha _{2m-1}를 항상 지난다. 쓸데 없을 지는 모르겠지만 일단 해봤어요.

    좋아요0 댓글수0
  • 수학장 2017.12.14 17:56:35

    1번 수정입니다 단순그래프가 일자 모양하고 고리 모양만 있는 게 아니더라구요

    좋아요0 댓글수1
    • 수학장 2017.12.14 18:26:28

      이것도 있는데 빼먹을 뻔했네요

      좋아요0
  • 여백 패르마 2017.12.15 14:32:07

    좋아요0 댓글수6
    • 여백 패르마 2017.12.15 14:33:13

      3번 풀이인데요 오류 찾으신 분은 대댓글 올려주시길 바랍니다.

      좋아요0
    • 여백 패르마 2017.12.15 14:35:39

      그리고 공집합도 포함해야 하기 때문에 바꿀 수 있으신 분은 올려주시길 바랍니다.

      좋아요0
    • 구머 2017.12.15 16:18:54

      일반항에 a에 대한 식이 들어가면 안 될것 같습니다...

      좋아요0
    • 여백 패르마 2017.12.15 18:30:20

      사실 그것은 수학적 귀납법을 이용하면 되지 않나요???

      (사실 저 그런것에 자신이 없어서 집에 있는 수학의 정석좀 써야겠어요)

      좋아요1
    • 수학장 2017.12.15 19:20:03

      잘 안 보입니다 좀 크게 해주세요

      좋아요0
    • 구머 2017.12.15 19:42:25

      음..저 식 되게 복잡해서 귀납법으로는 일반항을 유도하기 힘들것 같아요.

      좋아요0
  • 구머 2017.12.15 15:49:48

    3번을 풀다가 괜찮은 점화식 하나를 증명했습니다. 그 점화식은 다음과 같습니다.

    점 2k개가 직선 모양으로 배열된 그래프를 G2k라고 표현했을때,

    \small \small a(G_{2k})=(a(G_0)a(G_{2k-2})+a(G_2)a(G_{2k-4})+...+a(G_{2k-2})a(G_0))

    가 성립합니다. 그리고, a(G0)은 문제의 정의에 의해 1이므로, 이 점화식을 잘 이용하면 3번이 해결될 것 같습니다.

    좋아요0 댓글수13
    • 수학장 2017.12.15 17:26:58

      a(G _{0})a(\o )와 같으므로 1입니다.

      좋아요0
    • 수학장 2017.12.15 17:40:42

      이거 유도과정 좀 볼 수 있을까요

      좋아요0
    • 구머 2017.12.15 20:28:59

      아 오타가 났었군요 수정했습니다.

      좋아요0
    • ♥️ 2017.12.15 21:52:48

      유도과정에 대해서는 힌트를 드릴게요:

      부분유도그래프들을 '가장 앞쪽에 있는 점을 포함하는 가장 긴 연결그래프의 길이'에 따라 분류해 보세요.

      그리고 계산하실때 홀수개의 점을 가진 일직선 그래프의 a를 정의하면 계산이 편리해질겁니다

      (닉 변경:구머->♥️)

      좋아요0
    • ♥️ 2017.12.16 00:25:39

      점화식을 풀었습니다. 알고 보니 카탈란 수열과 구성이 비슷하더군요.

      답:2k개의 점을 가진 일직선 그래프의 a값=\frac{1}{k+1}\binom{2k}{k}×(-1)^k

       

      좋아요0
    • 수학장 2017.12.16 08:10:01

      맞는지 틀렸는지 확인해야 되니까 유도과정 좀 보여주세요

      좋아요0
    • 여백 패르마 2017.12.16 15:06:09

      그런데요 구머에서 왜 heart로 바꾸셧나요??(구머가 훨 나았는 데 말이죠)

      좋아요0
    • 구머 2017.12.16 18:24:52

      (귀찮아...)3번: 편의상 x개의 점을 가진 일직선 그래프를 Gx라고 정의하자. 또, 문제를 풀기 위해 새로운 함수 b를 다음과 같이 정의하자.

      =========================

      i)  그래프 G에 대해서,  \small b(G)=-\sum_{H\subsetneq G}{a(H)}

      ii) 공집합의 b값=1

      =========================

      만약, G가 홀수개의 점을 가지는 연결성분을 가지지 않는다면, b(G)와 a(G)는 값이 같음을 알 수 있다. 

      #1. b(G2k-1)의 값

       G2k-1의 부분유도그래프들을 'G2k-1의 가장 앞에 있는점을 포함하는 연결성분의 길이'로 분류하자. 그리고, 이 길이가 i인 부분유도그래프들의 집합을 Si집합이라고 정의하자.(맨 앞에 있는 점을 포함하지 않는 그래프들은 S0에 포함) 이때, Si에 속한 그래프들은 'G2k-1의 앞에서 i+1번째에 있는 점'을 포함하지 않음을 알 수 있다. 따라서 만약 i가 홀수라면, Si집합의 그래프들의 a값은 전부 0이 된다. 또, 만약 i<=2k-3인 짝수일때, Si에 속한 그래프들의 a값의 합을 구하면, 

      \small \sum_{H\subset S_i}{a(H)}=a(G_i)\sum_{H\subset G_{2k-i}}{a(H)}=a(G_i)(a(G_{2k-i})+\sum_{H\subsetneq G_{2k-i}}a(H))=0

      임이 나온다. 또 i=2k-2일때, S2k-2에 속하는 그래프는 G2k-2밖에 없으므로, S2k-2의 그래프들의 a값의 합은 a(G2k-2)이다. 따라서

       \small b(G_{2k-1})=-\sum_{H\subsetneq G_{2k-1}}^{ }{a(H)}=-\sum_{i=0}^{2k-2}\sum_{H\subset S_i}a(H)=-a(H_{2k-2})

      라는 결론이 나온다. //

      #2. a(G2k)에 대한 점화식

      (#1과 접근방식이 비슷하다) G2k의 부분유도그래프들을 'G2k의 가장 앞에 있는점을 포함하는 연결성분의 길이'로 분류하자. 그리고, 이 길이가 i인 부분유도그래프들의 집합을 Si집합이라고 정의하자.(맨 앞에 있는 점을 포함하지 않는 그래프들은 S0에 포함) 이때, Si에 속한 그래프들은 'G2k의 앞에서 i+1번째에 있는 점'을 포함하지 않음을 알 수 있다. 따라서 만약 i가 홀수라면, Si집합의 그래프들의 a값은 전부 0이 된다. 또, 만약 i<=2k-2인 짝수일때, Si에 속한 그래프들의 a값의 합을 구하면, \small \small \sum_{H\subset S_i}{a(H)}=a(G_i)\sum_{H\subset G_{2k-i-1}}a(H)=-a(G_i)b(G_{2k-i-1})=a(G_i)a(G_{2k-2-i})

      가 되고, 따라서 

      \small a(G_{2k})=-(a(G_0)a(G_{2k-2})+....+a(G_{2k-2})a(G_0))가 성립한다.

      #3. 점화식 풀기

      \small a(G_{2k})=(-1)^kC_k가 성립함을 보이자.(Ck는 k번째 카탈란 수이다)

      먼저 k=0,1일때는 잘 성립함을 알 수 있다. 이제 k<=n일때 성립한다고 가정하고, k=n+1일때 성립함을 보이자. 

      \small a(G_{2n+2})=-(a(G_0)a(G_{2n})+....+a(G_{2n})a(G_0))=(-1)^{n+1}(C_0C_{n}+...C_nC_0)=(-1)^{n+1}C_{n+1}

      ....보였다. 따라서  \small a(G_{2k})=(-1)^kC_k가 성립하고,  \small a(G_{2k})=(-1)^k\frac{1}{k+1}\binom{2k}{k}><

      좋아요0
    • 수학장 2017.12.16 19:00:06

      ㄷㄷㄷ 잘 푸셨네요 그러고 보니까 진짜로 카탈란 수열과 같네요. 그런데 \binom{a}{b}=\frac{a!}{b!}

      맞죠?

      좋아요0
    • 구머 2017.12.16 21:22:36

      음..저 풀이는 틀렸습니다 중간에 부호착각한게 있었네요. 그래도 그냥 수정하면 될것 같습니다

      그리고\binom{a}{b}=\frac{a!}{b!(a-b)!}입니다.

      좋아요0
    • 여백 패르마 2017.12.16 21:56:42

      그리고 수학장님이 말하신 것은 순열입니다.

      또, 수학장님이 말하신 점이 10개인 일직선의 값은 -81인데 구머님의 공식을 이용하면 -82이네요..

      좋아요0
    • 구머 2017.12.16 21:59:21

      아마 수학장님이 계산실수를 하셨을 껍니다.(데넵님 의견에 의하면)

      좋아요0
    • 여백 패르마 2017.12.16 22:00:31

      아마도 공집합을 빼먹으신 것 같네요..

      좋아요0
  • 수학장 2017.12.16 19:38:18

    4번이 난제네요 하나의 연결성분일 때 일자 모양하고 고리 모양밖에 없는 줄 알았는데 그게 아니었으니

    좋아요0 댓글수0
  • 여백 패르마 2017.12.16 21:41:03

    세로 찍어 봤고요, 일자일 때의 부호를 지금 이 공식으로 중명 가능 한 듯 합니다.

    좋아요0 댓글수3
    • 여백 패르마 2017.12.16 21:53:13

      여기에서 수학적 귀납법을 이용합시다. 

      맨 처음으로 2개일 때는 만족하고요.

      임의의 2m에 대해 만족하면 2m+2에도 만족한다는 것을 증명합시다. 

      2m이 4의 배수일때 a(2m)을 구합시다. 그것은 a(2m+2)일 때의 처음 부분들과 같습니다.a(2m+2)를 구해봅시다. a(2m)의 부호는 +일 것입니다.그리고 a(2m+2)의 급수에서  a(2m)의 부분 을 빼고 남은 부분은 a(2m)에다가 -큰수를 곱한 것과 같기때문에 전체의 부호는 -일 것입니다.

      또, 같은 논리로 m이 홀수일 때도 a(2m+2)의 부호는 +일 것입니다.

      Q.E.D

      구리고 고리는 일직선을 굽히고 점 하나를 뺀 것이기 때문에 같고 부호는 4번을 만족할 것입니다.

      좋아요0
    • 구머 2017.12.16 22:00:53

      일자일때는 제 3번 풀이에서 부호가 결정됬습니다.

      좋아요0
    • 수학장 2017.12.16 22:09:58

      a(2m+2)가 a(2m)보다 절댓값이 크다는 건 직관적으로 알 수 있겠지만 점이 충분히 많은 그래프 G에서 a(2m+2)보다는 a(2m)이 더 수가 많기 때문에 그걸 그렇게 간단히 증명할 수는 없습니다. 그리고 위에서 말했듯이 우리는 단순그래프를 잘 못 이해하고 있었습니다. 그래서 1번 수정을 보낸 것입니다. 연결 성분이 1개여도 일자 모양과 고리 모양만 있는 게 아닙니다. 수학적 귀납법으로 a(2m)의 부호가 (-1)^{m}일 때 a(2m+2)의 부호가 (-1)^{m+1}임을 증명하면 될 것 같습니다. 물론 모든 그래프에 대해 그래야 되겠죠 일단 점이 4개 일 때는 1번 풀이를 보시면 알겠지만 부호가 +로 만족합니다.

      좋아요0
  • 구머 2017.12.16 22:11:13

    여기 수식 편집기에서 \small \nsubseteq이 2개가 있고 \small \subsetneq가 없는데 이 부분 좀 수정 부탁드립니다.

    좋아요0 댓글수0
  • 여백 패르마 2017.12.17 16:10:06

    4번 풀어봤습니다.

    좋아요0 댓글수10
    • 여백 패르마 2017.12.17 16:24:59

      엑스 표시는 구머님 것을 좀 따라 했는데, 혹시 저작권 침해?????

      또, 오류가 있을 확률:99.9999999999999999999999999999

      좋아요0
    • 여백 패르마 2017.12.19 21:34:24

      왜 어디가 이해 안 이해되나요????

      좋아요0
    • 구머 2017.12.20 16:49:39

      다음에 All rights reserved라도 붙여야겠다ㅋㅋ

      좋아요0
    • 수학장 2017.12.20 17:55:31

      작을 수록 그래프가 많아지는 건 아닙니다 점의 개수가 2m일 때 m개인 부분유도그래프뷰터는 점점 개수가 작아집니다

      좋아요0
    • 여백 패르마 2017.12.20 19:32:06

      All rights reserved 가 뭔가요??(영어를 좀....)

      또, 일직선의 놈을 봐도 •-•가 •-•-•-•보다 훨씬 더 많은 데요..

      좋아요0
    • 구머 2017.12.20 20:01:46

      All right reserved는 '저작권을 소유한다'라는 의미로 생각하시면 됩니다.

      좋아요0
    • 여백 패르마 2017.12.20 20:45:53

      그런가요??

      좋아요0
    • 수학장 2017.12.20 22:32:10

      저 증명 아래에 G.E.V는 무슨 뜻이죠 궁금해요

      좋아요0
    • 구머 2017.12.20 23:25:37

      아래에 적힌건 Q.E.D입니다. '증명이 완료되었다'를 의미합니다.

      좋아요0
    • 여백 패르마 2017.12.22 20:14:44

      왜 G.E.V로 보이는지 모르겠네요...(ㅋㅋㅋ)

      좋아요0
  • 수학장 2017.12.18 23:13:10

    그래프 G의 점의 개수가 2m인 모든 단순그래프 G의 a값의 합을, G의 개수가 s라고 했을 때a(G _{2m}) \bullet s라고 정의하자.

    점의 개수가 2m인 임의의 G를 이렇게 풀자.a(G)=-(a(G _{2m-2}) \bullet \frac{2m(2m-1)}{2}+a(G _{2m-4})\bullet\frac{2m(2m-1)(2m-2)(2m-3)}{24}+.....)

    그런 후에 a(G _{2m-2}) \bullet \frac{2m(2m-1)}{2}를 다시 -(a(G _{2m-4}) \bullet (\frac{2m(2m-1)}{2})(\frac{(2m-2)(2m-3)}{2}))로 풀자 이 때 -(a(G _{2m-4}) \bullet (\frac{2m(2m-1)}{2})(\frac{(2m-2)(2m-3)}{2})가 a(G _{2m-4}) \bullet \frac{2m(2m-1)(2m-2)(2m-3)}{24}보다 절댓값이 크다는 걸 알 수 있다 두 식에서

    (\frac{2m(2m-1)}{2})(\frac{(2m-2)(2m-3)}{2})-\frac{2m(2m-1)(2m-2)(2m-3)}{24}=p(\geq 0)

    라고 놓자. 그러면a(G)=-(-a(G _{2m-4}) \bullet p+.......)가 되므로 2m개의 점을 가진 임의의 G는 2m-4개의 점을 가진 임의의 G와 부호가 같음을 알 수 있다 점이 2m-6 이하인 부분유도 그래프를 뺀 이유를 알려준다. 점의 개수가 2m-6인 부분유도그래프는 \frac{(2m)!}{(2m-6)!6!}개이다. -(-a(G _{2m-4}) \bullet p)를 분해한 것이 저것보다 절댓값이 크다는 것을 해보기 바란다. 쉽게 알 수 있다.몇 번을 반복해도 절댓값이 더 클 수는 없다. (오류 수정 완료) 2m개의 점을 가진 G와 2m-4개의 점을 가진 H가 부호가 같다는 것이 증명되었다. 이 때, 점이 2개일 때는 a값이 모두 음수이고, 점이 4개일 때는 a값이 모두 양수이다.(위의 1번 풀이 참고) 2m개의 점을 가진 G의 부호는 (-1)^{m}과 같다. 4번 증명 완료. 오류 발견하신 분이나 이해가 안 되시는 분은 댓글 남겨주세요

    좋아요0 댓글수21
    • 여백 패르마 2017.12.19 18:56:40

      처음 식이 틀린  것같은 대요??

      원래 부분유도그래프가 그렇게 간단하게 나오지 않아요

      좋아요1
    • 수학장 2017.12.19 19:57:21

      왜죠? 물론 임의의 점을 뽑아 부분유도그래프를 만들었기 때문에 • 이거 뒤에 수 중 홀수 개수의 연결성분을 가지는 그래프가 있을 수 있지만 문제가 되지 않습니다

      좋아요0
    • 여백 패르마 2017.12.19 21:30:44

      사실 •-••-•같은 것도 있어요

      좋아요0
    • 수학장 2017.12.19 22:09:32

      그런데요?.....임의의 그래프니까 그거 다 포함한 건데요.

      좋아요0
    • 여백 패르마 2017.12.20 19:35:09

      nCr은 대칭이여서 일자일때 •-•가 •-•-•-•보다 적다는 결과가 나오는 대요..

      좋아요0
    • 수학장 2017.12.20 22:26:28

      예 맞습니다. 대칭이라서 점이 2개인 부분유도그래프가 점이 4개인 부분유도그래프보다 적죠. 하지만, 분해를 반복해서 생긴 값의 절댓값은 점점 커집니다. 그러므로 작아져도 여전히 분해를 반복해서 생긴 개수가 항상 크다는 것을 알 수 있습니다.(오히려 더 차이가 벌어지죠.)(틀렸다고 논리적으로 답해주세요)

      좋아요0
    • 구머 2017.12.21 00:06:41

      첫식에서 a(G2m-2)의 개수에서 오류가 있는듯 합니다. 홀수개수의 점을 가진 연결성분을 가진 부분그래프들을 고려해주어야 합니다.

      좋아요0
    • 수학장 2017.12.21 08:07:23

      홀수 개수의 연결성분을 가진 것이 있어도 상관없지 않나요? 별로 큰 문제는 없을 것 같은데요

      제가 보니까 홀수 개수는 분해하면 오류가 생기는데 어차피 짝수 개수인 것만 분해해도 임의의 2m-4개의 점을 가진 그래프는 항상 어떤 2m-2의 부분유도그래프인 거는 확실하잖아요

      그런데 모든 2m-2개의 점을 가진 것 여러 개 중에 교집합이 생기는데 그 교집합 때문에 어차피 2m-2개의 점을 가진 그래프들을 분해한 것이 2m-4개의 점을 가진 부분유도그래프보다 많습니다.

      좋아요0
    • vorn 2017.12.23 21:21:22

      그런데 그 부분을 논리적으로 증명해야 하지 않을까요?

      좋아요0
    • 수학장 2017.12.23 21:42:38

      요 대댓글로 증명한 거 아닌가요? 교집합 때문에 겹치는 게 생겨서 분해한 것이 원래 것보다 많다고 증명한 건데요

      꼭 수식을 이용해서 식을 풀지 않아도 논리적으로 옳다고 유도한 것도 증명입니다.

      좋아요0
    • vorn 2017.12.23 22:17:45

      그 부분 말고 2m-6개 이하의 부분의 논증이요. '점의 개수가 2m-6인 부분유도그래프는 \frac{(2m)!}{(2m-6)!6!}개이다. -(-a(G _{2m-4}) \bullet p)를 분해한 것이 저것보다 절댓값이 크다는 것을 해보기 바란다. 쉽게 알 수 있다.몇 번을 반복해도 절댓값이 더 클 수는 없다.' 이 부분을 이런식으로 하기에는 논리가 부족한듯 합니다.

      좋아요0
    • 수학장 2017.12.24 13:06:36

      점 2m개 중에 점 2m-6개를 뽑는 경우의 수가 점의 개수가 2m-6인 부분유도그래프의 개수입니다. 그러므로 \frac{(2m)!}{(2m-6)!6!}인 것에 더 이상의 부가설명은 하지 않겠습니다.

      그리고 그 다음 문장 설명할게요 일단 p를 구하면 2m-2개의 점을 가진 부분유도그래프에서의 교집합이 남는데요 이 교집합들은 2m-4개의 점을 가진 모든 부분유도그래프들을 포함함은 자명합니다. 이것만 분해해도 또다시 2m-4개의 부분유도그래프를 분해한 것이 되는데, 이때도 마찬가지로 교집합이 생깁니다. 이것만 분해해도 2m-6개의 점을 가진 부분유도그래프보다 절댓값이 큽니다. 그런데 여러번 겹친 부분유도그래프들도 있죠. 이것들도 분해하다보면 절댓값은 기하급수적으로 커지고, 점점 할 수록 더 이상 원래의 부분유도그래프의 절댓값으로는 감당이 안 됩니다. 분해할 때마다 부호만 바뀔 뿐이지요.

      좋아요0
    • 여백 패르마 2017.12.24 13:56:10

      네 개수는 맞습니다 하지만 점의 개수가 같다고 그 그래프가 같지 않고 a값이 같지 않습니다.그래서 그냥 개수에다가 그 점의 개수인 그래프를 G2m-6라고 하고 a값을 구해서 곱하면  않됩니다.

      좋아요0
    • vorn 2017.12.24 15:21:56

      그런데 저건 너무 직관적으로 접근한것 같아요..좀더 확실한 증명이 필요합니다.

      좋아요0
    • 수학장 2017.12.25 11:49:37

      여백페르마님  말씀대로 모두 a값이 다르지만 저거는 포함관계를 설명하기 위해 새로 만든 기호로, ‘절댓값이 크다’라고 설명한 것은 ‘절댓값이 작다’라고 설명한 것을 포함하는 더 큰 집합이라고 생각하시면 될 것 같습니다 vorn님 맞습니다 여기에 쓴 건 약간 직관적이지요 그런데 수학적귀납법으로 충분히 증명될 것 같습니다. 그거는 이 댓 보시는 분이 해주세요 저는 시간없어요. 만약 증명하다가 오류 발견하면 대댓글 남겨주세요.

      좋아요0
    • 여백 패르마 2017.12.25 14:44:32

      좋아요1
    • 여백 패르마 2017.12.25 14:45:59

      사진은 아무리 해도 똑바로 안 나와요..

      좋아요0
    • 구머 2017.12.25 15:28:23

      사진 찍을때 카메라를 돌려서 찍으면 해결됩니다. 그리고 4개를 뽑으실때 점의 개수가 4개가 되게 뽑으셔야 합니다. 변의 개수는 상관이 없습니다,

      좋아요0
    • 수학장 2017.12.25 20:55:29

      변의 개수가 아닌 점의 개수입니다 임의의 점을 뽑으면 그 점들끼리 잇는 모든 변을 포함한 것이 부분유도그래프입니다. 다음 문제 빨리 나오면 좋겠네요 언제 공개될까요

      좋아요0
    • 여백 패르마 2017.12.26 22:11:21

      그러면 •-•   •-•같은 부분유도그래프는 못 생각하지  않나요??

      좋아요0
    • 수학장 2017.12.26 22:31:06

      여백패르마님 예를 들어 G=(V, E)를 이렇게 정의합시다.

      V=\left \{ 1,2,3,4,5,6 \right \}, E=\left \{ \left \{ 1,2 \right \},\left \{ 2,3 \right \},....,\left \{5,6 \right \} \right \}그러면 여기서 점 1,2,5,6을 뽑읍시다. 그러면 E=\left \{ \left \{ 1,2 \right \} ,\left \{ 5,6 \right \}\right \}이므로 •-• •-•모양도 나올 수 있습니다. 따라서 이렇게 증명하든 다르게 증명하든 E는 V에서부터 나오기 때문에 임의의 변을 뽑는 것이 아닌 임의의 점을 뽑으셔야 합니다.

      좋아요0