본문바로가기
폴리매스 문제
세상에 없던 문제에 도전하세요!
[대한수학회] 대59. 그래프와 연결 부분그래프의 성질
수학동아 2021.11.05 10:21 조회 286

이번에는 다시 그래프에 관한 문제를 다루려 한다. 다음은 예전 그래프를 다룰 때 소개했던 그래프에 대한 기본 이론이다. 이번 문제에도 중요한 개념이니 다시 한 번 복습하자.

 

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

 

P_{4} = 

 

② 그래프가 연결되어 있다는 것은 그래프의 임의의 점의 쌍에 대해서 한 점에서 출발하여 변으로만 이동해서 다른 점으로 갈 수 있다는 뜻이다. 그래프 G가 연결된 몇 개의 성분으로 나누어질 때, 각 성분을 그래프 G의 연결성분이라 부르자.

 

③ 단순그래프 G=\left ( V_{G}, E_{G} \right )의 부분유도그래프 H=\left (V_{H}, E_{H} \right )G에 포함되는 점의 부분집합에 대하여 그 부분집합으로 구성되는 모든 변을 다 모은 것이다. , V_{H} \subset E_{H}이고E_{H}=\left \{ \left \{ v, w \right \}\in E_{V}\mid v, w\in V_{H} \right \}를 만족하는 그래프이다.

 

-------------------------------------------------------------------------------------------------------------------------------------

 

연결된 그래프 G의 점의 집합을 \left \{ 1, 2, \cdots , n+1 \right \}라 하자. 각 점 i에 대해서 i를 점으로 가지면서 G의 연결된 부분유도그래프의 개수를 k_{i}라 정의하자. 이제 k_{i} 중에서 가장 작은 것을 k\left ( G \right )라 부르자.

 

k\left ( G \right )=min\left \{ k_{i}\mid i=1, 2, \cdots , n+1 \right \}

 

문제1-1.

완전그래프란 모든 점의 쌍을 변으로 가지는 그래프이다. n+1개의 점을 가지는 완전그래프 K_{n+1}에 대하여 k\left ( K_{n+1} \right )을 구하여라.

 

문제1-2.

자신이 알고 있는 그래프 G에 대하여 k\left (G \right )를 구하는 공식을 만들어 보아라.

 

 

문제2.

만약 k_{n+1}=k\left ( G \right )가 성립하면, 집합 \left \{ 1, \cdots , n \right \}로 유도되는 부분유도그래프는 연결임을 증명하여라.

 

 

문제3.

그래프 G의 연결된 부분유도그래프의 개수를 b(G)라 하자. 다음 부등식을 증명하여라.

 

n\cdot k(G)\geq b(G)-1

 

문제4-1.

k_{n+1}=k(G)이고 그래프 H가 집합 \left \{ 1, \cdots , n \right \}로 유도되는 부분유도그래프일 때, 다음 부등식이 성립함을 보여라.

 

b(G)-k(G)\geq b(H)

 

문제4-2.

위 문제4-1은 다음처럼 확장될 수 있다. k_{n+1}=k(G)이고 그래프 H가 점 n+1을 가지지 않는 G의 연결된 부분유도그래프일 때, 다음 부등식이 성립함을 보여라.

 

1+(\left | H \right |-1)a\geq b(H)

 

(, \left | H \right |H의 점의 개수를 의미하고, a=\frac{b(G)-k(G)-1}{n-1}이다.)

 

  •  
    원파 Lv.9 2021.11.08 00:03 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수1
    •  
      김다인(멘토) Lv.5 2021.11.22 01:35 비밀댓글
      비밀 댓글이 등록 되었습니다!
  •  
    원파 Lv.9 2021.11.08 00:31 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수1
    •  
      김다인(멘토) Lv.5 2021.11.22 01:40 비밀댓글
      비밀 댓글이 등록 되었습니다!
  • 폴리매스 문제는 과학기술진흥기금 및 복권기금의 재원으로 운영되고, 과학기술정보통신부와 한국과학창의재단의 지원을 받아 수행된 성과물로 우리나라의 과학기술 발전과 사회적 가치 증진에 기여하고 있습니다.

  • ☎문의 02-6749-3911