사이클 스페이스

수학의 한 분야인 그래프 이론에서, 비방향 그래프의 (이진) 주기 공간은 그것의 짝수 서브그래프의 집합이다.

이 서브그래프 세트는 2요소 유한장 위의 벡터 공간으로서 대수적으로 설명할 수 있다.이 공간의 치수는 그래프의 회로 순위다.같은 공간은 그래프의 첫 번째 호몰로지 그룹과 같은 대수적 위상으로부터 용어로도 설명할 수 있다.호몰로지 이론을 사용하면 임의의 링 위에 공간을 순환하도록 이항 사이클 공간을 일반화할 수 있다.

정의들

그래프 이론

주어진 그래프 G의 스패닝 서브그래프는 G의 가장자리의 모든 부분 집합 S에서 정의될 수 있다.서브그래프는 G 자체와 정점 집합은 동일하지만(이것은 "spanning"이라는 단어의 의미) S의 원소를 가장자리로 한다.따라서, m 에지가 있는 그래프 G는 G 자체를 포함한 2개의^m 스패닝 서브그래프를 가지고 있고, G와 같은 정점 집합에 빈 그래프를 가지고 있다.그래프 G의 모든 스패닝 서브그래프의 집합은 G의 가장자리 공간을 형성한다.^[1][2]

그래프 G, 즉 그 서브그래프 중 하나는 각각의 정점에 입사 에지 수가 짝수인 경우(이 숫자를 정점의 정도라고 한다) 오일러라고 한다.이 속성은 1736년 쾨니히스베르크의 일곱 다리 관련 연구에서 연결된 그래프가 오일러인 경우에만 각 가장자리를 정확히 한 번 방문하는 투어를 가지고 있다는 것을 증명했던 레온하르트 오일러의 이름을 따서 명명되었다.그러나 오일러식 하위 그래프는 연결할 필요가 없다. 예를 들어, 모든 정점이 서로 분리되는 빈 그래프는 오일러식이다.그래프의 주기 공간은 오일러 스패닝 서브그래프의 모음입니다.^[1][2]

대수학

특정 그래프의 두 스패닝 서브그래프에 세트 조합 또는 교차점 등 설정된 작업을 적용하면 결과는 다시 서브그래프가 된다.이런 식으로 임의 그래프의 가장자리 공간은 부울대수로 해석할 수 있다.^[3]

사이클 공간 역시 대수학적 구조를 가지고 있지만, 보다 제한적인 구조를 가지고 있다.두 개의 오일러 서브그래프의 결합이나 교차점은 오일러식일 수 있다.그러나 두 개의 오일러 서브그래프(주어진 그래프 두 개 중 정확히 한 개에 속하는 가장자리로 구성된 그래프)의 대칭적 차이는 다시 오일러다.^[1]이는 원소수가 짝수인 두 세트의 대칭적 차이도 일정하다는 데서 비롯된다.이 사실을 각 꼭지점 부근에 별도로 적용하면 대칭 차이 연산자가 오일러로서의 특성을 보존하고 있음을 알 수 있다.

세트가 대칭 차. 운전에 따라서 닫힌 가족은 대수적으로 벡터 공간은two-element 한정된 밭에 묘사될 수 있Z2{\displaystyle \mathbb{Z}_{2}}.[4]이 현장의 분위기는 두가지 요소, 0과 1, 그리고 그것의 덧셈과 곱셈 작전이 될 수 있다 설명한 것처럼 친숙한 덧셈과 곱셈은 Ofintegers, take modulo 2.벡터 공간은 익숙한 실제 벡터 공간의 특성을 일반화하는 특정 특성을 만족하는 추가 및 스칼라 곱셈 연산과 함께 요소 집합으로 구성된다. 사이클 공간의 경우 벡터 공간의 요소는 오일러식 하위 그래프이며, 추가 연산은 대칭 차이점, 곱셈 b이다.y 스칼라 1은 아이덴티티 연산이고, 스칼라 0에 의한 곱셈은 모든 요소를 빈 그래프에 가져가고, 이것은 사이클 공간의 첨가된 아이덴티티 요소를 형성한다.

