in-degrees의 합 $\sum_{v\in V} id(v)$ 그리고 이상도 $\sum_{v\in V} od(v)$ 항상 같습니까?
저는 Ralph P. Grimaldi의 이산 및 조합 수학, 응용 서론 제 5 판 섹션 11.3의 문제 # 24에 대해 작업하고 있습니다.
질문:
허락하다 $G=(V,E)$ 유 방향 그래프 여야합니다. 여기서 $|V|=n$ 과 $|E|=e$. 값은 무엇입니까$\sum_{v\in V} id(v)$ 과 $\sum_{v\in V} od(v)$?
$id(v)$ 과 $od(v)$ in-degrees와 out-degrees입니다.
11.3 절의 끝 부분에 합격 학위가 언급되어 있으므로이 질문에 답할 수있는 권한이 있습니다.
나는 필요한 사실을 추론하려고 $\sum_{v\in V} id(v)$ 과 $\sum_{v\in V} od(v)$ 내 논리가 올바른지 알고 싶습니다.
한정된 수의 정점이 주어지면 $n$ 추가하는 모든 '방향성'에지에 대해 $1$ ...에 $\sum_{v\in V} id(v)$ 과 $\sum_{v\in V} od(v)$ 항상 동일해야합니까?
그렇다면 $\sum_{v\in V} id(v)=\sum_{v\in V} od(v)=e?$
답변
아이디어를 엄격하게 만들려면 인덕션을 사용해야합니다. 허락하다$Q(k)$ 모든 방향성 그래프가 정확히 $k$모서리는 원하는 주장을 충족합니다. 그런 다음 유도를 사용하십시오.$Q$. 이렇게하면 않도록 조심 하지 않으면 "와 같은 아무것도 할$Q(k)$ 사실이라면 $G$ 방향성 그래프 $k$모서리를 추가하고 모서리를 추가하십시오 ... "! 유도 에 대한이 설명을 읽고 유도를 올바르게 수행했는지 확인하십시오.