주메뉴바로가기 본문바로가기
닫기

[지식]P일까, NP일까? 그래프 동형 문제

꼭짓점과 꼭짓점을 잇는 변으로 이뤄진 대상을 ‘그래프’라고 합니다. 그래프는 ({1,2,3}, {1-2,2-3, 3-1})처럼 꼭짓점 집합과 변 집합의 순서쌍으로 나타냅니다. 매우 추상적이지요. 지하철 노선도처럼 꼭짓점은 점, 두 꼭짓점을 잇는 변은 선으로 나타낸 그림이라고 생각하면 간단합니다.위의 두 그래프는 전혀 달라 보이지만 꼭짓...(계속)
글 : 엄상일
진행 : 조가현 수학동아 gahyun@donga.com
일러스트 : 뻐가콜라
이미지 출처 : [일러스트] 뻐가콜라

수학동아 2016년 01호
이전
다음
1
수학동아 2016년 01호 다른추천기사
이 기사를 읽은 분이 본
다른 인기기사는?
리만가설
[지식]2억 년 뒤 세계지도는? 대륙 퍼즐 맞추기
[지식]김재경 KAIST 수리과학과 교수
[지식] 물감의 혼돈, 잭슨 폴락의 그림엔 프랙탈이 있다!
[수학동아클리닉](초등)각기둥과 각뿔 요리하며입체도형탐구하기 (중등)작도로 즐기는 하트 모양디자인
  • 동아사이언스 바로가기
  • 과학동아 사이언스보드 바로가기
  • 어린이과학동아 어린이수학동아 바로가기
  • 폴리매스 바로가기
  • DS스토어 바로가기
  • 디라이브러리 바로가기
  • 과학동아천문대 바로가기
  • ㈜동아사이언스 | 등록번호 : 서울 아04396 | 등록일자 : 2017년 3월 2일 | 제호 : 동아사이언스 | 발행인 : 장경애 | 편집인 : 김민수
  • ㈜동아사이언스 디라이브러리 | 대표 : 장경애 | 개인정보관리책임자 : 최수정(privacy@dongascience.com) | 청소년보호책임자 : 신한식
  • 서울시 용산구 청파로 109, 7층 (04370) ｜ 문의 : 02-6749-2000 ｜팩스 : 02-3148-0789 ｜사업자등록번호 : 101-81-62201 (사업자정보확인)
  • 통신판매업신고번호 : 제2013-서울용산-01101호 ｜온라인 결제를 위한 PG사의 구매안전서비스(가입사실 확인)
  • Copyright © Dongascience. All right reserved.

  • 폴리매스 문제는 2019년도 정부의 재원으로 한국과학창의재단의 지원을 받아 수행된 성과물입니다.

  • ☎문의 02-6749-3911