무영역 흐름

그래프 이론에서, 0이 없는 흐름 또는 NZ 흐름은 0이 없는 네트워크 흐름이다.평면 그래프를 색칠하는 것과 (이중성에 의해) 밀접하게 연결되어 있다.

정의들

G = (V,E)를 디그그래프로 하고 M을 아벨로니아 집단으로 한다.지도 φ: E → M은 모든 꼭지점 v ∈ V에 대해 M 순환이다.

\sum _{e\in \i1}{+}(v)}\phi(e)=\sum _{e\in \i1}{-}(v)\phi(e),

여기서 Δ⁺(v)는 v 중 가장자리 집합을 나타내며 Δ⁻(v)는 가장자리 집합을 v로 나타내기도 한다. 때로는 이 조건을 Kirchhoff의 법칙이라고 한다.

e ∈ E마다 φ(e) ≠ 0이 되면 φ은 아무데도 없는 흐름, M-flow, NZ-flow라고 부른다.k가 정수이고 0 < φ(e) > k이면 φ은 k-흐름이다.^[1]

기타 개념

G = (V,E)를 방향하지 않은 그래프로 두십시오.E의 방향은 우리가 가진 모든 꼭지점 v ∈ V에 대해 다음과 같은 경우 모듈형 k-흐름이다.

\cHB \property ^{+}(v) \equiv \ique ^{-}(v) {\bmod {k}}.

특성.

하나의 가장자리에 있는 두 흐름의 합이 0에 더해질 수 있기 때문에 M-흐름 집합이 반드시 그룹을 형성하는 것은 아니다.

