노드가 n 개인 유 방향 그래프에서 최대 간선 수는 얼마입니까?
노드가 n 개인 유 방향 그래프에서 최대 간선 수는 얼마입니까? 상한선이 있습니까?
당신이있는 경우 N노드가 있습니다 N - 1그것에서 이어질 수있는 것보다 가장자리를 지시 (모든 다른 노드로 이동). 따라서 최대 모서리 수는 N * (N - 1)입니다.
무 방향 그래프 (다중 그래프 제외)에서 답은 n * (n-1) / 2입니다. 유 방향 그래프에서 에지는 두 노드 사이에서 양방향으로 발생할 수 있으며, 답은 n * (n-1)입니다.
유 방향 그래프 :
질문 : n 개의 정점이있는 유 방향 그래프의 최대 간선 수는 얼마입니까?
- 자체 루프가 없다고 가정합니다.
- 주어진 시작 정점에서 주어진 끝 정점까지 최대 하나의 가장자리가 있다고 가정합니다.
각 모서리는 시작 꼭지점과 끝 꼭지점으로 지정됩니다. 시작 정점에는 n 개의 선택 항목이 있습니다. 자체 루프가 없기 때문에 끝 정점에 대해 n-1 개의 선택 항목이 있습니다. 이것들을 함께 곱하면 가능한 모든 선택이 계산됩니다.
답변 :n(n−1)
무 방향 그래프
질문 : n 개의 정점이있는 무 방향 그래프에서 최대 간선 수는 얼마입니까?
- 자체 루프가 없다고 가정합니다.
- 주어진 시작 정점에서 주어진 끝 정점까지 최대 하나의 가장자리가 있다고 가정합니다.
무 방향 그래프에서 각 간선은 두 끝점으로 지정되며 순서는 중요하지 않습니다. 따라서 가장자리 수는 정점 집합에서 선택한 크기 2의 하위 집합 수입니다. 정점 세트의 크기가 n이므로 이러한 부분 집합의 수는 이항 계수 C (n, 2) ( "n choose 2"라고도 함)에 의해 제공됩니다. 이항 계수 공식을 사용하면 C (n, 2) = n (n-1) / 2입니다.
답변 :(n*(n-1))/2
Chris Smith가 제공 한 직관적 인 설명 외에도 방향이없는 그래프를 고려하는 다른 관점에서 이것이 왜 그런지 고려할 수 있습니다.
DIRECTED 그래프에서 답이 왜인지 알아 보려면 n*(n-1)무 방향 그래프를 고려하십시오 (단순히 두 노드 (A와 B) 사이에 링크가있는 경우 A에서 B로, B에서 A로 두 가지 방법으로 이동할 수 있음을 의미합니다. ). 무향 그래프의 에지들의 최대 번호는 n(n-1)/2분명 유향 그래프있다 여러 배 .
좋습니다 . 질문 할 수 있지만 방향이 지정되지 않은 그래프 에 최대 간선 이있는 이유는 무엇입니까? n(n-1)/2 이를 위해 n 개의 점 (노드)을 고려하고 첫 번째 점에서 얼마나 많은 모서리를 만들 수 있는지 물어보십시오. 분명히 n-1가장자리. 이제 첫 번째 점을 연결했다면 두 번째 점에서 몇 개의 모서리를 그릴 수 있습니까? 첫 번째와 두 번째 점이 이미 연결되어 있기 때문에 n-2할 수있는 가장자리가 있습니다. 등등. 따라서 모든 모서리의 합은 다음과 같습니다.
Sum = (n-1)+(n-2)+(n-3)+...+3+2+1
(n-1)Sum 에는 항이 있고 이러한 계열의 Sum 평균 은 ((n-1)+1)/2{(last + first) / 2}이므로,Sum = n(n-1)/2
그래프가 다중 그래프가 아닌 경우 각 노드는 기껏해야 다른 모든 노드에 대한 간선을 가질 수 있으므로 분명히 n * (n-1)입니다. 다중 그래프 인 경우 최대 제한이 없습니다.
다른 방식으로 말하면 :
완전한 그래프는 각각의 별개의 꼭지점 쌍이 이들을 연결하는 고유 한 가장자리가있는 무 방향 그래프입니다. 이것은 기본적으로 n 개의 정점 모음에서 2 개의 정점을 선택한다는 점에서 직관적입니다.
nC2 = n!/(n-2)!*2! = n(n-1)/2
무 방향 그래프가 가질 수있는 최대 간선 수입니다. 이제 유 방향 그래프의 경우 각 간선이 두 방향 간선으로 변환됩니다. 따라서 이전 결과에 2를 곱하면됩니다. 결과는 다음과 같습니다. n (n-1)
N 개의 정점이있는 유 방향 그래프에서 각 정점은 그래프의 N-1 개의 다른 정점에 연결할 수 있습니다 (가정, 자체 루프 없음). 따라서 총 모서리 수는 N (N-1)이 될 수 있습니다.
정답은 n * (n-1) / 2입니다. 각 모서리는 두 번 계산되었으므로 2로 나눕니다. 완전한 그래프에는 n choose 2 = n * (n-1) / 2로 주어진 최대 모서리 수가 있습니다.
n(n-1)/2다중 에지가 허용되지 않는 경우 그래프에 가능한 만큼의 에지 가있을 수 있습니다 .
그리고 이것은 우리가 정점에 레이블 을 붙이고 1,2,...,n에서 iff 까지의 가장자리 i가 j있으면 달성 할 수 i>j있습니다.
를 참조하십시오 여기 .
무 방향은 N ^ 2입니다. 단순-모든 노드에는 N 개의 에지 옵션 (자체 포함)이 있으므로 총 N 개의 노드가 있으므로 N * N
자체 루프가있는 그래프에서
max edges= n*n
예를 들어 4 개의 노드 (정점)가 있습니다.
4 nodes = 16 edges= 4*4
노드 쌍을 선택하는 방법의 수로 생각할 수도 있습니다 .n choose 2 = n (n-1) / 2. 한 쌍에만 가장자리가 하나만있을 수있는 경우 참입니다. 그렇지 않으면 2를 곱하십시오.
'Program Tip' 카테고리의 다른 글
| Maven-빌드 테스트 클래스 건너 뛰기 (0) | 2020.12.03 |
|---|---|
| 요소에서 두 번째 클래스 이름을 얻는 방법은 무엇입니까? (0) | 2020.12.03 |
| droppable 이벤트 종료시 jQuery 드래그 가능 객체를 원래 컨테이너로 되돌립니다. (0) | 2020.12.03 |
| SQL Management Studio의 시작 / 끝 블록에서 "스키마 만들기"를 사용할 수없는 이유는 무엇입니까? (0) | 2020.12.03 |
| ActiveRecord 범위에서 주문 제거 (0) | 2020.12.03 |