최소 단어 이상 선택하여야 합니다.
최대 10 단어까지만 선택 가능합니다.
다음과 같은 기능을 한번의 로그인으로 사용 할 수 있습니다.
NTIS 바로가기주관연구기관 | 전남대학교 Chonnam National University |
---|---|
연구책임자 | 임형석 |
보고서유형 | 최종보고서 |
발행국가 | 대한민국 |
언어 | 한국어 |
발행년월 | 2018-11 |
과제시작연도 | 2017 |
주관부처 | 교육부 Ministry of Education |
등록번호 | TRKO201900025313 |
과제고유번호 | 1345269069 |
사업명 | 개인기초연구(교육부) |
DB 구축일자 | 2020-08-29 |
키워드 | 밀집된 그래프.서로소 경로커버.쌍형 경로커버.비쌍형 경로커버.해밀톤 경로. |
연구개요
경로커버 문제는 널리 알려진 해밀톤 경로/사이클 문제와 깊은 관련이 있다. 실제로 한 정점쌍을 연결하는 해밀톤 경로는 일대일, 일대다, 다대다 1-경로커버에 해당한다. 그리고 정점수가 3이상인 그래프 G가 일대다 2-커버가능일 필요충분조건은 G가 해밀톤 연결된(Hamilton-connected) 그래프라는 것이다. 본 연구에서는 위와 같은 해밀톤 성질과 경로커버와의 연관 관계를 바탕으로 하여 밀집 그래프에 대해 비쌍형 다대다, 쌍형 다대다, 그리고 일대다 경로커버가 존재하기 위한 충분조건을 개발하였다.
연
※ AI-Helper는 부적절한 답변을 할 수 있습니다.