주어진 degree로 구성가능한 simple graph의 존재성

그래프 이론에서 simple graph란 동일한 점을 잇는 edge가 없는 undirected graph를 말한다. 쉽게 말해 고교 교과과정에서 다루는 그런 종류의 그래프이다. (신 교과과정에서는 애석하게도 그래프 이론이 없어졌다.)

여하간, 자연수로 된 finite sequence가 주어질 때, 이 숫자를 degree로 갖는 simple graph가 구성 가능할까? 라는 질문을 할 수 있다. 예를 들어, 3, 2, 2, 1이라는 sequence가 주어지면, 네 vertex로 이루어지고 각 vertex의 degree가 3, 2, 2, 1인 simple graph가 존재 가능하지만, 3, 3, 1 ,1은 불가능하다. 이런 성질을 graphic이라 부른다. 즉, (3, 2, 2, 1)은 graphic sequence이지만, (3, 3, 1, 1)은 graphic이 아니다.

그러면 어떤 finite decreasing sequence가 graphic인지 어떻게 판정할까? 이 질문에 대한 대답이 바로 Erdős–Gallai theorem이다. 실제로 그래프를 구성하지 않고 대수적 계산만으로 그래프가 존재하는지를 파악할 수 있는 필요충분조건이다. 정리의 완전한 statement는 위키피디아를 참조하시길.

뭐 여기까지는 그렇다 치고, 그런 그래프를 어떻게 만들까? 주어진 degree에 대해 직접 construct하는 알고리즘은 없는 듯 하다. 그러나 꽤 유용한 정리가 있다. 체코 수학자 Havel과 이란 수학자 Hakimi(시차가 좀 나니 아마 독립적인듯?) 증명한 Havel-Hakimi theorem이다. 뭔 내용인고 하면, 어떤 decreasing sequence가 graphic인 거랑, 제일 큰 수를 지우고 그 밑으로 제일 큰 수 만큼 1씩 뺀 새로운 decreasing sequence가 graphic인 거랑 동치라는 이야기이다. 즉, (d_1 , d_2 , \cdots , d_n )이 graphic인 것과, (d_2 -1 , \cdots , d_{d_1 +1}-1 , d_{d_1+2}, \cdots , d_n )이 graphic인 것은 동치라는 것. vertex가 하나 줄었으니 사정이 나아진다. 이 작업을 반복적용하면 쉽게 graph를 construct 할 수 있다.

여하간 이 사이트에서 직접 그래프 만들기 게임을 해 보시라. 애석하게도 모바일은 안 되는 듯 하니, 데스크탑으로 볼 것.

Havel-Hakimi in Jacopo Notarstefano

Havel-Hakimi 알고리즘을 따라 simple graph를 construct해보면 나름 재미있다. 아 사이트 하나 소개하기 힘드네-_-

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

%s에 연결하는 중