공부

(이산수학, 트리, 노드) 컴공과 형님들 이거 도저히 모르겠습니다... [4]

일병 바깥은한여름 | 21-11-30 18:28:32 | 조회 : 633 | 추천 : -


그래프숲(forest)의 전체 노드의 수가 100개, 트리가 52개로 이루어져 있을때, 이 숲의 에지(edge)는 총 몇개인가? 


이거 그냥 99개같은데 트리갯수가 왜있는지 모르겠어요... 
부탁이니 도와주세요    ㅠㅠㅠ
SNS로 공유하기

  • 이병 imsiro4년 전 | 신고

    음.. 단순히 생각했을 때 노드가 수가 1인 트리 52개를 그리면 총 간선이 0개인데 여기에 하나씩 48번 트리에 노드를 추가한다고 총 간선 수 99가 될까? 내 생각엔 48개인데 참고만 하셈 나도 잘모름 

  • 일병 바깥은한여름4년 전 | 신고

    @imsiro노드-1=엣지 
    이 공식때문에 너무 헷갈려요 ㅠㅠ

  • 이병 imsiro4년 전 | 신고

    @바깥은한여름노드 - 1 = 엣지인 이유는 단일 트리 기준에서 루트 노드 때문인데 포레스트의 트리가 52개라고 가정하면 루트도 52개이고 결국은 100 - 52라고 생각함

  • 일병 바깥은한여름4년 전 | 신고

    @imsiro저도 해보니깐
    노드가 2개, 엣지가 1개인 트리가 48개
    노드가 1개, 엣지가 0개(그냥점하나인 그래프) 트리가 4개 

    - 총 엣지 : 48개

    이 경우의 수 밖에 노드가100개에 트리52개가 될 수 밖에 없던데 

    제가 의문인것이 그냥 노드하나밖에 없는것이 트리가 맞는지 아닌지 궁금해요... 
    진짜 이거말고 다른 경우의수는 없는거같은데

공부
스탭: 재미있는토스,   |  미네랄 창고

인증|정보|칼럼|질문|답변
< 1 2 3 4 5 >