무향 그래프의 'n'개의 정점과 0 개의 모서리가 있습니다. 우리가 그릴 수있는 최대 엣지 수는 그래프가 연결되지 않은 채로 남을 수 있습니다.최대 수를 찾으십시오. 그래프의 모서리 부분
나는 우리가 하나 개의 정점을 제외 할 수 있습니다 그래프가 여전히 분리 유지되도록, 무향 그래프의 n-1 개의 정점 사이의 모서리의 최대 수를 찾을 수있는 솔루션을 만들었습니다. n 개의 꼭지점에 대해 n (n-1)/2이고 n-1 개의 꼭지점에 대해 (n-1) (n-2)/2가됩니다.
솔루션이 최상의 솔루션이어야합니다.
새 가장자리를 추가하면 한쪽 끝에 n 번째 꼭지점이 있어야하기 때문에.
그래프에 여러 가장자리가있을 수 있으면 n> = 3 인 경우 무한대가됩니다.
자체 루프를 포함 할 수도있는 경우 n> = 2 인 경우 대답은 무한대입니다.
해결 방법이 정확하지 않으면 답이 맞지 않습니다.
분석을 사용하여 해결할 수 있습니다. 당신의 아이디어를 가지고 그것을 일반화하십시오. 크기가 x 및 n-x 인 n 개의 정점을 두 그룹으로 나눕니다. 이제 모서리의 수는
f(x)= x(x-1)/2 + (n-x)(n-x-1)/2
f(x) = 1/2(2x^2 - 2nx +n^2 - n)
이 기능을 사용하면 원하는 파티션 크기가 최대 값에 의해 표현 x의 함수이다. 계산을하면 x=0에서 x=n/2으로 감소한 다음 x=n으로 증가합니다. x = 0 또는 x = n은 그래프가 수집됨을 의미하므로 다음으로 큰 값인 x=1을 취합니다. 그래서 당신의 직감이 최적입니다.
추가 된 새 가장자리를 beacuse하는 이유는 "한쪽 끝에 n 번째 꼭지점이 있어야합니다."는 설명이 왜 * 전역 최대 *가 아닌 * 최대 값 *인지 설명합니다. 이 설명은 구조가 완전히 다른 솔루션을 다루지는 않습니다. 왜곡 된 이유가 무엇인지에 대한 적절한 증거없이 더 많은 모서리를 가질 수 있습니다. – amit
다중 도트의 가장자리 수는 분명히 무한합니다. 이제 자체 루프를 가질 수없는 경우 에지를 추가하기 위해 두 개의 정점을 선택해야합니다. 첫 번째 (n-1) 개의 정점을 완전히 연결했습니다. 하나의 가장자리를 더 추가하려면 처음 n-1 개의 정점에서 모든 모서리를 만들었으므로 두 개의 정점 모두 n-1 개의 정점 세트에서 올 수 없습니다. 따라서 가장자리 중 하나가 n 번째 여야합니다. 셀프 루프가 허용되면 자체 루프가 연결을 추가하지 않기 때문에 n 개의 에지를 추가 할 수 있습니다. – sukunrt
이것은 1, n-1이 아닌 두 개의 완전한 서브 그래프로 구성된 그래프의 가능성을 전혀 다루지 않습니다. 해결책은 (사고로) 맞았지 만 추론은 그렇지 않습니다. – voidengine