<p style="text-align: left;"><span></span></p><div class="figure-img" data-ke-type="image" data-ke-style="alignCenter" data-ke-mobilestyle="widthOrigin"><img src="https://t1.daumcdn.net/cafeattach/1Lj3M/e3fcff1db3bdd59544d10914c9376d75e7fb2e9a" class="txc-image" data-img-src="https://t1.daumcdn.net/cafeattach/1Lj3M/e3fcff1db3bdd59544d10914c9376d75e7fb2e9a" data-orgin-width="480" data-origin-height="354"></div><p style="text-align: left;">케일리의 수형도 공식에 따르면 n개의 꼭짓점을 가진 수형도의 개수는 n의 n-2제곱인데<br>이 문제에서 풀이가 10의 8제곱이 되지 않는 이유가 궁금합니다!<br><br><br><br>문제 3.6.1<br></p><div class="figure-img" data-ke-type="image" data-ke-style="alignCenter" data-ke-mobilestyle="widthOrigin"><img src="https://t1.daumcdn.net/cafeattach/1Lj3M/d31114e5085d3ae3437b8efbdfae0c68a0be3ca4" class="txc-image" data-img-src="https://t1.daumcdn.net/cafeattach/1Lj3M/d31114e5085d3ae3437b8efbdfae0c68a0be3ca4" data-orgin-width="480" data-origin-height="296"><div class="figcaption"></div></div><p style="text-align: left;">문제 3.6.1 해설에서는 3개 라고 나와있는데<br>제가 해설지 위에 점을 찍고 선을 이은 것 처럼 하면 B에 하나 E에 하나. 총 두개 로도 해결 가능하다고 생각했습니다<br>(B에 설치하면 40km이내의 지역에 A,C,D,F가 포함됩니다)<br>혹시 이런 방법에 문제점이 있는지 설명해주시면 감사하겠습니다!<br><br><br><br></p><div class="figure-img" data-ke-type="image" data-ke-style="alignCenter" data-ke-mobilestyle="widthOrigin"><img src="https://t1.daumcdn.net/cafeattach/1Lj3M/d2651c05e174298de5037338b8995d6b912e56ab" class="txc-image" data-img-src="https://t1.daumcdn.net/cafeattach/1Lj3M/d2651c05e174298de5037338b8995d6b912e56ab" data-orgin-width="480" data-origin-height="140"></div><div class="figure-img" data-ke-type="image" data-ke-style="alignCenter" data-ke-mobilestyle="widthOrigin"><img src="https://t1.daumcdn.net/cafeattach/1Lj3M/ee47fcbf8f7360b007aabf13a24e49e15c339f54" class="txc-image" data-img-src="https://t1.daumcdn.net/cafeattach/1Lj3M/ee47fcbf8f7360b007aabf13a24e49e15c339f54" data-orgin-width="480" data-origin-height="562"></div><p style="text-align: left;">문제3.6.7의 경우 제가 첨부한 풀이의 방법으로 풀면 답지와 다르던데, 어느 부분에서 오류가 생기는 것인지 알려주시면 감사하겠습니다!</p>
<!-- -->
첫댓글1. 생성수형도의 정의를 보면 부분그래프라는 조건이 필요합니다. 모든 꼭짓점이 인접한 완전그래프의 생성수형도의 개수는 케일리의 수형도 공식이 바로 적용이 가능하지만, 주어진 그래프는 다른 상황입니다. 2. 문제를 조금 잘못 이해하신 듯 합니다. A, B, F의 거리가 모두 각각 40Km 미만이고 꼭짓점 A, B, F가 모두 인접하는 K_3를 부분그래프로 갖는 상황에서 최소 3개의 주파수가 필요합니다. 3. a와 b가 같은 색인 경우, a를 k-1가지 경우 중 하나의 색을 선택했다면 b는 a와 같은 색이므로 1가지가 됩니다.
첫댓글 1. 생성수형도의 정의를 보면 부분그래프라는 조건이 필요합니다. 모든 꼭짓점이 인접한 완전그래프의 생성수형도의 개수는 케일리의 수형도 공식이 바로 적용이 가능하지만, 주어진 그래프는 다른 상황입니다.
2. 문제를 조금 잘못 이해하신 듯 합니다. A, B, F의 거리가 모두 각각 40Km 미만이고 꼭짓점 A, B, F가 모두 인접하는 K_3를 부분그래프로 갖는 상황에서 최소 3개의 주파수가 필요합니다.
3. a와 b가 같은 색인 경우, a를 k-1가지 경우 중 하나의 색을 선택했다면 b는 a와 같은 색이므로 1가지가 됩니다.