(Tutte 1950) 그래프 G는 M - flow가 있는 경우에만 M-flow가 있다.그 결과, k-flow가 존재하는 경우에만 $\mathbb {Z} _{k}$ $\mathbb {Z} _{k}$ ${\$ 흐름이 $\mathbb {Z} _{k}$ 존재한다.^[1]결과적으로 G가 k-flow를 인정하면 $h\geq k$ 를 인정하는데 h $h\geq k$ k ${\displaysty h\geq k$

방향 독립.엣지 e를 선택하고 반전시킨 다음 φ(e)를 - -(e)로 교체하여 그래프 G에서 0이 없는 흐름 φ을 수정한다.이 조정 후에도 φ은 여전히 무(無)의 흐름이다.나아가 φ이 원래 k-흐름이었다면, 그 결과 φ도 역시 k-흐름이다.따라서 0이 없는 M-흐름이나 0이 없는 k-흐름의 존재는 그래프의 방향과 무관하다.따라서 G의 일부(따라서 모든) 방향의 흐름이 있는 경우 방향 그래프 G는 0이 아닌 M-흐름 또는 0이 아닌 k-흐름이라고 한다.

흐름 다항식

$N_{M}(G)$ $N_{M}(G)$ ( $N_{M}(G)$ ) $N_{M}(G)$ 을(를) G의 M-flow 수가 되게 $N_{M}(G)$ 한다.삭제-축소 공식을 만족한다.^[1]

N_{M}(G)=N_{M}(G/e)-N_{M}(G\setminus e).

이것을 유도와 결합하면 $N_{M}(G)$ $N_{M}(G)$ ( $N_{M}(G)$ ) $N_{M}(G)$ 은 $N_{M}(G)$ (는 $)$ $|M|-1$ - $|M|-1$ 의 다항식이고, $|M|$ $displaystyle$ M $}$ 은 $|M|$ (는) 그룹 M의 순서임을 알 수 있다. $N_{M}(G)$ 는 N $N_{M}(G)$ M ( $N_{M}(G)$ ) $N_{M}(G)$ 을 $N_{M}(G)$ (를) G와 아벨 그룹 M의 흐름 다항식이라고 부른다.

위의 내용은 동일한 순서의 두 그룹이 동일한 NZ 흐름을 가지고 있음을 의미한다.순서는 M의 구조가 아니라 유일하게 중요한 그룹 파라미터다.특히 $N_{M_{1}}(G)=N_{M_{2}}(G)$ $N_{M_{1}}(G)=N_{M_{2}}(G)$ $N_{M_{1}}(G)=N_{M_{2}}(G)$ ( $N_{M_{1}}(G)=N_{M_{2}}(G)$ ) $N_{M_{1}}(G)=N_{M_{2}}(G)$ = $N_{M_{1}}(G)=N_{M_{2}}(G)$ $N_{M_{1}}(G)=N_{M_{2}}(G)$ 2 $N_{M_{1}}(G)=N_{M_{2}}(G)$ ( $N_{M_{1}}(G)=N_{M_{2}}(G)$ ) ${\displaystyle N_{M_{1}:{$ 1}( $G)=$ $|M_{1}|=|M_{2}|.$ 1 = M 2 . $displaystyle M_{1}$ = $M_{2} .}$ 인 $N_{M_{1}}(G)=N_{M_{2}}(G)$ 경우 $N_{M_{2$ }}( $G)}$

위의 결과는 1953년 투테가 플로우 다항식의 일반화인 투테 다항식을 연구하고 있을 때 증명되었다.^[2]

플로우컬러 이중성

브리지리스 평면 그래프

브리지리스 평면 그래프의 경우 k-face 컬러링과 k-flow 사이에는 이중성이 있다.이를 보려면 G를 컬러 $\{0,1,\ldots ,k-1\}.$ { $\{0,1,\ldots ,k-1\}.$ 1, $\{0,1,\ldots ,k-1\}.$ $\{0,1,\ldots ,k-1\}.$ - $\{0,1,\ldots ,k-1\}.$ 을(를) 포함하는 적절한 k-face-coloring이 있는 브리지리스 평면 그래프로 설정. $\{0,1,\ldots,k-1}$ 지도 구성 $\{0,1,\ldots ,k-1\}.$

\phi :E(G)\to \{-(k-1)]\ldots ,-1,0,1,\ldots,k-1\

다음 규칙에 의해: 가장자리 e의 면은 왼쪽에 x 색이고, 가장자리 y의 면은 오른쪽에 있는 경우, φ(e) = x – y 색으로 한다.그러면 x와 y는 서로 다른 색이어야 하므로 φ은 (NZ) k-flow이다.

따라서 G와 G*가 평면 이중 그래프이고 G*가 k-컬러블(G의 얼굴 색상이 있음)이라면 G는 NZ k-flow를 가진다.E(G) Tutte에 유도를 사용함으로써 그 반대의 경우도 사실임을 증명했다.이것은 다음과 같이 간결하게 표현할 수 있다.^[1]

\displaystyle \chi(G^{*})=\phi(G),}

여기서 RHS는 흐름 번호로 G가 k 흐름을 허용하는 가장 작은 k이다.

일반 그래프

이중성은 일반 M-흐름에도 적용된다.

$c$ $c$ 값을 $c$ M으로 하여 얼굴 색상이 되도록 한다.

$\phi _{c}(e)=c(r_{1})-c(r_{2})$ $\phi _{c}(e)=c(r_{1})-c(r_{2})$ ( $\phi _{c}(e)=c(r_{1})-c(r_{2})$ ) $\phi _{c}(e)=c(r_{1})-c(r_{2})$ = c $\phi _{c}(e)=c(r_{1})-c(r_{2})$ ( r $\phi _{c}(e)=c(r_{1})-c(r_{2})$ ) $\phi _{c}(e)=c(r_{1})-c(r_{2})$ - $\phi _{c}(e)=c(r_{1})-c(r_{2})$ ( $\phi _{c}(e)=c(r_{1})-c(r_{2})$ $\phi _{c}(e)=c(r_{1})-c(r_{2})$ ) ${\displaystyle \phi _{c}(e)=c(r_{1})-c(r_{2})$ 를 정의하십시오. 여기서 $\phi _{c}(e)=c(r_{1})-c(r_{2})$ r은₁ e의 왼쪽 면이고 r은₂ 오른쪽 면입니다.

모든 M-circulation $\phi$ $\phi$ 에 대해 $\phi =\phi _{c}$ = $\phi =\phi _{c}$ c ${\$ 유도에 의해 증명됨)와 같은 색소함수 c가 있다 $\phi$ .

c는 $\phi _{c}$ $\phi _{c}$ ${\$ 가 $\phi _{c}$ NZ M-flow(직진)인 경우에만 E(G) -face-coloring이다.

이중성은 마지막 두 점을 조합하여 그 뒤를 잇는다.위에서 논의한 k-흐름에 대해서도 비슷한 결과를 얻기 위해 $M=\mathbb {Z} _{k}$ $M=\mathbb {Z} _{k}$ = $M=\mathbb {Z} _{k}$ $M=\mathbb {Z} _{k}$ ${\$ 로 전문화할 수 있다.NZ 흐름과 색상 사이의 이러한 이중성을 고려할 때, 그리고 임의 그래프(평면뿐만 아니라)에 대한 NZ 흐름을 정의할 수 있기 때문에, 우리는 이것을 사용하여 얼굴 색상을 비 평면 그래프로 확장할 수 있다.^[1]

적용들

G는 모든 꼭지점에 고른 정도가 있는 경우에만 2-얼굴 색상이 가능하다(NZ 2-흐름 고려).^[1]

$K=\mathbb {Z} _{2}\times \mathbb {Z} _{2}$ = $K=\mathbb {Z} _{2}\times \mathbb {Z} _{2}$ $K=\mathbb {Z} _{2}\times \mathbb {Z} _{2}$ $K=\mathbb {Z} _{2}\times \mathbb {Z} _{2}$ Z $K=\mathbb {Z} _{2}\times \mathbb {Z} _{2}$ ${\$ K $=\mathb {Z} _{$ 2}\ $time\$ mathb ${Z} _{$ 2}}번 클라인-4 그룹이 $K=\mathbb {Z} _{2}\times \mathbb {Z} _{2}$ 되게 $한다$ .입방형 그래프는 3-엣지 색상이 가능한 경우에만 K-flow가 된다.3-엣지 색상이 가능한 큐빅 그래프는 4-페이스 색상이 가능하다.^[1]

그래프는 NZ 4-flow를 허용하는 경우에만 4-face 색상이 가능하다(Four color organization 참조).Petersen 그래프는 NZ 4-flow가 없으며, 이는 4-flow 추측으로 이어졌다(아래 참조).

G가 삼각측량인 경우 G는 모든 꼭지점에 균등도가 있는 경우에만 3-(베르텍스) 색상이 가능하다.첫 번째 탄환에 의해, 듀얼 그래프 G*는 2가지 색상이 가능하여, 양분 및 평면 입방형이다.그래서 G*는 NZ 3-flow를 가지고 있으며, 따라서 3-face 색상이 가능하여 G 3-vertex 색상이 가능하다.^[1]

루프 가장자리가 있는 어떤 그래프도 적절한 정점 색상을 가지지 않듯이, 브리지가 있는 그래프는 어떤 그룹 M에 대해서도 NZ M-flow를 가질 수 없다.반대로 모든 브리지리스 그래프에는 NZ $\mathbb {Z}$ ${\$ -flow $\mathbb {Z}$ (로빈스의 정리)가 있다.^[3]

k-흐름의 존재

수학의 미해결 문제:

모든 무교량 그래프에 0-5 흐름이 있는가?Petersen 그래프를 마이너 그래프로 가지고 있지 않은 모든 브리지리스 그래프에는 0이 없는 4-흐름이 있는가?

(수학에서 더 풀리지 않은 문제)

k의 작은 값에 대한 0도 없는 k-flow를 찾으려 할 때 흥미로운 질문이 발생한다.다음과 같은 사실이 입증되었다.

재거의 4-흐름 정리.모든 4개의 가장자리가 연결된 그래프에는 4개의 흐름이 있다.^[4]

시모어의 6-흐름 정리.모든 무교량 그래프에는 6-흐름이 있다.^[5]

3-흐름, 4-흐름, 5-흐름 추정

2019년 현재 (투테로 인해) 미해결 상태인 것은 다음과 같다.

3-흐름 추측.모든 4개의 가장자리로 연결된 그래프에는 0이 없는 3-흐름이 있다.^[6]

4-흐름 추측.피터슨 그래프를 마이너로 하지 않은 모든 브리지리스 그래프에는 0이 없는 4-흐름이 있다.^[7]

5-흐름 추측.모든 무교량 그래프에는 0이 없는 5-흐름이 있다.^[8]

전체 그래프 K에₁₁ 피터슨 그래프와 4-플로우가 포함되어 있기 때문에 4-플로우 추측의 역은 유지되지 않는다.^[1]Petersen 마이너가 없는 브리지리스 입방형 그래프의 경우 스나크 정리(Seymour, et al 1998, 아직 발표되지 않음)에 의해 4-흐름이 존재한다.네 가지 색의 정리는 스나크가 없다는 말과 같다.^[1]

참고 항목

참조

^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j Diestel, Reinhard, 1959- Verfasser. (30 June 2017). Graph theory. ISBN 9783662536216. OCLC 1048203362. {{cite book}}: last=일반 이름 포함(도움말)CS1 maint: 여러 이름: 작성자 목록(링크)
^ Tutte, William Thomas (1953). "A contribution to the theory of chromatic polynomials". {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)
^ Z{\displaystyle \mathbb{Z}의 열거형}에 더 강력한 결과에 대해서는 가장자리의 최대 유량 양에, 다시 완전히 순환 방향에, 정리 2Kochol의, 마틴(2002년),"Polynomials nowhere-zero로 흐르관련된"면 필기장이 Combinatorial이론, 시리즈 B84(2):260–269를 참조하십시오 로빈스의 정리를 사용하여 마련과 -flows., doi:10.1006/jctb.2001.2081, MR1889258
^ F. 재거, 플로우 및 일반화된 색채 정리 그래프, J. 콤.이론 집합. B, 26 (1979), 205–216.
^ P. D. 시모어, Nowhere-zero 6-flows, J. Comb.이론 Ser B, 30 (1981), 130–135.
^ [1], 문제 정원 열기
^ [2], 문제 정원 열기.
^ [3], 문제 정원 열기.

추가 읽기

Zhang, Cun-Quan (1997). Integer Flows and Cycle Covers of Graphs. Chapman & Hall/CRC Pure and Applied Mathematics Series. Marcel Dekker, Inc. ISBN 9780824797904. LCCN 96037152.
Zhang, Cun-Quan (2012). Circuit Double Cover of Graphs. Cambridge University Press. ISBN 978-0-5212-8235-2.
Jensen, T. R.; Toft, B. (1995). "13 Orientations and Flows". Graph Coloring Problems. Wiley-Interscience Serires in Discrete Mathematics and Optimization. pp. 209–219.
Jacobsen, Jesper Lykke; Salas, Jesús (2013). "Is the five-flow conjecture almost false?". Journal of Combinatorial Theory. Series B. 103 (4): 532–565. arXiv:1009.4062. doi:10.1016/j.jctb.2013.06.001. MR 3071381.

[:0-1] ^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j Diestel, Reinhard, 1959- Verfasser. (30 June 2017). Graph theory. ISBN 9783662536216. OCLC 1048203362. {{cite book}}: last=일반 이름 포함(도움말)CS1 maint: 여러 이름: 작성자 목록(링크)

[2] Tutte, William Thomas (1953). "A contribution to the theory of chromatic polynomials". {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)

[3] Z{\displaystyle \mathbb{Z}의 열거형}에 더 강력한 결과에 대해서는 가장자리의 최대 유량 양에, 다시 완전히 순환 방향에, 정리 2Kochol의, 마틴(2002년),"Polynomials nowhere-zero로 흐르관련된"면 필기장이 Combinatorial이론, 시리즈 B84(2):260–269를 참조하십시오 로빈스의 정리를 사용하여 마련과 -flows., doi:10.1006/jctb.2001.2081, MR1889258

[4] F. 재거, 플로우 및 일반화된 색채 정리 그래프, J. 콤.이론 집합. B, 26 (1979), 205–216.

[5] P. D. 시모어, Nowhere-zero 6-flows, J. Comb.이론 Ser B, 30 (1981), 130–135.

[6] [1], 문제 정원 열기

[7] [2], 문제 정원 열기.

[8] [3], 문제 정원 열기.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

Search