종료(그래프 이론)

무한 그래프의 수학에서, 그래프의 끝은 직관적으로 그래프가 무한대로 확장되는 방향을 나타낸다.끝은 수학적으로 무한 경로의 동등성 등급으로, 추적-에 대한 전략을 그래프에 기술하는 안식처로, 또는 (국소적으로 유한한 그래프의 경우) 그래프와 연관된 위상학적 공간의 위상학적 끝으로 공식화할 수 있다.

정밀하게 생성된 그룹의 끝을 정의하기 위해 (Cayley 그래프를 통해) 그래프의 끝을 사용할 수 있다.미세하게 생성된 무한집단은 끝이 하나, 둘 또는 무한히 많으며, 집단의 끝에 대한 스털링스 정리는 한 쪽 이상의 끝을 가진 집단에 대해 분해를 제공한다.

정의 및 특성화

그래프의 끝은 무한경로의 동등성 등급 측면에서 루돌프 할린(1964)이 정의했다.^[1]A.mw-parser-output .vanchor&gt은 무한 그래프에서 target~.vanchor-text{background-color:#b1d2ff}ray은semi-infinite 단순 경로, vertices의, 그것은 무한 수열 v0, v1, v,...각각의 꼭지점 가장 한번에 시퀀스에그램의 가장자리에서 순서대로 각 2년 연속 vertices 있는 두 끝점으로 보인다.aph.할린의 정의에 따르면, 두 개의 광선 r과₀ r은₁ 각 r과₀ r에₁ 있는 정점의 무한히 많은 정점을 포함하는 다른 광선₂ r(첫 번째 두 광선 중 하나와 반드시 다를 필요는 없음)이 있으면 동등하다.이것은 등가관계다: 각 광선은 그 자체와 동등하고, 정의는 두 광선의 순서와 관련하여 대칭적이며, 타성으로 보일 수 있다.따라서 모든 광선 세트를 동등성 등급으로 분할하고, 할린은 이러한 동등성 등급 중 하나로 끝을 정의한다.

동일한 동등성 관계에 대한 대안적 정의도 사용되었다.^[2] 두 개의 광선 r과₀ r은₁ r의₀₁ 정점수에서 무한히 많은 정점을 분리하는 정점의 유한한 집합 X가 없다면 동등하다.이것은 할린의 정의와 동등하다. 할린의 정의에서 나온 r선₂ r이 존재한다면, 어떤 분리막도 r의₂ 무한히 많은 점을 포함해야 하므로 유한할 수 없으며, 반대로 r이₂ 존재하지 않는다면 r과₀ r 사이에₁ 가능한 한 많은 시간을 교대로 하는 경로가 원하는 유한 분리막을 형성해야 한다.

또한 엔드들은 추격-에피션 게임을 위한 회피 전략을 그래프 G에 기술하는 기능인 안식처 측면에서 보다 구체적인 특성을 가지고 있다.^[3]문제의 게임에서, 한 강도가 G의 가장자리를 따라 꼭지점에서 꼭지점으로 이동하여 일련의 경찰들을 피하려 하고 있다.경찰은 헬리콥터를 가지고 있기 때문에 가장자리를 따라갈 필요가 없다. 그러나 강도는 경찰이 오는 것을 볼 수 있고 헬리콥터가 착륙하기 전에 다음 장소를 선택할 수 있다.안식처는 경찰 위치의 각 세트 X를 X를 삭제하여 형성된 서브그래프의 연결된 구성 요소 중 하나에 매핑하는 기능 β이다. 강도는 게임의 각 라운드에 이 구성 요소 내의 꼭지점으로 이동하여 경찰을 피할 수 있다.Havense는 일관성 특성을 만족시켜야 한다(강도는 경찰이 이미 착륙한 정점을 통과할 수 없다는 요건에 대응함). X가 Y의 하위 집합이고 X와 Y 모두 주어진 경찰 세트의 유효한 위치 집합이라면, β(X)는 β(Y)의 상위 집합이어야 한다.한 피난처 있기 위해 k만약 경찰의 위치에 탈출 전략을 제공하는 컬렉션 그 그래프에서 kvertices보다 적은 모든 하위 집합을 포함하며, vertices의 매핑 됩니다 모든 유한 부분 집합 X이 특히 G의 구성 요소에)XG의 모든 광선 주문 ℵ0에게 안식처에 해당하는 경우 즉, 그 기능마다 그 매핑 됩니다 β 위해 ℵ0다. finite는 X를 무한히 많은 광선의 정점을 포함하는 G \ X의 고유한 구성요소로 설정한다.반대로 모든 안식처 ℵ은₀ 광선에 의해 이런 식으로 정의될 수 있다.^[4]두 개의 광선은 동일한 안식처를 정의하는 경우에만 동등하므로, 그래프의 끝은 질서의 안식처와 일대일 일치한다₀.

