원격평생교육원 이산수학 토론 과제

소개글

요약(대표) 키워드 : 이산수학 토론 과제
토론주제 : “G는 그래프이고 v와 w는 서로 다른 정점이라 하자. v에서 w로의 경로가 존재하면 v에서 w로 단순경로가 존재한다.” 라는 주장이 참인지 거짓인지를 논하시오. 만약 거짓이라면 반례를 들고, 참이면 그 이유를 말하시오.

과목 전체점수 91.7점(A+)를 받은 자료입니다.

목차

없음

본문내용

G는 그래프이고 v와 w는 서로 다른 정점이라고 한다면 v와 w를의 에지를 한번씩 지나게 된다.

해당 경로에서 다시 지나는 점을 r 이라고 하고 v와 w를 잇는 r를 거쳐가는 경로가 항상 존재하기 때문에 단순경로가 항상 존재하므로 단순경로가 존재할 수 밖에 없다.

따라서 v에서 w로의 경로가 존재하면 v에서 w로 단순경로가 존재한다는 것은 참이라는 결론을 얻을 수 있다.

또한 단순경로란 경로가 같은 에지를 두 번 이상 포함하지 않는 경로를 말하며, 일반적으로 경로라고 표현할 단순 경로를 의미한다. 경로는 정점의 연속(v1, v2, ..., vn+1) 또는 에지의 연속 (e1, e2, e3..., en)으로 나타내기도 한다.

예를 들어 G는 미국의 주(州)로 구성된 정점의 집합인 그래프라 정의하자. 주 v와 주w가 맞닿으면 주v와 주w 사이에 간선을 긋는다. 즉 네바다주와 유타주 그리고 몬타나주와 북다코타주 사이에 간선이 존재한다. 오하이오와 뉴욕 사이에는 간선이 존재하지 않고, 캔자스와 알라바마 사이에도 존재하지 않는다.

참고 자료

없음