서지주요정보
Connecting rank-width and tree-width via pivot-minors = Pivot-minor들을 이용한 rank-width와 tree-width의 관계에 대한 연구
서명 / 저자 Connecting rank-width and tree-width via pivot-minors = Pivot-minor들을 이용한 rank-width와 tree-width의 관계에 대한 연구 / O-Joung Kwon.
저자명 Kwon, O-Joung ; 권오정
발행사항 [대전 : 한국과학기술원, 2012].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8024343

소장위치/청구기호

학술문화관(문화관) 보존서고

MMAS 12006

SMS전송

도서상태

이용가능

대출가능

반납예정일

초록정보

We prove that every graph of rank-width $k$ is a pivot-minor of a graph of tree-width at most $2k$ and every graph of linear rank-width $k$ is a pivot-minor of a graph of path-width at most $k+1$. We also prove that graphs of rank-width at most $1$ are exactly vertex-minors of trees, and graphs of linear rank-width at most $1$ are precisely vertex-minors of paths. In addition, we show that bipartite graphs of rank-width at most $1$ are exactly pivot-minors of trees and bipartite graphs of linear rank-width at most $1$ are precisely pivot-minors of paths. Also, we calculate the linear rank-width of complete binary trees. And we show that if a tree has linear rank-width at least $k$, then it has the complete binary tree of height $k$ as a vertex-minor. Finally, we describe an interesting question that a class of graphs with unbounded linear rank-width contains all trees as vertex-minors or pivot-minors. We prove that this question for pivot-minor is false and we suggest another version of the question.

Tree-width가 $k$인 그래프는 rank-width가 $k+1$ 이하임이 알려져 있었지만, rank-width가 작은 그래프에 대해서는 tree-width와 관련된 결과가 없었다. 3장에서 우리는 처음으로 rank-width가 $k$ 이하인 그래프는 tree-width가 $2k$인 그래프의 pivot-minor로 얻을 수 있음을 증명하였고, 또한 linear rank-width가 $k$ 이하인 그래프는 path-width가 $k+1$인 그래프의 pivot-minor로서 얻을 수 있음을 증명하였다. 이 증명의 보조정리로서 rank-width가 $1$인 그래프는 정확히 트리의 vertex-minor들이고 linear rank-width가 $1$인 그래프는 정확히 패쓰의 vertex-minor들임을 증명하였다. 그리고 그래프들이 이분 그래프이면, 이 보조정리들의 vertex-minor를 pivot-minor로 대체할 수 있음을 보였다. 4장에서는, 높이가 $k$인 완전 이진 트리들과 그들의 결합 그래프들의 linear rank-width를 계산하였다. 또한 트리가 linear rank-width가 $k$보다 크면 높이가 $k$인 완전 이진 트리들을 vertex-minor로서 가짐을 증명하였다. 5장에서는, 우리는 그래프가 linear rank-width가 어떤 수 이상이면 반드시 어떤 그래프를 vertex-minor 혹은 pivot-minor로서 가진다는 문제에 대해서 생각해보았다. 처음에는 유명한 Robertson과 Seymour의 path-width 정리처럼 문제의 어떤 그래프가 트리가 될 것이라고 추측을 하였다. 하지만, pivot-minor에 대해서는 이 추측이 잘못 되었다는 사실을 증명하였고, 트리를 대신하여 트리의 결합 그래프가 어떤 그래프에 들어갈 것이라고 문제를 제시하였다.

서지기타정보

서지기타정보
청구기호 {MMAS 12006
형태사항 iv, 29 p. : 삽도 ; 30 cm
언어 영어
일반주기 저자명의 한글표기 : 권오정
지도교수의 영문표기 : Sang-Il Oum
지도교수의 한글표기 : 엄상일
학위논문 학위논문(석사) - 한국과학기술원 : 수리과학과,
서지주기 References : p. 27
주제 rank-width
tree-width
vertex-minor
pivot-minor
rank-width
tree-width
vertex-minor
pivot-minor
QR CODE qr code