그래프 이론 1장 연습문제 풀이

소개글

그래프 이론 1장 연습문제 풀이에 대한 보고서 자료입니다.

목차

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

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

3. Given an undirected, connected graph G, show that it is always possible to find a circuit which traverses each edge exactly twice, once in each
direction. Show such a circuit on the graph below

4. The diameter of a graph is definded as the maximum number of edges which must be traversed to get from any one vertex to any other. What is the diameter of a (K, W) DeBruijn Graph?

본문내용

umber of edges which must be traversed to get from any one vertex to any other. What is the diameter of a (K, W) DeBruijn Graph?
[answer] diameter : 그래프에서 임의의 두 vertex 사이의 최단거리 중에서 가장 큰값을 말함
DeBruijn Graph에서 본다면 두 vertex 사이의 가장 큰값을 W-1이 라고 볼수 있다.
그 이유는 가장 크게 가질수 있는 words of length를 W-1 이기 때문이다. 그리고 또한 하나의 edge를 지날 때 마다 한 bit씩 이동 하므로 최대로 변할 수 있는 수는 W-1이 된다.
그러므로 DeBruijn Graph의 diameter는 W-1이다.

키워드

그래프 이론,   연습문제 풀이,   알고리즘,   circuit,   Graph,   vertex