본문바로가기
폴리매스 문제
아직 아무도 답을 모르는 문제에 도전하세요!
[대한수학회] 대59. 그래프와 연결 부분그래프의 성질
수학동아 2021.11.05 10:21 조회 1282

대한수학회 59번

 

그래프와 연결 부분 그래프의 성질

 

 

문제 출제자 : 최수영 아주대학교 수학과 교수

 

 

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

 

① (유한)그래프는 유한한 점의 집합에 대해서 각 점의 쌍을 서로 변으로 연결한 것이다. 이때 어떤 두 점도 많아야 한 개의 변으로 연결되어 있고, 각 변은 항상 서로 다른 두 점을 잇는다면 이 그래프를 단순그래프라고 한다. , 단순그래프 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.15 2021.11.22 01:35 비밀댓글
      비밀 댓글이 등록 되었습니다!
  •  
    다시 도전
    원파 Lv.9 2021.11.08 00:31 비밀댓글
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수1
    •  
      김다인(멘토) Lv.15 2021.11.22 01:40 비밀댓글
      비밀 댓글이 등록 되었습니다!
  •  
    Amath Lv.8 2022.06.15 21:10 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수2
    •  
      Amath Lv.8 2022.06.15 21:22

      여기서 '나뉘는 두'라는 말을 빼서 읽어 주세요. 

      좋아요0
    •  
      강지원 멘토 Lv.4 2022.06.23 10:00

      1-1번 잘 풀었습니다

      좋아요0
  •  
    Amath Lv.8 2022.06.15 21:47 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수2
    •  
      강지원 멘토 Lv.4 2022.06.23 10:01

      주어진 그래프가 회로그래프일 때의 k값 잘 구했습니다~

      좋아요0
    •  
      Amath Lv.8 2022.06.23 16:56

      네. 

      좋아요0
  •  
    Amath Lv.8 2022.06.15 22:11 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수2
    •  
      Amath Lv.8 2022.06.15 22:41

      * 가장 처음의 명제는, 등호가 성립할 때도 있으므로 거짓입니다. 가장 처음의 명제를 언급한 이유는 그와 비슷한 형식으로 생각하려고 넣어 둔 거에요. 

      좋아요0
    •  
      Amath Lv.8 2022.06.15 23:23

      아. 실수했어요. 수정해서 올릴게요. 

      좋아요0
  •  
    Amath Lv.8 2022.06.15 23:36 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수1
    •  
      Amath Lv.8 2022.06.17 16:00

      이것도 조금 잘못됐어요. 

      좋아요0
  •  
    Amath Lv.8 2022.06.17 16:24 비밀댓글
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수0
  • 폴리매스 문제는 과학기술진흥기금 및 복권기금의 재원으로 운영되고, 과학기술정보통신부와 한국과학창의재단의 지원을 받아 수행된 성과물로 우리나라의 과학기술 발전과 사회적 가치 증진에 기여하고 있습니다.

  • ☎문의 02-6749-3911