MoonNote

- 모든 vertex를 정확히 한번씩 pass하는 그래프, 모든 edge를 pass할 필요는 없음

- Line Graph란? Simple graph G의 Line Graph L(G)란 G의 edge와 1대1로 대응하는 vertex로 이루어진 그래프이다. G의 해당 edge가 인접하는 경우에만 L(G)의 두 vertex가 인접한다.

정의 : 그래프 G(V)의 모든 vertex의 deg(V) = k로 일정

정의 : 해당 그래프의 Shortest Cycle의 길이

다음과 같은 철골구조에서 RIGID(튼튼)한 것과 그렇지 않은 것 1)구별하는 방법과 제시된 cross bar의 갯수가 2)최소로 필요한 갯수인지 알 수 있는 방법은? 1) RIGID 구별 방법 1. 철골구조의 row와 column을 bipartite graph로 나타낸다. 2. bipartite graph의 component들이 연결이 된다면 RIGID 하고 그렇지 않다면 NOT RIGID하다. 2) RIGID를 위해 필요한 cross bar의 최소 갯수 1. bipartite graph에서 edge 수가 가장 적은 경우를 찾는 문제로 치환할 수 있다. 2. 결국, bipartite graph에서 spanning tree 찾기 문제다.

정의 : 서로 compatible한 vertex에 edge를 연결한 graph 다음은 어떤 3각 교차로의 상황을 나타낸 그림이다. 이 교차에서 우리가 관찰하는 것은 6개의 주행선이다. 이 교차로는 각 주행선마다 방향이 지정되어 있어 만일 오른쪽에서 들어와 아래쪽 방향으로 가려고 한다면 반드시 b 주행선에 들어와서 준비를 해야 한다. Problem) 어떤 2개의 주행선이 동시에 진행될 수 있으면 이 두 주행선은 서로 compatible 하다라고 이야기한다. 6 개의 주행선을 node로 하는 Compatibility Graph를 구성해 보시오. 그리고 우리는 1분 주기로 신호등을 조작해서 소통을 원할하게 하려고 한다. 그 원할의 정도는 각 lane에서 자기 신호를 위하여 기다리는 시간(waiting time..