예

만약 무한 그래프 G가 그 자체로 광선이라면, 그것은 G의 각 꼭지점에서 시작하는 한 개의 광선 서브그래프를 무한히 많이 가지고 있다.그러나 이 모든 광선은 서로 동등하기 때문에 G는 한쪽 끝만 가지고 있다.

G가 숲(즉, 유한한 주기가 없는 그래프)인 경우, 어떤 두 개의 광선의 교차점은 경로 또는 광선이다. 두 개의 광선은 그들의 교차점이 광선이라면 동등하다.G의 각 연결된 구성 요소에서 기저 정점을 선택한 경우, G의 각 끝은 기준 정점 중 하나에서 시작하는 고유한 광선을 포함하므로, 끝은 이 표준선과 일대일 대응으로 배치될 수 있다.모든 계수 가능한 그래프 G에는 G와 같은 끝 집합을 가진 스패닝 포리스트가 있다.^[5]그러나, 모든 스패닝 트리의 끝이 무한히 많은 한 쪽 끝만을 가진 무한 그래프들이 존재한다.^[6]

만약 G가 무한 그리드 그래프라면, 그것은 많은 광선을 가지고 있고 임의로 큰 정점 분리 광선을 가지고 있다.그러나 끝은 하나뿐이다.이는 피신처의 관점에서 끝의 특성화를 가장 쉽게 이용할 수 있다: 어떤 한정된 정점 집합의 제거는 정확히 하나의 무한 연결 구성요소를 남기 때문에 하나의 안식처(각 유한 집합을 고유한 무한 연결 구성요소에 매핑하는 것)만 존재한다.

위상학적 목적과의 관계

점 집합 위상에는 그래프 이론의 끝 개념과 유사하지만 상당히 같지는 않은 끝의 개념이 있는데, 이는 프로이덴탈(1931년)에 훨씬 앞서 거슬러 올라간다.If a topological space can be covered by a nested sequence of compact sets ${\displaystyle \kappa _{0}\subset \kappa _{1}\subset \kappa _{2}\dots }$, then an end of the space is a sequence of components ${\displaystyle U_{0}\supset U_{1}\supset U_{2}\dots }$ of the complements콤팩트 세트의이 정의는 콤팩트 세트의 선택에 의존하지 않는다. 그러한 선택으로 정의되는 끝은 다른 선택으로 정의되는 끝과 일대일 일치로 배치될 수 있다.

무한 그래프 G는 서로 다르지만 관련된 두 가지 방법으로 위상학적 공간으로 만들어질 수 있다.

• 그래프의 각 꼭지점을 한 점으로, 그리고 열린 단위 구간으로 그래프의 각 가장자리를 교체하면 그래프의 가장자리와 S의 각 교차점이 단위 구간의 열린 부분 집합이 될 때마다 세트 S가 열리도록 정의되는 그래프에서 하우스도르프 공간이 발생한다.
• 그래프의 각 꼭지점을 점으로 교체하고 그래프의 각 가장자리를 점으로 교체하면 Hausdorff 공간이 아닌 공간이 생성되며, 여기서 열린 집합은 속성이 S이고, 정점 v가 S에 속하면 모든 가장자리가 그 끝점 중 하나로 v를 갖는 속성이다.

어느 경우든 G의 모든 유한 서브그래프는 위상학적 공간의 컴팩트 서브스페이스에 해당하며, 모든 소형 서브스페이스는 하우스도르프 사례에서 최종적으로는 많은 소형 적절한 서브셋과 함께 유한 서브그래프에 해당한다.따라서 그래프는 모든 꼭지점에서 한정된 수의 가장자리를 갖는 국소적으로 유한한 경우에만 콤팩트 세트의 내포된 시퀀스로 덮을 수 있다.

