서지주요정보
Local equivalence of directed graphs and monadic second-order logic = 유향그래프의 국지적 동등과 단항 이차 논리
서명 / 저자 Local equivalence of directed graphs and monadic second-order logic = 유향그래프의 국지적 동등과 단항 이차 논리 / Ju-Hyun Cho.
저자명 Cho, Ju-hyun ; 조주현
발행사항 [대전 : 한국과학기술원, 2010].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8021791

소장위치/청구기호

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

MMA 10015

SMS전송

도서상태

이용가능

대출가능

반납예정일

초록정보

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.

유향그래프는 점과 방향성을 가진 선분으로 이루어져 있다. 어느 한 점에 대해 그 점으로 향해오는 선분의 시작점을 그 점의 내접점이라고 하고 반대로 그 점에서 나가는 직선의 끝점을 외접점이라고 한다. 유향그래프에서의 한점에서 국지적 보완을 하는 것은 그 점의 외접점과 내접점에 대해 만약 내접점에서 외접점으로 향한 선분이 있다면 그 선분을 제거하고 반대로 없다면 그 내접점에서 외접점으로 선분을 이어주는 것이다. 어떤 유향그래프에 대해 국지적 보완에 의해 만들어진 유향그래프를 처음의 그래프와 국지적으로 동등하다라고 말한다. 그리고 한 유향그래프에 국지적 보완을 적용하고 점을 없앰으로써 만들어진 유향그래프를 처음의 유향그래프의 꼭짓점마이너라고 부른다. 부쉐가 1987년 유향그래프와 관련된 오일러리안 시스템을 소개하였다. 각각의 유향그래프는 그것들과 관련된 오일러리안 시스템이 있다. 부쉐는 두 유향그래프에 대해 각각에 대해 관련된 오일러리안 시스템이 같다는 것과 두 유향그래프가 서로 국지적으로 동등하다는 것이 동치임을 증명하였다. 그래서 우리는 그 사실을 이용하여 주어진 유향그래프에 대해 입력되는 유향그래프가 처음 주어진 유향그래프와 동등한 꼭짓점마이너를 갖는지를 확인하는 알고리즘이 단항 이차 논리로 표현될 수 있음을 증명하였다. 그리고 이것은 무향그래프에서 증명된 것을 유향그래프로 일반화시킨 것이다.

서지기타정보

서지기타정보
청구기호 {MMA 10015
형태사항 iii, 20 p. : 삽도 ; 26 cm
언어 영어
일반주기 저자명의 한글표기 : 조주현
지도교수의 영문표기 : Sang-Il Oum
지도교수의 한글표기 : 엄상일
학위논문 학위논문(석사) - 한국과학기술원 : 수리과학과,
서지주기 Includes References.
주제 directed graphs
local equivalence
monadic second-order logic
vertex-minor
eulerian systems
유향그래프
국지적 동등
단항 이차 논리
꼭지점마이너
오일러리안 시스템
QR CODE qr code