삼차 그래프

위키백과, 우리 모두의 백과사전.
(큐빅 그래프에서 넘어옴)
이동: 둘러보기, 검색
페테르센 그래프는 큐빅 그래프이다.

삼차 그래프(三次graph, 영어: cubic graph 큐빅 그래프[*])는 모든 꼭짓점이 정확히 세 개의 변에 접한 그래프이다. 즉, 삼차 그래프는 3-정규 그래프이다.

성질[편집]

1880년피터 거스리 테이트는 모든 삼차 그래프는 해밀턴 경로를 가진다는 추측을 내놓았지만, 1946년윌리엄 토머스 텃이 46개 꼭짓점을 가진 반례를 찾았다.

1971년윌리엄 토머스 텃은 모든 이분 삼차 그래프는 해밀턴 회로가 있을 것이라고 추측했지만, 호턴(영어: Horton)이 96개 꼭짓점을 가진 반례를 찾아냈다.

2003년에 Petr Hliněný가 삼차 그래프의 최소 교차점 개수를 찾는 문제는 NP-난해임을 증명하였다.

바깥 고리[편집]