귀납법으로 그래프 문제를 증명할 때 항상 노드를 하나 지우는 방식으로 접근하라고 배웠는데 사실 왜 그렇게 해야 맞는지는 확실히 배우지 않았다. 물론 그냥 딱 듣고 왜 그런지 알아채는 친구들도 있겠지만.. 내 경우에는 ㄴㄴ With the help of Professor John F. Hughes, Brown University Department of Computer Science, here is a proof showing why you should always remove a vertex, not add a vertex, in the induction step of your proofs on graphs.
An Euler trail is a walk that uses every edge of a graph exactly once. An Euler circuit is a circuit that uses every edge of a graph exactly once. A Euler trail with same endpoints is a Euler circuit. Here are some examples: Letbe a finite connected graph and denote the number of vertices that have odd degrees. Prove that G has a Euler trail if and only if . First, by the Handshake Theorem, we c..
Prove that for , . Intuition: Suppose n people shake hands with other people in the group. They don't shake hands twice with the same person.How many handshakes take place?각 사람을 노드로 본다면 두 사람이 악수를 하면 그 두 노드 사이에 Edge 가 생긴다.전체 악수의 수 = Number of Edges in the graph = 각 사람이 한 악수의 수의 총합 / 2 = Sum of degree of every vertex / 2 Let be the vertices of G and their degrees respectively. Also, Then we know t..
When designing an algorithm, ask yourself : For which cases does the obvious method work? Then find a new way to tackle the remaining cases! 예제) Find a hamiltonian path through a tournament graph. Using a more-of-input approach, we claim to have a solution while pretending that the nodes we have processed so far is the entire input instance. We want to maintain the Loop Invariant by adding a new..