초록 ▼

그래프는 네트워크와 같은 이진관계로 이루어진 구조를 분석할 수 있게 해주는 수학적인 구조입니다. 그래서 어떤 조건을 만족하는 그래프의 성질을 밝히는 일은 매우 중요합니다. 특히 그래프 내의 특정 부분구조가 존재하는지, 그리고 그 부분구조와 그래프의 다른 성질과 관계가 있는지, 특정 부분구조를 가지지 않는 극단적인 그래프의 구조가 어떤지를 밝히는 것은 매우 흥미롭고 중요한 문제입니다. 이 연구에서 우리는 위의 연구방향 중에서도 특정 그래프를 포함하지 않는 그래프의 최대 선(edge)개수가 몇 개인지, 즉, 그 그래프의 극단값이 얼마인

그래프는 네트워크와 같은 이진관계로 이루어진 구조를 분석할 수 있게 해주는 수학적인 구조입니다. 그래서 어떤 조건을 만족하는 그래프의 성질을 밝히는 일은 매우 중요합니다. 특히 그래프 내의 특정 부분구조가 존재하는지, 그리고 그 부분구조와 그래프의 다른 성질과 관계가 있는지, 특정 부분구조를 가지지 않는 극단적인 그래프의 구조가 어떤지를 밝히는 것은 매우 흥미롭고 중요한 문제입니다. 이 연구에서 우리는 위의 연구방향 중에서도 특정 그래프를 포함하지 않는 그래프의 최대 선(edge)개수가 몇 개인지, 즉, 그 그래프의 극단값이 얼마인지 알아내는데 중심을 두고 있습니다.

또한 그래프의 분해 문제는 극단적 그래프이론에서 중요하게 생각하는 문제 중 하나입니다. 그래프에서 하나의 부분구조를 찾아내는 문제도 어려운 문제이지만, 그래프 분해 문제는 그래프 안에서 최대한 많은 부분구조를 서로 겹치지 않게 찾아내야 해서 더 어려워지기 때문입니다. 최근 여러 극단적 그래프이론의 결과를 Ramsey-Turan type 문제의 관점에서 재해석하는 연구가 활발히 진행되고 있습니다. 하지만 그래프 분해 문제를 Ramsey-Turan Type으로 시도한 결과는 아직 없었습니다. 최근 Hong Liu교수와 김연진 박사와 함께 큰 bi-independent set이 없는 정규 그래프를 주어진 차수가 제한된 Tree로 거의 최적의 방법으로 분해할 수 있는 정리를 증명했습니다. 이는 그래프 분해 문제를 Ramsey-Turan type으로 접근한 최초의 논문으로, 앞으로 많은 후행 연구들을 촉발시킬 것으로 기대됩니다.

(출처 : 초록 3p)

목차 Contents

• 표지 ... 1
• 제 출 문 ... 2
• 보고서 초록 ... 3
• 요 약 문 ... 4
• C O N T E N T S ... 6
• 목차 ... 7
• 제 1 장 연구개발과제의 개요 ... 8
• 제 2 장 국내외 기술개발 현황 ... 9
• 제 3 장 연구개발수행 내용 및 결과 ... 10
• 제 4 장 목표달성도 및 관련분야에의 기여도 ... 11
• 제 5 장 연구개발결과의 활용계획 ... 12
• 제 6 장 연구개발과정에서 수집한 해외과학기술정보 ... 13
• 제 7 장 참고문헌 ... 14
• 끝페이지 ... 15