본문바로가기
폴리매스 문제
세상에 없던 문제에 도전하세요!
[슬기로운 수학생활] 슬6. 그래프와 집합
수학동아 2020.10.05 19:05

그래프 G는 유한한 꼭짓점의 집합 V와, V의 서로 다른 두 점을 잇는 일부 변의 집합 E로 이뤄진 구조다. 이때 꼭짓점과 변의 위치나 모양은 중요하지 않고, 각 꼭짓점이 어떤 다른 꼭짓점과 변으로 연결돼 있는지가 중요하다. 한 변의 양 끝점은 무조건 다르고, 특정한 두 점을 잇는 변은 최대 1개밖에 없다. 즉, 서로 다른 두 변은 양 끝점이 둘 다 같을 수 없다.

 

 

G의 독립집합 W란 어떤 두 점도 서로 연결되지 않은 꼭짓점의 집합을 말한다. 예를 들어, 아래 그래프에서 \left \{ e, d, f \right \}는 독립집합이고, \left \{ b, e, d, f \right \}는 b와 e가 연결돼 있으므로 독립집합이 아니다.

 

 

(출처:대한수학회 45번 문제)

 

 

각 꼭짓점 v에 대해, v의 차수 d(v)는 v와 직접 연결된 변의 개수다. 예를 들어 위 그래프에서 d(a)는 4다.  그래프 G에 대해 독립집합의 최대 크기를 \alpha(G)라고 하자. 위 그래프에서는 \alpha(G)의 값이 3이다.

 

 

문제1 다음을 증명해보자.

 

\alpha(G)\geq \sum_{v\in V}\frac{1}{d(v)+1}

 

여기서 우변의 \sum_{v\in V} 기호는 모든 꼭짓점 v에 대해 \frac{1}{d(v)+1}의 값을 합한다는 뜻이다.

 

 

문제2문제1의 부등식에서 등호조건이 성립할 조건은 무엇인가?

 

 

문제3문제1의 부등식을 더 개선할 수 있을까? 즉, 각 꼭짓점의 차수들을 가지고 \alpha(G)가 최소 얼마인지를 계산하거나, 문제1보다 더 좋은 하한을 만들 수 있을까?

 

 

 

  •  
    수학꿀잼 Lv.2 2020.10.06 00:02 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수0
  •  
    hgmhc Lv.2 2020.10.21 23:56

    일단 너무 어려워서 생각해 본 것들만 적어봅니다.

    컴포넌트들이 합쳐지는 과정을 주목하면 되지 않을까 싶습니다.

    컴포넌트 2개가 각각 알파1, 알파2의 값을 지녔다면, 두 컴포넌트에서 임의의 노드 2개를 연결해주는 과정에서 알파1+알파2가 되거나 알파1+알파2-1이 될텐데, 그냥 합해진 것은 자명할테고 -1이 된 경우에 대해 어느정도 넉넉함을 보여야 할 것 같습니다.

    제가봐도 뭔 소린지 난해하네요.

    그래서 생각해 본 것은 이분그래프? 정도입니다.

    각이 안 나와요ㅠ

    많이 도와서 풀었으면 좋겠네요

    댓글 작성하기 좋아요0 댓글수0
  • 폴리매스 문제는 2019년도 정부의 재원으로 한국과학창의재단의 지원을 받아 수행된 성과물입니다.

  • ☎문의 02-6749-3911