Graph Theory(1), 과거로의 여행

A Direct Graph Direct Graph는 G = ( V X E) 로 표현되며, 유한한 vertex 집합과, 유한한 edge들의 집합을 가지며, edge는 source Vertex와 target vertex를 포함한다. 전반적인 vertex 와 edge의 그림은 다음을 참조한다. Open Source인 QuickGraph를 참조로 하여, 코드로 표현해 본다.

public interface IEdge 
{
    TVertex Source {get;}
    TVertex Target { get;}
}

인터페이스 IEdge는 정의대로 Generic으로 선언된 Source Vertex와 Target Vertex를 갇는다.

 e = (u, v)에서 edge e는 Vertex u의 out-edge이고, v의 in-edge이다. 

in-degree(v) 는 incoming edge의 수를 가리킨다. (들어오는 edge) 

out-degree(u) 는 outcoming edge의 수를 가리킨다 (나가는 edge) 

하나의 그래프는 u와 v가 같은 vertex pair로 부터의 multi edge를 허락하며, multi-graph라 한다. 

하나의 path는 연속으로 이어진 edge e1e2....en의 집합이며, 각각의 edge들은 부모 자식 관계가 성립된다. 

하나의 Cycle은 시작 vertex와 끝 vertex가 같은 하나의 path이다. 

하나의 directed acyclic graph는 cycle이 없는 directed graph이다. 

하나의 Weighted directed graph는 각 vertex간에 특정한 값(예를 들어 거리)가 존재하는 directed graph이다. 

하나의 adjacency graph는 direct graph를 표현한 데이타 구조이며, out-edge 만으로 어떤 vertex로 접근하며, adjacency matrix를 만들 수 있다. 

bidirectional graph는 direct graph를 표현한 데이타 구조이며, in-edge,out-edge 둘다 어떤 vertex로 접근할수 있다. 추가.. 

(Object C로 edge 구현)

#import 
#import "Vertex.h"

@interface Edge : NSObject {
	Vertex *source;
	Vertex *target;
}

@property (readonly, retain) Vertex *source;
@property (readonly, retain) Vertex *target;

@end

그리고 implementation은 다음과 같다. Object C 2.0의 Property를 사용한다.

#import "Edge.h"

@implementation Edge

@synthesize source;
@synthesize target;

@end