[알고리즘] 그래프에서 패스(Path) 의 정확한 정의..
글쓴이: gyxor / 작성시간: 금, 2005/07/29 - 5:28오후
형식언어와 오토마타라는 책에서는..
일반적으로 간선들의 순서열을 보행(walk)라고 하며
보행중 간선 중복이 없는 경우를
:경로(path)
경로중에서 어느 정점도 중복하여 지나지 않는 경우
:단순경로(simple path)
경로중에서 처음 시작 정점과 마지막 정점이 같은 경우
:사이클(cycle)
사이클중에서 정점이 중복되지 않는 경우
:단순 사이클(simple cycle)
이렇게 나와있습니다.
그런데
이산수학,자료구조,알고리즘 각각의 총 3권의 책에
나와있는 path의 정의에서는 하나같이..
" 간선이 중복 되지 않아야 한다 "는 이야기가 없습니다.
즉, walk의 정의가 따로 없게 되는것입니다.
물론 매우 사소한 부분이지만..
정의....라는 측면에서 보면..
아직도 개념이 제각각인것인지....
어느게 맞는것인지 모르겠습니다.
설명부탁드립니다.
Forums:
개념이 제각각인게 맞습니다. 제가 전에 정리한 세가지(-_-;)정의는 다
개념이 제각각인게 맞습니다. 제가 전에 정리한 세가지(-_-;)정의는 다음과 같습니다.
1) WALK : sequence of vertex which has incident edges.
a) TRAIL : a WALK whose edge is not repeated
PATH : a TRAIL whose vertex is not repeated
b) CIRCUIT : a WALK which strat from and end at the same vertex and whose edge is not repeated.
CYCLE : a CIRCUIT whose vertex is not repeated
2) WALK : same as above
a) PATH : a WALK whose edge is not repeated
simple PATH : a PATH whose vertex is not repeated
b) CYCLE : a WALK which start from and end at the same vertex and whose edge is not repeated
simple CYCLE : a CYCLE whose vertex is not repeated
3)
a) PATH : sequence of edges
simple PATH : a PATH whose edge is not repeated
elementary PATH : a simple PATH whose vertex is not repeated
b) CYCLE : sequence of edges which start from and end at the same vertex
simple CYCLE : a CYCLE whose edge is not repeated
elementary CYCLE : a simple CYCLE whose vertex is not repeated
--
Passion is like genius; a miracle.
음 어렵네요;;
주위에 있는 책이 알고리즘책과 자료구조책 뿐이군요.
자료구조개론 이란 책에서는 path 가 중복되지 않는다는 문장은 없지만
라고 기술된것을 보면 간선은 중복되는 것이 아니라는 의미를 가지고 있지 않을까 생각됩니다.
중복이 될수있다면 길이자체를 저렇게 수식으로 내보일수 없을것 같거든요.
컴퓨터알고리즘이란 책에서는
라고 distinct 라는 표현이 사용되어 있네요.
pool007 님이 정리해주신 내용에서도 1, 2번에선
path 는 edge 가 not repeat 인데..
에서는 좀 혼란스럽긴 하네요
만일 simple PATH + elementary PATH = PATH 라는 개념이라면
PATH 에서는 간선이 중복되지 않는다.. 라는 의미를 가지고 있는것이라 볼 수 있지 않을까요?
-----
이글을 읽는 모든 이에게 평화가 함께 하기를... ^^;
답변감사합니다..
그렇게 3가지 종류의 정의가 있는지 미처 몰랐습니다...
나름대로...정의군요..^^;
답변감사합니다.
이미 좋은 댓글들이 많이 달려서 원하시던 답변을 벌써 얻으셨을테지만 참고
이미 좋은 댓글들이 많이 달려서 원하시던 답변을 벌써 얻으셨을테지만 참고삼아 사족을 하나 달자면, 어디에서나 똑같이 정의되어있으리라 기대되는 매우 일반적인 용어들 중에도 이 경우처럼 문헌마다 정의가 조금씩 엇나가는 일이 종종 있습니다. 물론 새로운 글을 저술할 때에는 가능한 한 (그런게 확정되어 있을 경우) 기존의 ‘관례적 정의’에 맞춰서 똑같이 쓰는게 바람직하겠지만, 같은 용어를 조금 다르게 정의했다고 해서 꼭 잘못된 것이라고 할 수도 없습니다. 정의란 말 그대로 ‘정의’이고, 결국 (한 문헌 내에서 그 정의들끼리 논리적으로 충돌하지만 않는다면) 정의하는 사람 마음대로니까요.
그래서, (특히 이공계 문헌들일수록 더욱) ‘지금 읽고있는 문헌에서 이 용어를 어떻게 정의했었는가’에 철저하게 맞춰서 읽는 것이 가장 중요합니다. 좋은 문헌이라면
- 딱 한가지로 고정된 관례적 정의가 널리 통용되는 용어들을 (그 의미대로) 주로 사용하거나,
- 만일 관례적 정의가 확정되지 못한 (문헌마다 조금씩 다른 경우가 많은) 용어를 사용할 때에는 초반에 이 용어를 정확하게 정의해두며
- 관례적 정의와 문헌 내의 로컬 정의를을 모두 아울러도 논리적인 모순이 없도록
잘 정의되어있을테니까요. 만일 용어의 정의가 정확히 무엇이냐에 따라 글의 의미가 완전히 달라질 정도로 모호한 용어를 사용하면서도 그 용어를 정확히 정의해두지 않고 진행하는 글이 있다면, 그다지 좋은 글은 아닐겁니다.여담이지만, 개중에는 스스로 정의해둔 용어마저 나중에 함부로 막 쓰는 문헌들도 있는데, 이런 경우에도 솔직히 조금 짜증이 나죠. 예를 들어:
이렇게 정의해놓고는 한참 나중에 본문에 이런게 나옵니다:
:evil: 물론 “모든 simple T x와 y에 대해서…”를 잘못 썼겠거니 생각해줄 수도 있지만, 이런 짐작을 동원해 읽어야한다는 사실은 (아무리 이 경우처럼 개연성이 충분해도) 분명히 찝찝한 일입니다. 때로는 매우 위험하기도 하고, 결국 골탕을 먹는 경우도 있습니다. 저자도 인간이니 한 두 번 정도의 사소한 실수야 그렇다고 쳐도, 이런 일이 수없이 반복되거나 이로인해 개념 자체를 오해하면서 골탕을 먹고나면 책을 집어던지게되더군요. :?
아무튼, 항상 그 책에 나오는 정의에 충실히 따르시는게 중요하며, (좋은 책이라면) 이렇게만 읽으시면 다른 책에 나오는 정의와 조금 다르더라도 아무 문제 없을겁니다. :)
[/]--
자본주의, 자유민주주의 사회에서는 결국 자유마저 돈으로 사야하나보다.
사줄테니 제발 팔기나 해다오. 아직 내가 "사겠다"고 말하는 동안에 말이다!
오 그러면..for each v0, v1, v2, v3v0
오 그러면..
for each v0, v1, v2, v3
v0 → v1 → v2 → v3 ?
v0 → v1 → v1 → v2 → v3
v0 → v1 → v1 → v1 → v2 → v3
v0 → v1 → v1 → v1 → v1 → v2 → v3
이것들이 다 walk로는 구분되는데,
trail 이나 path로는 구분이 안된다는 말인가요?
알쏭달쏭..
헐 저도 책읽다가
헐 저도 책읽다가 짱나서 검색하고 있었는데용 ^^
책보다 보면 개념이 살짝살짝 제 각각인경우가 많은것 같습니다.
동감동감
헐 저도 책읽다가 짱나서 검색하고 있었는데용 ^^
책보다 보면 개념이 살짝살짝 제 각각인경우가 많은것 같습니다.
동감동감
헐 저도 책읽다가 짱나서 검색하고 있었는데용 ^^
책보다 보면 개념이 살짝살짝 제 각각인경우가 많은것 같습니다.
댓글 달기