그래프 이론 1장 연습문제 풀이
본 자료는 미만의 자료로 미리보기를 제공하지 않습니다.
닫기
  • 1
  • 2
  • 3
해당 자료는 1페이지 까지만 미리보기를 제공합니다.
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이다.
  • 가격1,000
  • 페이지수3페이지
  • 등록일2003.12.24
  • 저작시기2003.12
  • 파일형식한글(hwp)
  • 자료번호#240323
본 자료는 최근 2주간 다운받은 회원이 없습니다.
다운로드 장바구니