http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
재귀원형군과 토러스에서 쌍형 다대다 서로소인 경로 커버 (pp.40-51)
김유상(Eusang Kim),박정흠(Jung-Heum Park) 한국정보과학회 2009 정보과학회논문지 : 시스템 및 이론 Vol.36 No.1
그래프 G의 쌍형 다대다 k-서로소인 경로 커버(쌍형 k -DPC)는 k개의 서로 다른 소스-싱크쌍을 연결하며 그래프에 있는 모든 정점을 지나는 k개의 서로소인 경로 집합이다. 이 논문에서는 재귀원 형군 ?G(cd<SUP>m</SUP>,d), d≥3과 토러스에서 서로소인 경로 커버를 고려하여, 이분 그래프가 아니고 분지수가?δ인 재귀원형군과 토러스는 고장 요소(정점이나 에지)가 f 개 이하일 때 f+2≤ δ-1을 만족하는 임의의 f, k ≥1 에 대하여 쌍형 k -DPC를 가짐을 보인다. A paired many-to-many k-disjoint path cover (paired k-DPC) of a graph G is a set of k disjoint paths joining k distinct source-sink pairs in which each vertex of G is covered by a path. In this paper, we investigate disjoint path covers in recursive circulants G(cd<SUP>m</SUP>,d) with d≥3 and tori, and show that provided the number of faulty elements (vertices and/or edges) is f or less, every nonbipartite recursive circulant and torus of degree δ has a paired k -DPC for any f and k ≥1 with f+2≤δ-1 .