전압 그래프

그래프 이론에서 전압 그래프는 그룹의 요소에 의해 가장자리가 역전할 수 없는 것으로 표시된 방향 그래프다.게인 그래프와 형식적으로는 동일하지만, 일반적으로 위상 그래프 이론에서 전압 그래프의 파생 그래프라는 다른 그래프를 지정하는 간결한 방법으로 사용된다.

이 단체들 전압 그래프에 사용되는 전형적인 선택은 그two-element 그룹 ℤ2(그래프의 2부로 구성된 이중 커버를 정의하는), 자유 단체(그래프의 보편적인 커버를 정의하는)d-dimensional 정수 lattices ℤd(벡터 가법 산하 단체로,d-dimensional 유클리드 공간에서 주기적인 구조 정의하는 것으로 간주되고)[1]과 포함한다.최후의.n > 2에 대한 주기 그룹 ℤ_n.π이 주기적인 그룹인 경우, 전압 그래프를 주기 전압 그래프라고 할 수 있다.

정의

특정 그룹 π에 대한 π 전압 그래프의 공식 정의:

• digraph G. (방향은 오로지 표기법상의 편의를 위한 것이다.)
• G 호의 π 전압은 π의 원소 x에 의한 호 라벨이다.예를 들어, π = ℤ인_n 경우, 라벨은 숫자 i(mod n)이다.
• π-전압 할당은 G의 각 ${\displaystyle 호}$에${\displaystyle }$α : E${\displaystyle }$( ${\displaystyle G}$ ${\displaystyle )}$ → $[\displaystyle$ \alpha $:E(G)\오른쪽$ 화살표 $\Pi }$ 함수다${\displaystyle .}$
• π 전압 그래프는 한 쌍${\displaystyle (G}$ , ${\displaystyle \alpha }$ ${\displaystyle :}$E${\displaystyle }$( ${\displaystyle \mathrm{G}}$) → ${\displaystyle )}$ ) ${\displaystyle (G,\alpha :E(G)\오른쪽$ 화살표 $\Pi$)이므로$$ G는 디그라프, α는 전압 할당이다.
• 전압 그래프의 전압 그룹$({\displaystyle G}$, ${\displaystyle \alpha }$: E${\displaystyle }$( G${\displaystyle }$)${\displaystyle }$→ ${\displaystyle \mathrm{\pi }}$) ${\displaystyle (G,\알파 :E(G)\오른쪽$ 화살표 $\Pi$)은$$ 전압이 할당되는 그룹 π이다.

전압 그래프의 전압은 Kirchhoff의 전압 법칙을 만족시킬 필요가 없다는 점에 유의하십시오. 이 법칙은 아래에 설명된 파생 그래프에 대해 유효하지만 폐쇄 경로 주변의 전압 합계는 0(집단의 ID 요소)이다.따라서, 그 이름은 다소 오해의 소지가 있을 수 있다.위상학적 그래프 이론의 현재 그래프에 이중적인 전압 그래프의 기원에서 비롯된다.

파생 그래프

The derived graph of a voltage graph ${\displaystyle (G,\alpha :E(G)\rightarrow \mathbb {Z} _{n})}$ is the graph ${\displaystyle {\tilde {G}}}$ whose vertex set is ${\displaystyle {\tilde {V}}=V\times \mathbb {Z} _{n}}$ and whose edge set is ${\displaystyle \tilde{E}=E\times {}_{}}$${\displaystyle {\tilde {E}}=E\times \mathbb {Z} _{n}}$, where the endpoints of an edge (e, k) such that e has tail v and head w are ${\displaystyle (v,\ k)}$ and ${\displaystyle (w,\ k+\alpha (e))}$.

전압 그래프는 디그라프에 대해 정의되지만, 각 비방향 가장자리를 반대로 순서가 정해진 가장자리 쌍으로 교체하고 이러한 가장자리들이 그룹 구조에서 서로 반비례하는 라벨을 갖도록 요구함으로써 비방향 그래프까지 확장될 수 있다.이 경우, 파생된 그래프는 지시된 가장자리가 반대 방향의 가장자리 쌍을 형성하는 속성도 갖게 되므로 파생된 그래프 자체는 비방향 그래프로 해석될 수 있다.

파생된 그래프는 주어진 전압 그래프의 커버 그래프다.전압 그래프의 엣지 라벨이 ID 요소인 경우, 파생 그래프의 정점과 관련된 그룹 요소는 그룹 순서와 동일한 수의 색상으로 파생 그래프의 색상을 제공한다.중요한 특별한 경우는 2-요소 그룹의 비식별 요소로 모든 가장자리가 라벨로 표시된 전압 그래프의 파생 그래프인 초당적 이중 커버다.집단의 순서가 2이기 때문에 이 경우 파생된 그래프는 초당적으로 보장된다.

다항 시간 알고리즘은 $Z{\displaystyle {\mathbb{}}^{}}$ ${\displaystyle {}^{}}$ ${\$ -전압$$ 그래프의 파생 그래프에 지시된 사이클이 포함되어 있는지 여부를 결정하는 데 알려져 있다.^[1]

예

일정한 γ의 발전기를 가진 그룹 π의 모든 케이리 그래프는 하나의 꼭지점과 γ 자체 루프를 갖는 π 전압 그래프의 파생 그래프로 정의될 수 있으며, 각각 γ의 발전기 중 하나로 라벨을 붙일 수 있다.^[2]

피터슨 그래프는 두 정점을 연결하는 하나의 에지와 각 정점에 있는 하나의 자기 루프라는 두 개의 정점과 세 개의 가장자리가 있는 아령 모양의 voltage₅ 전압 그래프를 위한 파생 그래프다.한 개의 자체 루프에는 1이, 다른 하나는 2가, 두 개의 꼭지점을 연결하는 가장자리에는 0이 표시된다.보다 일반적으로, 동일한 구성을 통해 모든 일반화된 피터슨 그래프 GP(n,k)를 그룹 ℤ에서_n 라벨 1, 0 및 k가 있는 동일한 아령 그래프의 파생 그래프로 구성할 수 있다.^[3]

평면의 주기적인 다듬기의 정점과 가장자리는 전압이 voltages인² 유한 그래프의 파생 그래프로 형성될 수 있다.

메모들

참조

• Cohen, Edith; Megiddo, Nimrod (1989), "Strongly polynomial-time and NC algorithms for detecting cycles in dynamic graphs", Proc. 21st Annual ACM Symposium on Theory of Computing (STOC '89), pp. 523–534, doi:10.1145/73007.73057.
• Gross, Jonathan L. (1974), "Voltage graphs", Discrete Mathematics, 9 (3): 239–246, doi:10.1016/0012-365X(74)90006-5.
• Gross, Jonathan L.; Tucker, Thomas W. (1977), "Generating all graph coverings by permutation voltage assignments", Discrete Mathematics, 18 (3): 273–283, doi:10.1016/0012-365X(77)90131-5.
• Gross, Jonathan L.; Tucker, Thomas W. (1987), Topological Graph Theory, New York: Wiley.
• Iwano, K.; Steiglitz, K. (1987), "Testing for cycles in infinite graphs with periodic structure", Proc. 19th Annual ACM Symposium on Theory of Computing (STOC '87), pp. 46–55, doi:10.1145/28395.28401.
• Kosaraju, S. Rao; Sullivan, Gregory (1988), "Detecting cycles in dynamic graphs in polynomial time", Proc. 20th Annual ACM Symposium on Theory of Computing (STOC '88), pp. 398–406, doi:10.1145/62212.62251.