또한 에지 공간은 대칭 차이를 덧셈으로 사용할 경우$$ $Z{\displaystyle {\mathbb{}}_{}}$ ${\displaystyle {\mathrm{}}_{}}$ ${\$2}}에 걸친 벡터 공간이다.벡터 공간으로서, 그래프의 사이클 공간과 컷 공간(그래프의 컷에 걸쳐 있는 에지 집합의 패밀리)은 에지 공간 내에서 서로 직교 보완물이다.이 만일 모든 오일러 부분 그래프. 가장자리가 S{S\displaystyle}과 공통점이 짝수가 가장자리의 그래프에서 집합 S{S\displaystyle}, S{S\displaystyle}이론의 오일러 부분 그래프. 만일 때마다. 가장자리가 일반적인 S{S\displaystyle}과 짝숬다[2을 형성하고 인하를 이루고 있다는 것을 의미한다.]이 두 공간은 직교 보완 공간이지만, 일부 그래프에는 두 공간 모두에 속하는 비어 있지 않은 하위 그래프가 있다.이러한 하위 그래프(Ulerian $cut)$는 $G{\displaystyle }$ ${\$displaystyle G$}$이(가) 일정한 수의 스패닝 포리스트를 갖는$$ 경우에만$$ 그래프 $G{\displaystyle }$ ${\displaystyle G}$의 일부로 존재한다.^[5]

위상

비방향 그래프는 정점이 0차원 단순화로, 가장자리는 1차원 단순화로, 단순화 그래프는 단순화 복합체로 볼 수 있다.^[6]이 위상 공간의 체인 콤플렉스는 가장자리 공간과 꼭지점 공간(정점 집합의 부울 대수)으로 구성되며, 스패닝 서브그래프(가장자리 공간의 요소)를 홀수도의 정점 집합(정점 공간의 요소)에 매핑하는 경계 연산자에 의해 연결된다.호몰로지 그룹

