시작은, 해당 문제랑 동치인 문제를 만드는 것으로 시작합니다.
그 문제는 흰 꼭짓점 두개를 원처럼 연결한 그래프에서 시작하며,
흰돌 하나를 넣을 때 마다 인접 두 돌의 색을 바꿀 때, 모든 돌의 색이 흰돌을 만드는 문제입니다.
위 그래프를, 돌 추가시 변화를 잘 보기위해 아래와 같이 변형했습니다.
위 그래프의 특성을 바탕으로 가능한 흰 그래프의 유형을 나눠,
왜 특정 수의 흰 그래프가 불가능 한지 밝혔습니다ㅡ.
Sprout게임 생각남
시작은, 해당 문제랑 동치인 문제를 만드는 것으로 시작합니다.
그 문제는 흰 꼭짓점 두개를 원처럼 연결한 그래프에서 시작하며,
흰돌 하나를 넣을 때 마다 인접 두 돌의 색을 바꿀 때, 모든 돌의 색이 흰돌을 만드는 문제입니다.
위 그래프를, 돌 추가시 변화를 잘 보기위해 아래와 같이 변형했습니다.
위 그래프의 특성을 바탕으로 가능한 흰 그래프의 유형을 나눠,
왜 특정 수의 흰 그래프가 불가능 한지 밝혔습니다ㅡ.
Sprout게임 생각남
와우
두 문제가 동치인 이유가? 동치라고 쳐도 한변만을 끊는 것으로 다시 봉모양 그래프로 돌릴 수 있어야 하므로 작업도 이미 존재하는 변 사이에서 행해지는 작업2밖에 불가능할텐데
https://m.dcinside.com/board/math/39155?page=3
원에서 봉으로 가는 방법은 이렇습니다. G”1중 한 꼭짓점을 G”n에서 추적해서 없애기만 하고, 나머지 꼭짓점들의 색은 없애기 전의 변의 홀 짝 여부로 결정하면 됩니다
사실 그 부분보다는, 고리베이스 흰 그래프를 전부 따지지 못한 거 같습니다. 첫항=4일때 n+3/ 2n-1 보다 훨씬 많은 흰그래프가 있는 게 생각났는데, 저는 이만 이 문제는 놓으려고 합니다.
고리베이스 흰 그래프에 추가점이 생겼을때, 추가점 인접점 두개중 한개를 시점, 나머지를 종점이라고 이름 붙입니다. 그 다음, 점추가를 “다리놓기”라고 하면, 시점에서 종점까지 다리를 놓았을때 다시 고리베이스 흰 그래프가 됩니다. 모든 다리놓기 경우의 수를 따져야지, 경우의 수에 포함 안된 경우를 불가능하다고 증명한게 되는데, 저는 모든 경우의수를 못따졌어요
그런데 어차피 문제는 봉 모양그래프만 확인하면 되어서 그 그래프와 동치인 양끝을 이어붙인 원 모양 흰정점 그래프만 확인하면 되는거 아닌가요?
네 맞아요. 그렇게 접근하는게 더 현명한 방법 같네요. 여집합으로 가는 것보다
바나나 / 링베이스 흰 그래프가 왜 3n개에서 안되는지 직접적으로 밝히는게 더 나앗을 듯 하네요 지금 생각해보니