전치 그래프

그래프 이론의 수학적 및 알고리즘적 연구에서 지시된 그래프 G의 역,^[1] 전치^[2] 또는 역방향은^[3] G의 해당 가장자리의 방향과 비교하여 모든 가장자리가 반전된 동일한 정점 집합에 대한 또 다른 방향 그래프다.즉, G에 에지$({\displaystyle u}$, v${\displaystyle }$) ${\displaystyle (u,v)}$이(가) 포함되어 있으면$$ G의 역/전송/후진에는${\displaystyle \mathrm{에지}(v}$,$$u ) {\$displaystyle (v,$u$$)}이(가) 포함되어 있고 그 반대의 경우도 있다.

표기법

역이라는 이름은 화살의 반전이 논리에 함축된 의미를 갖는 것에 해당하기 때문에 발생한다.전치라는 이름은 전치 지시 그래프의 인접 행렬이 원래 지시된 그래프의 인접 행렬의 전치 행렬이기 때문이다.

선호 용어에 대한 일반적인 동의는 없다.

역은 어떤 용어를 사용하는지, 어떤 책이나 글이 표기법의 근원이 되는지에 따라 상징적으로 G', G, G^R 또는^T 기타 표기법으로 표기된다.

적용들

그래프와 그 전치 사이에는 수학적으로 거의 차이가 없지만, 주어진 그래프를 어떻게 나타내느냐에 따라 컴퓨터 공학에서는 그 차이가 더 클 수 있다.예를 들어, 웹 그래프의 경우, 정점의 발신 링크를 결정하는 것은 쉽지만 들어오는 링크를 결정하는 것은 어려운 반면, 이 그래프의 반전에서는 그 반대다.따라서 그래프 알고리즘에서는 그래프에서 수행되는 작업에 더 적합한 형태로 그래프를 삽입하기 위해 그래프 반전의 명시적 표현을 구성하는 것이 유용할 수 있다.그 예로는 깊이 첫 번째 검색을 두 번, 주어진 그래프에 한 번, 그리고 그 반전에 두 번 적용하는 강하게 연결된 구성 요소에 대한 코사라주의 알고리즘이 있다.

관련개념

스큐 대칭 그래프는 모든 정점을 쌍으로 이루는 특별한 종류의 이형성을 통해 자신의 전치 그래프에 이형성을 갖는 그래프다.

이항 관계의 역관계는 관련 개체의 각 쌍의 순서를 거꾸로 하는 관계다.관계를 지시된 그래프로 해석하면 이는 그래프의 전치(轉治)와 같은 것이다.특히 부분순서의 이중순서는 이런 식으로 해석할 수 있는데, 이는 전이적으로 닫힌 방향의 아크순환 그래프의 전치라고 해석할 수 있다.

참고 항목

• 컨버스 관계

참조