what is the problem ?
who solved?
나보고 풀라고 한다면 ?
이 그림에서 보면 패턴
red- red -blue X3 은 yellow point
blue-blue-red X3 은 green point
point
1. 모든 vertex에서의 degree가 같다.
2. directed graphic 이다.
조건에 있는지는 모르겠지만 red, blue color수가 같다.
방향도 대칭이다.
<수학적인 묘사>
1) G : finite directed graph
2) all vertexs have the same out-degree K
3) all the edges going out from a vertex takes a diffrerent label
얼핏 문제보면 compiler의 register 최적화 기법이 떠오르지만 완전 다른 문제이다. 물론 이 기법은 network에 적용해야 겠지
문제를 engineering 관점으로 본다면 ?
1) algorithm이 간단해진다.
- 만약 어느 지점에서 다른 지점으로 간다면 matrix table이나 어떤 table 을 참조해야 할 것이다. ( router 의 경우 routing table을 이용한다면 )
2) 그렇지만 어느 지점을 가기 위한 최소한의 거리는 아니다.
table 을 이용하는 검색시간 과 그냥 알고리즘을 적용하는 시간 trade off
=>거리가 가까울 수록 유리
3)위의 알고리즘은 특정지역에만 도달할 수 있다.
가령 yellow point와 green point
따라서 한벙향 통신에만 적용된다.
굳이 적용하라고 한다면
ubiquitous에서 각각의 sensor들의 정보를 모을 때 유리할 것같다. 802.15.4 통신에 유리 할 것으로 보임
finite automata = finite state machine
directed graph = periodic graph
