DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Oum, Sang-Il | - |
dc.contributor.advisor | 엄상일 | - |
dc.contributor.author | Cho, Ju-hyun | - |
dc.contributor.author | 조주현 | - |
dc.date.accessioned | 2011-12-14T04:57:01Z | - |
dc.date.available | 2011-12-14T04:57:01Z | - |
dc.date.issued | 2010 | - |
dc.identifier.uri | http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=455185&flag=dissertation | - |
dc.identifier.uri | http://hdl.handle.net/10203/42235 | - |
dc.description | 학위논문(석사) - 한국과학기술원 : 수리과학과, 2010.08, [ iii, 20 p. ] | - |
dc.description.abstract | For a simple directed graph $\It{F}$ if there is an arc from $\It{x}$ to $\It{y}$ for a pair $\It{x}$, $\It{y}$ of distinct vertices, then we call $\It{x}$ an $\It{inneighbor}$ of $\It{y}$ and conversely $\It{y}$ an $\It{outneighbor}$ of $\It{x}$. To locally complement F at a vertex v is for each inneighbor x and outneighbor y of v, to delete the arc (x, y) if there is an arc from $\It{x}$ to $\It{y}$, or to add an arc from x to y otherwise. We say that a directed graph $\It{F}$ is $\It{locally equvalent}$ to another directed graph $\It{H}$ if $\It{H}$ is obtained from F by successive local complementations. Furthermore a directed graph $\It{H}$ is a $\It{vertex-minor}$ of F if H can be obtained by applying a sequence of local complementations and deletions of vertices to $\It{F}$. A. Bouchet introduced Eulerian systems which are related to directed graphs and shows that a pair of directed graphs $\It{F}$, H have same Eulerian system if and only if $\It{H}$ is locally equivalent to F. We show that vertex-minor relation can be expressed in modulo-2 counting monadic second-order logic. This generalizes known properties of local complementations and vertex-minors of undirected graphs to directed graphs. | eng |
dc.language | eng | - |
dc.publisher | 한국과학기술원 | - |
dc.subject | vertex-minor | - |
dc.subject | monadic second-order logic | - |
dc.subject | local equivalence | - |
dc.subject | directed graphs | - |
dc.subject | eulerian systems | - |
dc.subject | 오일러리안 시스템 | - |
dc.subject | 꼭지점마이너 | - |
dc.subject | 단항 이차 논리 | - |
dc.subject | 국지적 동등 | - |
dc.subject | 유향그래프 | - |
dc.title | Local equivalence of directed graphs and monadic second-order logic | - |
dc.title.alternative | 유향그래프의 국지적 동등과 단항 이차 논리 | - |
dc.type | Thesis(Master) | - |
dc.identifier.CNRN | 455185/325007 | - |
dc.description.department | 한국과학기술원 : 수리과학과, | - |
dc.identifier.uid | 020084129 | - |
dc.contributor.localauthor | Oum, Sang-Il | - |
dc.contributor.localauthor | 엄상일 | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.