2010년07월11일 29번
[임의 과목 구분(20문항)] 28개의 노드를 모두 망형으로 구성할 경우 최소로 필요한 회선수는?
- ① 378
- ② 348
- ③ 278
- ④ 148
(정답률: 74%)
문제 해설
노드가 28개인 경우, 모두 망형으로 구성할 경우 각 노드는 다른 2개의 노드와 연결되어야 합니다. 따라서 총 필요한 회선 수는 28 x 2 = 56개가 됩니다.
하지만 망형 구성에서는 각 노드가 다른 모든 노드와 직접 연결되어 있지 않기 때문에, 각 노드에서 다른 모든 노드로의 경로를 구성하기 위해 추가적인 회선이 필요합니다.
이를 계산하기 위해, 노드를 중심으로 한 개의 트리를 구성하고, 이 트리에서 각 노드로의 경로를 계산합니다. 이때, 각 노드에서 다른 모든 노드로의 경로를 구성하기 위해 필요한 회선 수는 해당 노드의 차수(연결된 노드의 수)와 같습니다.
따라서, 각 노드의 차수를 합산한 값이 추가적으로 필요한 회선 수가 됩니다. 모든 노드가 차수 2인 망형 구성에서는 각 노드의 차수 합이 56이므로, 추가적으로 필요한 회선 수는 56입니다.
하지만 실제로는 모든 노드가 차수 2인 구성이 어렵기 때문에, 일부 노드의 차수가 3 이상이 됩니다. 이 경우, 해당 노드에서 다른 모든 노드로의 경로를 구성하기 위해 추가적인 회선이 필요하므로, 차수가 3 이상인 노드의 수가 적을수록 총 필요한 회선 수는 감소합니다.
따라서, 28개의 노드를 모두 망형으로 구성할 경우 최소로 필요한 회선 수는 378이 됩니다.
하지만 망형 구성에서는 각 노드가 다른 모든 노드와 직접 연결되어 있지 않기 때문에, 각 노드에서 다른 모든 노드로의 경로를 구성하기 위해 추가적인 회선이 필요합니다.
이를 계산하기 위해, 노드를 중심으로 한 개의 트리를 구성하고, 이 트리에서 각 노드로의 경로를 계산합니다. 이때, 각 노드에서 다른 모든 노드로의 경로를 구성하기 위해 필요한 회선 수는 해당 노드의 차수(연결된 노드의 수)와 같습니다.
따라서, 각 노드의 차수를 합산한 값이 추가적으로 필요한 회선 수가 됩니다. 모든 노드가 차수 2인 망형 구성에서는 각 노드의 차수 합이 56이므로, 추가적으로 필요한 회선 수는 56입니다.
하지만 실제로는 모든 노드가 차수 2인 구성이 어렵기 때문에, 일부 노드의 차수가 3 이상이 됩니다. 이 경우, 해당 노드에서 다른 모든 노드로의 경로를 구성하기 위해 추가적인 회선이 필요하므로, 차수가 3 이상인 노드의 수가 적을수록 총 필요한 회선 수는 감소합니다.
따라서, 28개의 노드를 모두 망형으로 구성할 경우 최소로 필요한 회선 수는 378이 됩니다.
연도별
- 2022년10월08일
- 2022년03월12일
- 2021년10월02일
- 2021년03월13일
- 2020년09월26일
- 2020년05월24일
- 2019년10월12일
- 2019년03월09일
- 2018년10월06일
- 2018년03월10일
- 2017년10월14일
- 2017년03월04일
- 2016년10월08일
- 2016년03월05일
- 2015년10월04일
- 2015년03월07일
- 2014년10월04일
- 2014년03월09일
- 2013년10월12일
- 2013년03월17일
- 2012년10월06일
- 2012년03월11일
- 2011년07월31일
- 2011년04월17일
- 2010년07월11일
- 2010년03월28일
- 2009년08월27일
- 2009년03월29일
- 2008년07월13일
- 2007년07월15일
- 2006년07월16일
- 2005년07월17일
- 2004년07월18일
- 2003년07월02일
- 2002년07월21일