${\displaystyle H_{1}(G,\mathb {Z} _{2})$

정점 공간의 0 요소에 매핑되는 가장자리 공간의 요소들로 구성된다. 이것들은 정확히 오일러식 하위 그래프들이다.그것의 그룹 운영은 오일러 서브그래프의 대칭 차이 연산이다.

임의의 링에 의해 이 $구조$에서 ${\displaystyle {\mathrm{}}_{}}$ 2 ${\$}를 대체하면 링 위에 모듈을 형성하는 지정된 링에 계수가 있는 공간까지 사이클 공간의 정의를 확장할 수 있다.^[7]특히 일체형 사이클 공간은 공간이다.

${\displaystyle H_{1}(G,\mathb {Z}).}$

그래프의 임의 방향을 선택하고 그래프 $G{\displaystyle }$ ${\displaystyle G}$의 적분 주기를 각 꼭지점에서 n의 합을 나타내는 속성과 함께 $G{\displaystyle }$ ${\displaystyle G}($가장자리 위의 자유 아벨리아 그룹의 요소)의 가장자리에 정수를 할당하는 것으로$$ 정의함으로써 그래프 이론적 용어로 정의할 수 있다.들어오는 가장자리에 할당된 탯줄은 나가는 가장자리에 할당된 숫자의 합과 같다.^[8]

A member of ${\displaystyle H_{1}(G,\mathbb {Z} )}$ or of ${\displaystyle H_{1}(G,\mathbb {Z} _{k})}$ (the cycle space modulo ${\displaystyle k}$) with the additional property that all of the numbers assigned to the edges are nonzero is called a nowhere-zero flow or a nowhere-zero $$${\displaystyle k}$ $[\displaystyle k}$ -flow$$.^[9]

회로 순위

벡터 공간으로서, $정점$ $n{\displaystyle }$ ${\displaystyle n},$ m ${\displaystyle$ m$},$ c$$ ${\displaystyle$ c}이$($가) 연결된 그래프의 사이클 공간 치수는 ${\displaystyle m}$- n${\displaystyle }$+ ${\displaystyle c}$ ${\displaystyle m-n+c}$이다$.$^[1][2][10]이 숫자는 위상학적으로 그래프의 첫 번째 베티 번호로 해석할 수 있다.^[6]그래프 이론에서, 그것은 그래프의 회로 순위, 사이클로메틱 수 또는 무효로 알려져 있다.

이 순위에 대한 공식을 사이클 공간이 2요소 영역에 걸친 벡터 공간이라는 사실과 결합하면 사이클 공간의 총 원소 수가 정확히 ${\displaystyle {\mathrm{2m}}^{}}$- n +${\displaystyle c^{}}$ ${\$임을 알 수 있다$.$

사이클 베이스

벡터 공간의 기본은 다른 모든 요소가 기본 요소의 선형 결합으로 기록될 수 있는 특성을 가진 요소의 최소 부분집합이다.유한차원 공간의 모든 기초는 동일한 수의 원소를 가지며, 이는 공간의 치수와 같다.사이클 공간의 경우, 기본은 $정확히{\displaystyle m}$ -${\displaystyle }$n + ${\displaystyle c}${\$displaystyle m-n+c}$ 을러어$$ 서브그래프의 계열이며, 모든 을러어 서브그래프를 기본 요소 계열의 대칭적 차이로 작성할 수 있는 속성이 있다.

존재

베블렌의 정리에 의해,^[11] 주어진 그래프의 모든 오일러 서브그래프는 단순한 사이클로 분해될 수 있다. 서브그래프는 모든 정점이 0도 또는 2도를 가지고 있고, 도 2 정점이 연결된 세트를 형성하는 서브그래프.따라서 기본 요소 자체가 모두 단순한 사이클이라는 근거를 항상 찾을 수 있다.그러한 근거를 주어진 그래프의 사이클 베이시스라고 한다.더 강하게는, 기본 요소들이 유도 사이클 또는 (3Vertex 연결 그래프에서) 유도 사이클이며, 제거가 나머지 그래프를 분리하지 않는 유도 사이클의 근거를 항상 찾을 수 있다.^[12]

근본적이고 약하게 근본적 기초

사이클 베이스를 구성하는 한 가지 방법은 그래프의 스패닝 포리스트를 형성한 다음 포리스트에 속하지 않는$$ 각 에지 $e{\displaystyle }$ ${\displaystyle e}$에 대해 $e{\displaystyle }$ ${\displaystyle e}$로 구성된$$ 사이클 ${\displaystyle C_{}}$ e ${\$를 형성하고 $e{\displaystyle }$ ${\displaystystyle e$}의 끝점을 연결하는 포리스트의 경로를 형성한다$$.$\}\}.$ 이러한 방식으로 형성된$$ 사이클 $C{\displaystyle {}_{}}$ ${\displaystyle e_{}}$ ${\$의 집합은 선형적으로 독립적이며(각 사이클에는 다른 사이클에 속하지 않는$$ 에지 $e{\displaystyle }$ ${\displaystyle e}$이(가) 포함되어 있음) 올바른 $크기{\displaystyle }$ m${\displaystyle }$- ${\displaystyle n}$+ ${\displaystyle c}$ ${\displaystym m-n+c}$을 기본으로 하기 때문에 반드시$$ 기본이 된다.이런 식으로 형성된 기초를 근본 사이클 베이스라고 한다.^[1]

각 사이클이 이전 사이클의 일부가 아닌 적어도 하나의 에지를 포함하도록 사이클 단위로 사이클의 선형 순서가 존재하는 경우, 사이클 베이스를 약하게 기본이라고 한다.모든 기본 사이클 기초는 약하게 기초적이지만(모든 선형 순서에 대해) 반드시 그 반대의 경우도 아니다.약하게 기초가 되지 않는 그래프와 그 그래프에 대한 사이클 베이스가 존재한다.^[13]

최소 중량 기준

그래프의 가장자리에 실제 수 가중치가 부여된 경우, 하위 그래프의 가중치는 가장자리 가중치의 합으로 계산할 수 있다.주기 공간의 최소 중량 기준은 반드시 주기 기준이며, 다항 시간 내에 구성할 수 있다.^[8]최소 중량 기준이 항상 약하게 기초적인 것은 아니며, 그렇지 않을 때는 최소 가능 중량으로 약하게 기초적인 기초를 찾는 것이 NP-강력하다.^[13]

평면 그래프

호몰로지

평면 그래프가 평면에 내장되는 경우, 평면 그래프의 가장자리와 꼭지점의 체인 콤플렉스는 그래프의 면 세트도 포함하는 고차원 체인 콤플렉스에 내장될 수 있다.이 체인 단지의 경계도는 어떤 2체인(면들의 집합)이라도 2체인 내의 홀수 면수에 속하는 가장자리 집합으로 가져간다.2사슬의 경계는 반드시 오일러식 서브그래프로서, 모든 오일러식 서브그래프는 정확히 두 개의 다른 2체크(각각은 다른 체인의 보완물)로부터 이런 방식으로 생성될 수 있다.^[14]이로부터 임베딩의 경계면 집합이 평면 그래프의 주기 기준을 형성한다: 이 주기 집합에서 무한면을 제거하면 각 오일러 서브그래프가 2개에서 정확히 1개로 생성될 수 있는 방법의 수가 감소한다.

맥 레인의 평면성 기준

손더스 맥 레인(Sunders Mac Lane)의 이름을 딴 맥 레인(Mac Lane)의 평면성 기준은 평면 그래프의 사이클 공간과 사이클 베이스 측면에서 특징을 나타낸다.그것은 그래프의 각 가장자리가 최대 두 개의 기본 사이클에 참여하는 사이클 베이스를 가진 경우에만 유한한 비방향 그래프를 평면이라고 명시한다.평면 그래프에서, 내장형 경계면 집합에 의해 형성된 주기 기준은 반드시 이 특성을 가지고 있다. 각 에지는 분리되는 두 면에 대한 기본 주기에만 참여한다.반대로, 사이클 기준이 에지당 최대 2 사이클을 갖는 경우, 사이클을 그래프를 포함하는 평면형 면의 집합으로 사용할 수 있다.^[14][15]

이중성

평면 그래프의 주기 공간은 이중 그래프의 절단 공간이며, 그 반대의 경우도 마찬가지다.평면 그래프의 최소 중량 주기 기준은 경계면에 의해 형성된 기준과 반드시 동일하지는 않다. 즉, 면에 없는 사이클을 포함할 수 있으며, 일부 면은 최소 중량 주기 기준의 사이클로 포함되지 않을 수 있다.두 사이클이 서로 교차하지 않는 최소 체중 주기 기준이 존재한다. 즉, 기준의 두 사이클마다 사이클이 경계면의 분리형 하위 세트를 둘러싸거나, 두 사이클 중 하나가 다른 사이클을 감싸고 있다.사이클 공간과 절단 공간 사이의 이중성에 따라 평면 그래프의 이 기준은 절단 공간의 최소 중량 기준인 이중 그래프의 고모리-후 트리에 해당한다.^[16]

0이 흐르지 않는 곳

평면 그래프에서 $k{\displaystyle }$ ${\displaystyle k$$}$ 구별되는$$ 색상을 가진 색상은 정수 $modulo$ k$${\$displaystyle$ $\mathb {$$Z$}$_{$k}} 링 ${\displaystyle {}_{}}$로 0으로 이중으로 흐른다$.$ 이 이중성에서 두 인접 영역의 색상의 차이는 가장자리 구분선에 걸친 흐름 값으로 표현된다.지방을 엷게 하다특히 어디에도 없는 4-흐름의 존재는 4색 정리와 맞먹는다.스나크 정리는 이 결과를 비 평면 그래프로 일반화한다.^[17]

참조