그래프 이론

1. For each set of integers shown below, draw a simple graph(no self-loops or parallel edges) having the indicated degrees or tell why you can`t a) 2, 2, 3, 2, 2, 3 b) 1, 1, 2, 3, 4 simple graph를 그릴 수가 없다. 왜냐하면, odd degrees의 vertices의 수가 even이 되어야 하는데 그 조건을 만족하지 않는다. c) 1, 2, 3, 3, 5 역시 simple graph를 그릴 수가 없다. 이유는 위와 동일하며, 만약 simple graph가 되기 위해서는 마지막 integer 5의 degree가 성립하기 위해서 self-loop나 parallel edge가 생겨야만 한다. d) 1, 1, 2, 2, 4 2. Show that if self-loops and parallel edges are permitted then for any set of n, positive integers whose sum is even, there exists a graph whose n vertices have the indicated degrees [answer] any set of positive integers = 위 any set of positive integers의 vertex를 라 하고, degree를 라 하자. 그러면 위에 해당하는 vertex에 대한 set of integer를 다음과 같이 만들 수 있다. edge의 set은 위의 vertex 중에서 임의의 두 개를 선택해서 만들 수 있으므로 integer의 합은 even 이므로 모든 vertex를 edge의 set으로 만들 수 있다. 3. Given an undirected, connected graph G, …
…