그래프 G가 연결되고 국소적으로 유한하다면, 그것은 콤팩트 커버를 가지고 있는데, 세트 κ은_i 임의로 선택한 시작 꼭지점에서 최대 i의 거리에 있는 정점 집합이다.In this case any haven β defines an end of the topological space in which ${\displaystyle U_{i}=\beta (\kappa _{i})}$. And conversely, if ${\displaystyle U_{0}\supset U_{1}\supset U_{2}\dots }$ is an end of the topological space defined from G, it defines a haven in which β(X) is thU를_i 포함한 e 성분, 여기서 i는 X를_i 포함할 정도로 충분히 큰 숫자다.따라서 연결된 그래프와 국소적으로 유한한 그래프의 경우 위상학적 끝은 그래프-이론적 끝과 일대일 일치한다.^[7]

국소적으로 유한하지 않을 수 있는 그래프의 경우, 그래프와 그 끝에서 위상학적 공간을 정의할 수 있다.이 공간은 그래프가 정규 스패닝 트리를 가지고 있는 경우에만 메트릭 공간으로 나타낼 수 있으며, 각 그래프 가장자리가 상위-하위 쌍을 연결하는 루트 스패닝 트리가 있다.일반 스패닝 트리가 존재할 경우, 주어진 그래프와 동일한 끝 집합을 가진다. 즉, 그래프의 각 끝에는 트리에서 하나의 무한 경로가 정확히 포함되어야 한다.^[8]

특별한 종말의 종류

자유 끝

그래프 G의 끝 E는 X가 그래프의 다른 모든 끝에서 E를 분리하는 속성을 가진 정점 X의 유한 집합 X가 있으면 자유 끝이라고 정의된다. (즉, 안식처 측면에서, β_E(X)는 다른 끝 D의 모든 끝에서 β_D(X)와 분리된다.) 끝이 미세하게 많은 그래프에서 모든 끝은 자유 끝이어야 한다.할린(1964)은 G가 끝이 무한히 많으면 자유롭지 못한 끝이 존재하거나, 또는 광선의 무한 계열이 존재하여 공통의 시작 정점을 공유하고 그렇지 않으면 서로 분리된다는 것을 증명한다.

두꺼운 끝

그래프 G의 두꺼운 끝은 한 쌍으로 분리된 광선을 무한히 많이 포함하는 끝이다.할린의 그리드 정리는 두꺼운 끝을 포함하는 그래프를 특징으로 한다: 그것들은 정확히 6각형 타일링을 서브그래프로 나눈 그래프들이다.^[9]

특별한 종류의 그래프

대칭 및 거의 대칭 그래프

Mohar(1991)는 정점 v와 숫자 D가 있을 경우 "거의 대칭"으로 정의하여 다른 모든 정점 w에 대해, v의 이미지가 w의 거리 D 내에 있는 그래프의 자동화가 존재하며, 동등하게, 연결된 국소 유한 그래프는 그 자동성 그룹이 유한하면 거의 대칭이다.많은 궤도를 돌다그가 보여주듯이, 국소적으로 유한한 거의 대칭 그래프의 경우, 끝의 수는 최대 두 개 또는 셀 수 없는 것이다. 만약 이 그래프를 계산할 수 없다면 끝은 칸토어의 토폴로지를 설정한다.또한, Mohar는 끝의 수가 체거 상수를 제어한다는 것을 보여준다.

${\displaystyle h=\inf \left\{\frac {\partial V}{{{}{{partial V}}{V}}}}}{{{}}}}}}$

여기서 V는 그래프의 모든 한정된 비빈 정점 집합에 걸쳐 있으며 여기서${\displaystyle \mathrm{}}$where ${\displaystyle V}$ ${\displaystyle \partial V}$은 V에 있는 하나의 끝점이 있는 가장자리 집합을 나타낸다.끝이 셀 수 없이 많은 거의 대칭 그래프의 경우 h > 0이지만, 두 끝만 있는 거의 대칭 그래프의 경우 h = 0.

케이리 그래프

그룹의 모든 그룹과 발전기 집합은 Cayley 그래프를 결정한다. 이 그래프는 정점이 그룹 요소이고 가장자리가 원소 쌍(x,gx)이며 g는 생성기 중 하나이다.정밀하게 생성된 집단의 경우, 집단의 끝은 유한한 발전기 집합에 대한 Cayley 그래프의 끝이라고 정의된다. 이 정의는 두 개의 서로 다른 유한한 발전기 집합을 선택하면 두 개의 Cayley 그래프의 끝이 일대일 대응 위트에 있다는 점에서 발전기의 선택에 따라 불변한다.서로 h를 나누다

