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년 유향그래프와 관련된 오일러리안 시스템을 소개하였다. 각각의 유향그래프는 그것들과 관련된 오일러리안 시스템이 있다. 부쉐는 두 유향그래프에 대해 각각에 대해 관련된 오일러리안 시스템이 같다는 것과 두 유향그래프가 서로 국지적으로 동등하다는 것이 동치임을 증명하였다. 그래서 우리는 그 사실을 이용하여 주어진 유향그래프에 대해 입력되는 유향그래프가 처음 주어진 유향그래프와 동등한 꼭짓점마이너를 갖는지를 확인하는 알고리즘이 단항 이차 논리로 표현될 수 있음을 증명하였다. 그리고 이것은 무향그래프에서 증명된 것을 유향그래프로 일반화시킨 것이다.
