노드, 간선의 개수에 따른 최대 경로의 수

  • chochogogo
    chochogogo

    안녕하세요?
    여쭙고 싶은 것이 있어 글 남기게 되었습니다.

    유향 그래프에서

    총 노드의 수 : N
    총 간선의 수 : E
    그래프에서 출발지와 목적지가 정해져 있는 경우
    출발지로부터 목적지 까지의 경로(정점은 한번만 방문)의 개수를 예상할 수 있는건가요??

    예를들어.. 총 경로의 수는 간선의 수보다 작다 라던가...

    감사합니다.
    수고하십시오!


    9년 전
2개의 댓글이 있습니다.
  • JongMan
    JongMan

    (n-2)! 이하일 거라는 말밖에 할 수 없지 싶네요. 모든 간선 쌍에 대해 양방향으로 간선이 있는 상황을 생각해 보세요.


    9년 전 link
  • chochogogo
    chochogogo

    매번 친절한 답변 감사드립니다~!!
    수고하십시오!!


    9년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.