대한수학회 60번
그래프의 가까운 변들의 모임
문제 출제자 : 김린기 인하대학교 수학과 교수
그래프에서 서로 다른 두 변이 한 점을 공유하거나 두 변을 연결하는 변이 존재할 경우, “두 변은 가깝다”라고 한다. 아래 그래프에서 과
는 한 꼭짓점을 공유하므로 둘은 가깝다.
과
는 꼭짓점을 공유하지는 않지만
가 두 변을 연결하므로
과
도 가깝다. 하지만
과
는 가깝지 않다.
그래프 의 변으로 구성된 집합
에 대하여,
의 임의의 두 변이 서로 가까우면
를 “가까운 변의 집합”이라 하자. 위의 그래프에서
와
는 가까운 변의 집합이다. 그리고 그래프
의 가까운 변의 집합 중 가장 큰 것의 크기를
로 표기하자.
문제1. 은 길이가
인 순환그래프(cycle)이다. 정의에 의하면
라는 것을 쉽게 알 수 있다. 5 이상인 자연수
에 대하여
을 구하여라.
문제2. 임의의 짝수 에 대하여
이고
인 그래프 가 존재할까? (
는
의 최고 차수이다.)
문제3. 그래프 는
가 가까운 변의 집합을 이루는 그래프이다.(여기서
는
의 모든 변을 포함하는 집합이다.) 즉,
의 임의의 두 변은 한 꼭짓점을 공유하거나, 둘을 연결하는 다른 변이 존재한다. 예를 들어,
는 위의 성질을 만족한다.
이때 을 증명하여라.
문제4. 이분그래프 에 대하여
임을 증명하여라.
1번에서 제가 잘못 이해한 것 같은데 이고
부터는 계속 3이 되는 것 같은데 설명해주실 수 있나요? 인접한 세 변만이
가 되서... (죄송해요 제가 그래프 이론을 모릅니다)
(글고 애초에 순환그래프를 몰라서 위키피디아에 쳐봤더니 정다각형 그래프라던데 맞나요?)
어느 부분에서 문제를 잘못 이해했다고 생각하셨는지 더 말씀해주실 수 있나요? 5 이상의 n에 대하여 을 구하는 것이 문제입니다!
그리고 순환그래프는 정다각형 그래프가 맞습니다! 다른 질문 있으시면 댓글 부탁드릴게요^^
다인 멘토 드림
저는 5이상에서도 계속 5가 나오는데요..?
그니까 육각형을 예로 들자면 한 변으로부터 인접한 두 변과 그 변과 연결되어있는 두 변, 총 5개인 것 같아요
5일 때는 5 맞고 6이상일 때는 임의의 두 원소에 대해서 거리가 2 이상이면 안 되므로 3 맞는듯요.
6 이상일 때 w(Cn) 값이 4 이상이면 반드시 거리가 2 이상인 두 변이 생기거든요.
@Scubed
정육각형을 예로 들자면
서로 마주보는 면은 가까운 면이 아니니
기껏해야 한 면 + 꼭짓점으로 맞닿아 있는 두 면 해서 w(C_6)이 3이 나오는 것 같습니다
좀 더 엄밀하게 이야기해 보겠습니다.
n = 5일 때는 C5 전체가 가까운 변의 집합이므로 답은 5입니다.
n >= 6일 때 연속한 3개를 잡아보면 이는 가까운 변의 집합입니다. 이것이 최댓값임을 보이기 위해 w(Cn)의 값이 4 이상인 집합 S가 존재한다고 가정해봅시다. 고립된 변이 있으면 가까운 변의 집합일 수 없으며, Cn은 정다각형 그래프이므로 집합 S는 일직선 형태일 것입니다. 이때, 집합 S의 모든 변을 일직선 순서대로 E1, E2, E3, E4, ...라고 합시다.
E1, E4의 거리는 두 방향에서 잴 수 있는데, 그 길이는 2와 n-4입니다. 그런데 이 두 수는 모두 2 이상이므로 가까운 변의 집합이 될 수 없습니다. 따라서 w(Cn)의 값은 4 이상일 수 없으며, 답은 3입니다.
답 : n = 5이면 5, n >= 6이면 3
@222
고렇네요 제가 실수했네요 ㅠㅠ
혹시 이런 문제를 취미로 풀어보고 싶다면 어떻게 공부해야할까요ㅠㅠ 수능이나 내신대비를 위한 수학만 해서 이런 수학문제를 푸는 것에는 익숙하지 않은데 이런 문제를 해결하는 것을 공부할 수 있는 책이 있을까요?
1)
최대한 정리해서 말하겠습니다.
정다각형 그래프에서, w(C5)는 5이고, 그 뒤는 모두 3입니다.
우선, 최대인 점들이 존재할려면, 한점에 대해서 그 점에서 한쪽으로는 2개의 점만이 퍼져나가야합니다. 모두 가까워야 되기 때문이지요.
반대도 같고, 그래서 한 점에서 양끝으로 2개가 있는 것이 최대입니다. 하지만, 모든 점에서 가까워야 하므로, 양끝도 가까워야 합니다. 그래서, 양끝을 이어주면 최대인 5가 됩니다.
정다각형 모양을 가진 최대는 5인 것이죠.
그러면, 6이상부터는 이것이 성립하지 않고, w(G)는 직선형이 되면서, 최대가 3이 됩니다.
w(C5)=5, w(C6이상))=3 입니다.
아 그리고 w(G)=5/4뭐시기(G)2인데 집합G를 제곱한건가요 아니면 n을 제곱한건가요??
2번 문제에 대해서, 일반적인 방법을 찾는것이 좋을까요 아니면 수식적으로 증명하는 것이 나을까요?
어? 이거 4색정리 증명할때 나오는 것과 비슷한데 이거 4색정리와도 관련성이 깊은 것 같습니다
풀었습니다. (p.s. pure math님 같이 토론하기로 하고 못해서 죄송합니다ㅠㅠ 숙제가 많아서 가끔씩 눈팅밖에 못했어요)(p.s2 asdf3님 감사합니다 님이 n = 4일 때를 보여주셔서 일반화할 수 있었습니다)
/resources/comment/2022/02/d87d4ae8734db269b92c018c31171af4.jpg
잘 푸셨습니다.
다음과 같은 방법으로 서술할 수도 있습니다.
let n = 2m
다음과 같은 그래프 G를 잡자.
V(G)={(a,b) : 1 <= a <= m, 1<= b <= 5}
E(G)={{(a,b),(c,d)} : b-d가 mod5로 1 or -1}
let f(v) = v의 두 번째 index in mod5.
각각의 점은 f(v)값이 1 차이나는 점과 연결되고 차수 2n.
한편, {v1,v2}, {v3,v4}가 이웃하지 않다면 v1,v2는 v3,v4와 연결되지 않고 일반성을 잃지 않고 f(v1)=0, f(v2)=1일 때, f(v3)=f(v4)=3이고 모순.
따라서 모든 변이 이웃하고 w(G)=|E(G)|=5m^2
와!!! 축하드려요!!! 다음엔 시간 날 때 같이 문제 풀어봐요!!!
유태영 멘토님, pure math님 모두 감사합니다!