예를 들어, 모든 자유 그룹에는 트리인 Cayley 그래프가 있다.한 발전기의 자유 그룹은 그것의 Cayley 그래프처럼 두 배로 무한의 경로를 가지고 있고, 두 개의 끝을 가지고 있다.다른 모든 자유 그룹은 끝이 무한히 많다.

미세하게 생성된 모든 무한집단은 1, 2 또는 무한히 많은 끝을 가지고 있으며, 집단의 끝에 대한 스털링스 정리는 한 개 이상의 끝을 가진 집단의 분해를 제공한다.^[10]특히:

1. 정밀하게 생성된 무한집단은 유한지수의 주기적 하위집단을 갖는 경우에만 2개의 끝이 있다.
2. 미세하게 생성된 무한집단은 합병을 포함한 비경쟁적 자유상품 또는 유한한 합병을 가진 HNN-확장 제품일 경우에만 끝이 무한히 많다.
3. 다른 모든 미세하게 생성된 무한 집단은 정확히 하나의 끝을 가지고 있다.

메모들

참조

• Diestel, Reinhard (1992), "The end structure of a graph: recent results and open problems", Discrete Mathematics, 100 (1–3): 313–327, doi:10.1016/0012-365X(92)90650-5, MR 1172358.
• Diestel, Reinhard (2004), "A short proof of Halin's grid theorem", Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 74: 237–242, doi:10.1007/BF02941538, MR 2112834.
• Diestel, Reinhard (2006), "End spaces and spanning trees", Journal of Combinatorial Theory, Series B, 96 (6): 846–854, doi:10.1016/j.jctb.2006.02.010, MR 2274079.
• Diestel, Reinhard; Kühn, Daniela (2003), "Graph-theoretical versus topological ends of graphs", Journal of Combinatorial Theory, Series B, 87 (1): 197–206, doi:10.1016/S0095-8956(02)00034-5, MR 1967888.
• Freudenthal, Hans (1931), "Über die Enden topologischer Räume und Gruppen", Mathematische Zeitschrift, 33: 692–713, doi:10.1007/BF01174375.
• Freudenthal, Hans (1945), "Über die Enden diskreter Räume und Gruppen", Commentarii Mathematici Helvetici, 17: 1–38, doi:10.1007/bf02566233, MR 0012214.
• Halin, Rudolf (1964), "Über unendliche Wege in Graphen", Mathematische Annalen, 157 (2): 125–137, doi:10.1007/bf01362670, hdl:10338.dmlcz/102294, MR 0170340.
• Halin, Rudolf (1965), "Über die Maximalzahl fremder unendlicher Wege in Graphen", Mathematische Nachrichten, 30 (1–2): 63–85, doi:10.1002/mana.19650300106, MR 0190031.
• Krön, Bernhard; Möller, Rögnvaldur G. (2008), "Metric ends, fibers and automorphisms of graphs" (PDF), Mathematische Nachrichten, 281 (1): 62–74, doi:10.1002/mana.200510587, MR 2376468.
• Mohar, Bojan (1991), "Some relations between analytic and geometric properties of infinite graphs" (PDF), Discrete Mathematics, 95 (1–3): 193–219, doi:10.1016/0012-365X(91)90337-2, MR 1141939.
• Robertson, Neil; Seymour, Paul; Thomas, Robin (1991), "Excluding infinite minors", Discrete Mathematics, 95 (1–3): 303–319, doi:10.1016/0012-365X(91)90343-Z, MR 1141945.
• Seymour, Paul; Thomas, Robin (1991), "An end-faithful spanning tree counterexample", Proceedings of the American Mathematical Society, 113 (4): 1163–1171, doi:10.2307/2048796, JSTOR 2048796, MR 1045600.
• Stallings, John R. (1968), "On torsion-free groups with infinitely many ends", Annals of Mathematics, Second Series, 88 (2): 312–334, doi:10.2307/1970577, JSTOR 1970577, MR 0228573.
• Stallings, John R. (1971), Group theory and three-dimensional manifolds: A James K. Whittemore Lecture in Mathematics given at Yale University, 1969, Yale Mathematical Monographs, vol. 4, New Haven, Conn.: Yale University Press, MR 0415622.
• Thomassen, Carsten (1992), "Infinite connected graphs with no end-preserving spanning trees", Journal of Combinatorial Theory, Series B, 54 (2): 322–324, doi:10.1016/0095-8956(92)90059-7, hdl:10338.dmlcz/127625, MR 1152455.