http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
- 中文 을 입력하시려면 zhongwen을 입력하시고 space를누르시면됩니다.
- 北京 을 입력하시려면 beijing을 입력하시고 space를 누르시면 됩니다.
RISS 인기검색어
- 검색키워드
- 저자 : 박혜련(Hye Ryon Park) (검색결과 1 건)
- 무료
- 기관 내 무료
- 유료
-
직병렬 유향 그래프의 기하학적 대칭성 탐지 및 드로잉 알고리즘
박혜련(Hye-Ryon Park),홍석희(Seok-Hee Hong),이상호(Sang-Ho Lee) 한국정보과학회 1998 정보과학회논문지 : 시스템 및 이론 Vol.25 No.5
그래프 드로잉이란 그래프가 갖고 있는 추상적인 정보를 시각적으로 보여줄 수 있는 형태로 구성하여 이를 이차원 평면상에 그려주는 것을 의미한다. 보통 그래프의 정점은 하나의 점으로 표현되며 에지는 이러한 점들을 이어주는 선분이나 아크로 표현된다. 좋은 드로잉은 그래프의 시각화를 통하여 그래프 구조에 대한 이해도를 증진시킬 수 있으며 정보의 의미를 명확하게 전달할 수 있고 판독성을 증가시킨다. 대칭적으로 그려진 드로잉은 그래프의 구조와 특성을 시각적으로 표현할 수 있게 하지만 일반적인 그래프가 기하학적 대칭성을 갖는지의 여부를 결정하는 것은 NP-complete 문제로 증명되어 있다. 본 논문에서는 평면 그래프의 한 부류로서 스케쥴링 문제나 네트워크의 모델링에 많이 사용되는 직병렬 유향 그래프를 대상으로 하여 그의 기하학적 대칭성을 탐지하는 o(m)-시간 알고리즘과 직병렬 유향 그래프의 드로잉 알고리즘을 제안하였다. 단, m은 주어진 직병렬 유향 그래프가 갖고 있는 에지의 개수이다. Graph drawing is constructing a visually-informative drawing of an abstract graph in the plane. Typically, each vertex of a graph is represented by a point and each edge by a line segment or an arc between its corresponding points. Good drawing can help to understand the structure of a graph and the meaning of information that the graph has. It also increases the readability of the graph. Symmetric drawing enables an understanding of the entire graph to be built up from that of a smaller subgraph. But, the problem of determining if a given graph has any geometric symmetry is known to be an NP-complete problem when the graph is general. In this paper, we develope an o(m) -time algorithm for detecting geometric symmetry in a Series-Parallel (SP) digraph, where m is the number of edges in a given SP digraph. An SP digraph is a subclass of planar graph and is used for scheduling problems and network modeling. An algorithm for drawing SP digraphs is also developed and implemented.
연관 검색어 추천
이 검색어로 많이 본 자료
활용도 높은 자료
