1
현재 공간적으로 임베디드 된 네트워크를 조사 중이며 다음에 대한 답변을 찾는 데 문제가 있습니다. N 노드가있는 네트워크가 있다고 가정 해 보겠습니다. 이 노드들 각각은 공간에 위치하며, 4 개의 포트로 연결될 수 있습니다 (각 노드의 최대 차수는 4입니다). 각 노드는 4 개의 가장 가까운 이웃과 연결을 시도합니다. (링크 양방향)그래프 : 최대 차수가 4 인 노드는 각 노드가 가장 가까운 네 개의 노드에 연결을 시도합니다 - 손실 된 연결 수는 얼마입니까?
다음 문제가 발생합니다 연결이 추가됩니다
으로, 특정 노드가 최대 수준에 도달합니다. 다른 노드는 가장 가까운 이웃 노드 중 하나로서이 노드를 가질 수 있지만 다른 노드가 더 이상 연결을 허용 할 수 없기 때문에이 노드를 연결할 수 없습니다. 이러한 '시도'는 빨간색으로 강조 표시됩니다.
이 문제를 일반화하고 그래프 내에서 가능한 연결 수를 결정할 방법이 있습니까? 연결이 이루어지는 순서는 결과에 어떤 영향을 줍니까?
흥미롭고 어려운 문제 일 수 있습니다. 그러나 당신이 기대하는 "친절한"대답이 무엇인지는 완전히 명확하지 않습니다. 첫 번째 짧은 (!) 한눈에봤을 때 * 연결 수는 고정되어 있다고 말할 수 있습니다. 추가 할 수있는 각 빨간색 가장자리에 대해 정확히 하나의 다른 가장자리를 제거해야합니다. 삽입 순서는 관련이 없어야합니다. 그러면 그래프의 총 모서리 수는 'sumOfAllDegrees/2'가됩니다. 여기에 4 정규 그래프 (http://en.wikipedia.org/wiki/Regular_graph 참조)에 대한 최대 것입니다. 하지만 당신의 고려 사항은 거리에 따라 약간의 "가중치"가 있다고 가정합니다 ...? – Marco13