이 유형의 지정 비순환 그래프의 이름은 무엇입니까?

어쩌면 그것은 DAG도 아니지만, 이름을 지어서 내가 어떤 제목을 부여했는지 알 수 없었습니다 ...이 유형의 지정 비순환 그래프의 이름은 무엇입니까?

모든 노드가 0 개 또는 1 개의 경로 만 가질 수있는 데이터 구조의 이름은 무엇입니까? ? 엄밀히 말하면,이 나무입니까?

감사합니다.

2009-06-03 Andrew Bullock

감독적인 나무입니다. 보통 나무는 그와 같이 방향이 없습니다.

제한 조건은 정확하게 나무가 정의 된 방법이 아닙니다 (나무의 정의는 두 개의 꼭지점이 둘 이상의 경로로 연결되지 않는다는 것입니다). 그러나 그래프는 유효한 지시 트리가되도록 제한합니다. (나는 당신이 관심있는 말을 할 수없는 일정한 방향성을 요구하는 '지시 된 나무'의 이상한 사용법을 사용하고 싶지 않다.)

출처

2009-06-03 15:59:58 chaos

설명해 주셔서 감사합니다 –

Bill마다 도마뱀, 그것은 acyclicity 제약 조건을 필요로합니다. 나는 그것이 실제로 당신의 최종 사양에 있지는 않지만 모든 언급에서 그것을 추측하고있었습니다. – chaos

그래, 나는 제목에서 유추 한 비순환을 의미했지만 더 구체적 이어야만했다.) –

다른 제약 조건이 있습니까? 당신이 주어진 것에서 만 이 아닌 그래프를 만들 수 있습니다. 트리입니다.

A -> B ->를

당신이 그래프가 비순환 제약 조건을 추가하면, 그때는 나무 일 것이다.

출처

2009-06-03 16:16:40

안녕하세요? 그는 A -> B -> {C, D, E} 할 수 있습니다 .... 나는 뭔가를 놓쳐 버린 것 같아요. – chaos

오, 알았어요. 나는 당신이 아웃 링크에 대한 제약의 의미를 읽는 중이다. 하지만 OP의 질문에서 읽을 수있는 유일한 제약은 아웃 링크가 아니기 때문에 불가능한 것처럼 보입니다. 그러면 아웃 바운드가 생겨 그래프가 전혀 나타나지 않게 될 것입니다. – chaos

@ chaos : 내 대답을 편집하기 전에 귀하의 의견을 쓰기 시작했다고 생각합니다. 나는 편집하기 전에 뭔가를 놓쳤다. –

이 유형의 지정 비순환 그래프의 이름은 무엇입니까?

답변

관련 문제