그래프 이론에 대한“까다로운”질문
그래서 저는 그래프 이론을 수정하고 있습니다. 적어도 나에게는 까다롭기 때문에 도움 / 피드백을 얻어야합니다. 시간이 촉박 한 시험에서 나오기 때문에 신속하게 답변해야합니다. (그래서 강력한 이론 요구 사항이나 똑똑한 "통찰"이있는 것 같습니다.)
-Eulerian과 bipartite 인 1871 개의 꼭지점이있는 그래프가 있습니다.
이분하려면 홀수 길이의주기가 없어야합니다. 오일러 원이 있으면 일련의 분리 된 원으로 분할 될 수 있습니다 (그리고 모두 길이가 균등해야합니다). 그래서 우리가 모든 것을 더하면 우리는 짝수의 모서리를 가져야합니다.$\exists k$ 그런 $|Ε|=2k \rightarrow \frac{\sum_{i}^n deg(v_i)}{2}=2k \rightarrow \sum_{i}^n deg(v_i)=4k$. 그러나 나는 꼭지점 수를 어디에도 사용하지 않습니다. 나는 아무데도 ..
단순 (평행 에지 없음), 무 방향 그래프에 대한 에지의 최대 값은 얼마입니까? $n \geq 10$ 그것은 Eulerian이고 적어도 두 개의 다른 Hamilton 서클이 있다는 것을?
Inclass, 우리는 Eulerian이되기 위해 n이 짝수이면 최대 $n(n-2)$ n이 홀수이면 최대 $\frac{n(n-1)}{2}$. 우리는 기본적으로 다리가 없다는 것을 알고 있습니다. 따라서 모든 모서리는 원에 속합니다. Eulerian이므로 모든 정점에는 짝수 차수가 있습니다. 해밀턴 원이있는 그래프에 가장자리를 추가하면 해밀턴 속성에 해를 끼치 지 않으므로 Eulerian 속성에만 영향을줍니다. 그래서 우리는 해밀턴 원이 두 개인 그래프가 어떻게 Eulerian이 될 수 있는지 조사해야합니다. 해밀턴 원은 정점을 반복하지 않으므로 가장자리도 없습니다. 이 2 개의 Hamilton 원이 완전히 분리 된 경우 (각 원은 n 개의 모서리로 구성됨) Euler 원에는 최소 2n 개의 모서리가 있습니다.
참고 : 두 번째 질문에는 추가 질문이있었습니다. 다음 을 사용하여 단순 (평행 모서리가없는), 무 방향 그래프에 대한 최소 모서리 수를 찾습니다.$n \geq 10$ 그것은 Eulerian이고 적어도 두 개의 다른 Hamilton 서클이 있다는 것을?
답변
- Eulerian과 bipartite 인 1871 개의 꼭지점이있는 그래프가 있습니다.
이것은 홀수의 정점으로 당신을 속이려는 것입니다. 이것은 bipartition의 두 부분이 같은 크기를 가질 수 없음을 의미합니다. 그러나 이것은 오일러 사이클이 아닌 해밀턴 사이클의 문제 일뿐입니다.
이 그림은 임의의 홀수에 대해 이분 Eulerian Graph를 생성 할 수 있음을 보여줍니다 ( $\ge 7$) 정점 :
규칙적인 빨간색 패턴이 시작된 것과 같은 쪽에서 끝나는 것은 중요하지 않습니다. 오일러주기를 얻기 위해 가장자리를 2 개 더 (녹색) 추가하면됩니다.
- 단순 (평행 에지 없음), 무 방향 그래프에 대한 에지의 최대 값은 얼마입니까? $n\ge 10$ 그것은 Eulerian이고 적어도 두 개의 다른 Hamilton 서클이 있다는 것을?
이상한 경우 $n$ 간단합니다. 완료되었습니다. $K_n$ 와 ${n \choose 2} = \frac{n(n-1)}2$ 가장자리.
짝수 $n$, 꼭지점 당 하나 이상의 가능한 가장자리가 그래프에있을 수 없습니다 (각 꼭지점의 정도를 균일하게 만들기 위해). 즉, 최소한$\frac{n}2$전체 그래프에서 가장자리. 정점을 쌍으로 연결하면 완벽한 일치를 뺀 완전한 그래프를 얻을 수 있습니다. 그 그래프는 Eulerian이고 (왜냐하면$n$충분히 큽니다) 여전히 2 개의 다른 해밀턴주기가 있습니다). 그래서 여기서 답은${n \choose 2} -\frac{n}2= \frac{n(n-2)}2$
ADDED : 두 번째 예제의 그래프에 적어도 두 개의 해밀턴주기가있는 이유는 무엇입니까? 그들은 이상하기 때문에$n$ 정확하고 심지어 $n$ 거의 완전한 그래프 $K_n$! 주어진 정점 세트를 사용하면 가장자리가 많을수록 더 좋습니다 (필요하지 않지만 Hamiltonian주기에 사용할 수 있음). 이 그래프에는 해밀턴 사이클이 많이 있습니다. 2는 매우 쉬운 하한입니다.
짝수 사례를 살펴 보겠습니다. $n$:
위의 구성은 빨간색 "래더 가로대"를 제외하고 점 사이의 모든 모서리가 그래프에 있음을 의미합니다. 사다리의 각 측면에서 녹색으로 된 2 개의 사이클과 몇 가지 더 많은 가장자리 (파란색과 보라색)를 선택했습니다.
사다리의 왼쪽에서 시작하면 첫 번째 파란색 가장자리에 도달 할 때까지 올라가고 파란색 가장자리가있는 오른쪽으로 건너간 다음 아래쪽의 "외부"녹색 가장자리를 잡고 위로 올라가면 Hamiltonian 한 명을 얻게됩니다. 다른 파란색 가장자리를 만날 때까지 다시 오른쪽에서 왼쪽으로 다시 교차하고 왼쪽 "외부"녹색 가장자리를 아래쪽으로 가져간 다음 처음 시작 지점에 도달 할 때까지 위로 이동합니다.
이 절차를 다시 수행하면 다른 Hamiltonian을 얻지 만 보라색 가장자리를 사용하여 왼쪽에서 오른쪽으로 그리고 뒤로 교차합니다.
왼쪽과 오른쪽 지점을 선택하고 녹색주기에서 정렬하는 방법을 선택할 수있는 방법이 너무 많아서 "단지 2"해밀턴주기는 이미 최소값에 대한 광대 한 절제 문구입니다. $n$ 10의.