내 신청현황
종류	모집공고명	진행상태
신청내용이 없습니다.

알림마당

그래프의 클래스와 알고리즘

전문가 제언: ○ 이 분석에서 소개된 그래프 클래스는 그래프의 성질을 정적(靜的)으로 설명한 그래프 이론에서 나온 접근 방식이다. 이와는 달리, 어떤 조건 하에서 그래프를 랜덤하게 생성하는 모델도 있다. 이것은 1960년대에 제안된 ‘Random Graph로, 1980년대 이후 활발하게 연구한 분야이다.

○ 최근 www로 대표되는 인터넷상에서의 서비스는 우리들의 일상생활과 밀접하게 관련되어 있다. 그러나 인터넷에서의 네트워크 구조는 랜덤 그래프처럼 균일성이 아닌 다양성을 갖고 있다.

○ 최근에 ‘Power Law'라는 법칙이 주목을 받고 있다. 이 Power Law를 만족시킬만한 그래프를 확률적으로 생성한 방법이 최근에 제안되었다. 이와 같은 이론적 연구는 인터넷의 보급과 함께 1990년대 후반부터 시작되었다.

○ 컴퓨터를 이용해 취급되는 문제들은 대부분 그래프 상의 문제로 정식화시킬 수 있다. DNA의 절편(切片) 간 관계 등을 모델화함으로써 그래프로 나타낼 수 있다. 대표적인 그래프의 클래스와 관련된 알고리즘에 관한 연구 개발이 적극 진행되기를 기대한다.