초록 ▼

Ⅳ. 연구개발결과
제곱이 chromatic-choosable이 아닌 그래프가 존재한다는 결과를 바탕으로 그래프를 여러번 거듭제곱하더라도 chromatic-choosable 되지 않는 Cayley graph에 대한 연구결과와 추가적으로 degree condition이 주어지는 경우에 대해서는 보다 더 연구가 필요하지만 제곱하여 chromatic-choosable되지 않는 이분그래프의 존재성에 대한 연구결과를 얻었다. Algebraic structure를 이용한 Kneser graph의 injective coloring을 연구하였

Ⅳ. 연구개발결과
제곱이 chromatic-choosable이 아닌 그래프가 존재한다는 결과를 바탕으로 그래프를 여러번 거듭제곱하더라도 chromatic-choosable 되지 않는 Cayley graph에 대한 연구결과와 추가적으로 degree condition이 주어지는 경우에 대해서는 보다 더 연구가 필요하지만 제곱하여 chromatic-choosable되지 않는 이분그래프의 존재성에 대한 연구결과를 얻었다. Algebraic structure를 이용한 Kneser graph의 injective coloring을 연구하였고 이를 통해 모든 r에 대하여 (수식) 을 보였으며, 위의 두 연구결과에 대한 논문을 투고하였다.곡면위로 embedding된 그래프의 구조 연구에서는 Spindle surface embeddable graphs를 판단하는 알고리듬 구현하였고, Non-planar 그래프에 edge deletion이나 edge contraction을 해서 planar되는 그래프의 구조에 대하여 연구를 진행하여 간단한 이론적 결과를 도출하였다. 곡면의 조합, 위상, 기하적 성질에 대한 연구에서는 궤도공간의 모든 proper face가 acyclic일 때, 토릭오리가미 다양체의 코호몰로지 베티수 계산과 4차원 토릭오리가미다양체의 코호몰로지 환를 계산하였고, 모든 2n(n≥3) 차원에서, 토릭오리가미구조를 가질 수 없는 유사토릭다양체가 존재하는 것을 밝혔다. 이 두 가지 결과에 대한 논문은 투고 완료하였다. 또한 수도그래프 associahedra의 조합적 성질을 관찰하고, complete graph 와 같은 특정한 수도그래프의 induced subgraph로 만들어지는 poset의 shellability에 대하여 증명하여 논문투고 준비 중이다.
뿐만 아니라, 천-가우스-보닛 정리로부터, 4차원 리만 다양체에서 성립하는 곡률항등식을 유도하고 그것의 활용에 대한 직전연도 연구 결과를 이용하여 천-가우스-보닛 정리로부터 6차원 다양체에 대한 곡률항등식을 유도하여 다양체 연구에 활용하였으며, 이를 논문으로 투고 하였다. 추가적으로 Lichnerowicz 가설을 해결하고자 한다. 또한 짝수차원 round sphere들의 Riemann products로 주어진 다양체 위의 직교 almost complex structure의 적분가능성에 관한 연구를 기반으로 닫힌 유향곡면과 4차원 round sphere의 warped product로 주어진 다양체의 almost complex structure는 적분가능하지 않음을 밝혔고 이를 논문으로 투고 했다.
점 (0,0)에서 점(m,r)까지 단위 경로 <0,1> 과 < 0,1> 만으로 가는 두 개의 격자 경로 P와 Q가 `경로 P가 경로 Q보다 더 위로 올라가지 않는다'는 조건을 만족할 때, 경로 P와 Q 사이에 놓일 수 있는 격자 경로들을 기저로 하는 transversal matroid인 lattice path matroid M[P,Q]와 그에 대응하는 matroid base polytope인 lattice path matroid polytope Q(M[P,Q])의 성질을 연구 lattice path matroid polytope Q(M[P,Q])의 모든 faces이 lattice path matroid polytope의 restriction, contraction, and direct sum들로 구성될 수 있음을 보이고, 그 composition에 대응하는 border strips의 cd-indices들과 lattice path matroid polytope Q(M[P,Q])의 cd-index 관계를 연구를 진행하여 관련연구결과를 얻었다.Non-planar graph들 중에서 planar graph에 가까운 Non-planar graphs with a critical edge와 Minimal not nearly planar graph라는 graph class를 정의하고 그래프 G의 구조는 그 두 가지 중 하나를 따름을 밝혔다.
실제 자연 또는 사회 현상을 모델링하기 위한 다양한 돌연변이를 정의하고 돌연변이를 수반한 순서트리의 통계량 연구에서는 돌연변이를 수반한 순서트리의 수와 각 돌연변이에 의해 변형되어 나타나는 새로운 형태의 점의 비율을 계산하여 점근적 행동 예측할 수 있었고, 임의의 자연수 r에 대해 r-ary 수열들을 자연스럽게 연결해주는 조합적 의미를 가지는 무수히 많은 수열을 소개함으로써 Link 정리에 대한 조합적 증명 제시하였다. 이 두가지 연구결과는 논문으로 투고 완료하였다.

목차 Contents

• 표지 ... 1
• 제 출 문 ... 2
• 요 약 문 ... 3
• 목 차 ... 6
• 제 1 장 서론 ... 8
• 1 절 연구개발의 필요성 ... 8
• 1. 연구개발의 개요 ... 8
• 2. 연구개발 사업의 필요성 ... 9
• 2 절 연구개발의 목적 ... 20
• 3 절 연구개발의 범위 ... 20
• 1. 그래프 coloring 문제와 intersection graph에 대한 구조 분석 연구 ... 20
• 2. 곡면위로 embedding된 그래프와 곡면의 조합적 성질 연구 ... 20
• 3. 실생활의 네트워크에서 요구되는 문제로의 응용 ... 21
• 제 2 장 국내외 기술개발 현황 ... 22
• 1 절 국내외 연구동향 ... 22
• 제 3 장 연구개발 수행내용 및 결과 ... 26
• 1 절 연구개발의 추진일정 ... 26
• 1. 개발내용에 따른 추진 일정 ... 26
• 2 절 연구개발의 추진전략 및 추진체계 ... 29
• 3 절 선행연구 ... 32
• 1. 그래프 구조 분석과 그 기반 이론 연구 ... 32
• 2. 실생활의 사회적 네트워크 분석에 대한 선행 연구 ... 34
• 3. 네트워크 최적화 문제인 graph coloring 문제에 대한 연구 ... 35
• 4. 협조적 게임이론에서의 경제적 비용 배분에 대한 연구 ... 42
• 4 절 연구개발의 내용과 결과 ... 48
• 1. 네트워크 최적화 문제인 graph coloring 문제에 대한 연구 ... 48
• 2. 협조적 게임이론에서의 배분 규칙의 공리적 특징화 및 공항활주로 배분 문제 ... 52
• 3. Critical edge를 가지는 graph의 구조 연구 ... 57
• 4. K3,4를 graph minor로 가지는 minimal not nearly planar graph들에 대한 연구 ... 59
• 5. 6차원 곡률의 항등식과 그의 응용에 관한 연구 ... 60
• 6. 닫힌곡면과 4차원 구의 휜 곱(warped product)으로 주어진 다양체 상에 정의된 almost complex structure의 적분가능성에 관한 연구 ... 62
• 7. 토러스 작용을 가지는 위상다양체의 코호몰로지 연구 ... 64
• 8. 실토릭다양체의 유리계수 코호몰로지 연구 ... 66
• 9. 유사토릭다양체의 토릭오리가미구조 연구 ... 68
• 10. 격자경로 매트로이드 다면체의 면 구조 연구 ... 69
• 11. 순서트리에서의 돌연변이 연구와 순서트리를 통한 r-ary 수열 사이의 관계 ... 73
• 제 4장 연구개발목표 달성도 및 대외기여도 ... 80
• 제 5 장 연구개발결과의 활용계획 및 기대성과 ... 81
• 1절 활용계획 ... 81
• 2절 기대효과 ... 82
• 제 6 장 참고문헌 ... 83
• 끝페이지 ... 88