주어진 여러 토폴로지 순서로 DAG 구성

Question

주어진 토폴로지 순서(예:그래프 $G$ 생성된 항목에는 토폴로지 순서로 지정된 모든 순서가 있어야 합니다.단순화를 위해 정점은 첫 번째로 레이블이 지정됩니다. $n$ 자연수.(한 번 생성된 그래프는 $G$ 주어진 것 외에 더 많은 위상 순서가 있을 수 있습니다.)
다음 제약 조건을 충족해야 합니다.

1. 모든 노드의 최대 아웃도는 1이어야 합니다.
2. 차수가 0인 노드의 수는 최소이어야 합니다.

여러 가지 솔루션이 있을 수 있으며 그중 어느 것이든 작동합니다.

내가 시도한 것.(접근법 1 답변에 제공된 한 가지 예가 실패했기 때문에 이는 잘못된 것입니다.두 번째 접근 방식으로 스크롤하세요. 여전히 실수를 찾을 수 없습니다.)

접근법 1
주어진 모든 순서에서 먼저 모든 노드에서 다음 노드까지 방향성 간선을 생성하여 방향성 그래프를 만듭니다.이는 주문이 다음과 같은 경우를 의미합니다.
$$ 1, 3, 2, 5, 4, 6 $$ $$ 3, 1, 5, 2, 4, 6 $$ $$ 1, 5, 3, 2, 4, 6 $$

나는 방향성 간선을 갖는 방향성 그래프를 생성할 것입니다. $1$ 에게 $3, 3$ 에게 $2, 2$ 에게 $5$ 기타 등등.

이렇게 하면 차수가 0인 노드 수가 최소로 유지됩니다.이제 모든 사이클을 제거하고 모든 순서가 유효한지 확인한 다음 마지막으로 모든 노드에 있는 추가 가장자리를 모두 제거하겠습니다.그렇게 하는 동안 동일한 노드에서 가장자리가 나오는 노드가 두 개 있는 경우 차수가 더 높은 노드에서 가장자리를 제거하여 조건 2가 충족되는지 확인합니다.그러면 구성된 그래프는 다음과 같아야 합니다.

이 DAG는 두 가지 제약 조건을 모두 따르며 IMO의 최소 내차 노드 수는 0이지만 입증되지는 않았습니다.

나는 접근 방식을 코딩했고 내가 제공한 사용 사례에 대해 예상된 결과를 제공했지만 그것이 잘못되었다는 것을 알고 있습니다.내가 여기서 무엇을 놓치고 있는 걸까요?위의 접근 방식이 실패한 대체 사용 사례를 제공할 수 있는 사람이 있나요?

접근법 2
방향성 그래프를 만듭니다 $G$ 가장자리를 생성하여 $a_i $ 에게 $a_j$ 모든 $j > i$ 주어진 모든 명령에서.따라서 주문의 경우:
$$ 1, 2, 3, 4, 5$$ $$ 2, 4, 1, 5, 3$$

다음 그래프를 작성하겠습니다.
그 후의 첫 번째 단계는 모든 주문을 검증하는 것입니다.이 단계 자체에서 사이클이 제거되므로 사이클을 별도로 제거할 필요는 없습니다.
어떤 주문이든$$ a_1, a_2, a_3, a_4, ...a_n $$가장자리가 있는지 확인하겠습니다. $a_j$ 에게 $a_i$ 어디 $j > i$, 해당 가장자리를 제거하겠습니다.
그렇게 하면 다음과 같은 그래프가 나타납니다.
마지막 단계는 모든 노드의 최대 아웃도가 가능하므로 모든 노드에서 추가 가장자리를 제거하는 것입니다. $1$ 최대.차수를 갖는 노드 수가 되도록 나가는 가장자리를 제거하겠습니다. $0$ 최소입니다.먼저 각 노드의 차수를 계산합니다.그런 다음 나가는 가장자리가 2개 이상인 각 노드에 대해 최소 각도를 가진 가장자리를 제외한 모든 가장자리를 제거합니다.

최종 그래프 $G$ 다음과 같이 보일 것입니다:

이 그래프는 두 가지 제약 조건을 모두 충족합니다.하지만 나는 이 접근 방식이 잘못되었다는 것을 알고 있습니다!이것이 왜 잘못된지 찾는 데 도움을 줄 수 있는 사람이 있습니까?

Answer 1

접근법 1

예를 들어 다음 두 가지 주문을 고려해보세요.1, 2, 3, 4, 5 및 2, 4, 1, 5, 3.

귀하의 접근 방식에 따르면 1->2->3->4->1 주기가 발생합니다.그런 다음 3->4와 4->1을 제거하고 그래프를 얻습니다.

     ______
    /      \
1->2->4->5->3
 \______/

이제 5->3과 1->2는 각각 첫 번째와 두 번째 순서를 위반하므로 이를 제거하고 다음을 얻습니다.

     ______
    /      \
1  2->4->5  3
 \______/

이제 노드 2에는 2개의 나가는 간선이 있습니다.둘 중 하나를 제거하면 3개의 노드(1, 2, 3 또는 1, 2, 4)의 차수가 0인 최종 그래프가 생성됩니다.

그러나 그래프가 존재합니다.

1->3 2->4->5

두 차수가 모두 충족되지만 2개의 노드만 차수 0을 갖습니다.

따라서 접근 방식 1은 올바르지 않습니다.

접근법 2

최적의 솔루션을 고려하십시오.이 최적 솔루션의 모든 모서리는 다음과 같은 형태여야 합니다. $(a_i,a_j)$ 어디 $i<j$ 각 순서대로.이는 최적 솔루션의 모든 간선이 중간 그래프에 포함됨을 의미합니다.따라서 차수가 0인 노드 수가 최소가 되도록 나가는 가장자리를 제거하면 올바른 최적 솔루션을 얻을 수 있습니다.

그러나 차수가 0인 노드 수를 최소로 만들려는 접근 방식은 올바르지 않습니다.

예를 들어 다음 세 가지 주문을 고려해보세요.begin {align} 1, 2, 3, 4, 5, 6, 7, 8 5, 1, 6, 3, 8, 2, 4, 7 2, 7, 3, 8, 1, 4 , 5, 6 end {align}

먼저 다음과 같은 중간 그래프를 얻을 수 있습니다.

    _____
   / ____\__
  / / ____\_\__
 / / /     \ \ \
1 2 3->4 5->6 7 8
 \ \__/
  \__/

접근 방식을 적용하면 1->4, 2->4 및 3->4(또는 3->8)가 제거되고 차수가 0인 5개의 노드가 있습니다.1, 2, 3, 4(또는 8), 5.그러나 최적의 솔루션은 다음과 같습니다.

     _______
    / ____ _\__
   / /       \ \
1 2 3 4 5->6 7 8
 \___/

여기서 4개의 노드만 차수 0을 갖습니다.1, 2, 3, 5.