귀 분해

그래프 이론에서, 방향하지 않은 그래프 G의 귀는 경로 P로 경로의 두 끝점이 일치할 수 있지만, 그렇지 않으면 가장자리나 정점의 반복이 허용되지 않기 때문에 P의 모든 내부 정점에는 G의 2도가 있다.비방향 그래프 G의 귀 분해는 각 귀의 한 두 끝 또는 두 끝점이 시퀀스에서 초기 귀에 속하고 각 귀의 내부 정점이 어떤 초기 귀에 속하지 않도록 귀의 일련의 가장자리를 분할한 것이다.또한 대부분의 경우 시퀀스의 첫 귀는 사이클이어야 한다.열린 귀 분해 또는 적절한 귀 분해는 첫 번째 귀 다음에 각 귀의 두 끝점이 서로 구별되는 귀 분해다.

귀 분해는 몇 가지 중요한 그래프 클래스의 특성 및 효율적인 그래프 알고리즘의 일부로 사용될 수 있다.그것들은 또한 그래프에서 모종까지 일반화될 수 있다.

그래프 클래스 특성 지정

몇 가지 중요한 등급의 그래프는 특정 유형의 귀 분해를 갖는 그래프로 특징지어질 수 있다.

그래프 연결

그래프는 (k - 1) 정점을 제거하면 (k - 1) k-vertex 연결되고, (k - 1) 가장자리를 제거하면 (k - 1) 연결된 서브그래프가 남아 있으면 (k-edge) 연결된다.

다음 결과는 하슬러 휘트니(1932) 때문이다.

${\displaystyle E}$ ${\displaystyle \ge }$ ${\displaystyle 2}$ ${\displaystyle$ E $\geq$ 2$}$이(가) 있는 그래프 $G{\displaystyle }$=${\displaystyle }$(${\displaystyle V}$, ${\displaystyle E}$) ${\displaystyle$ $G$$=(V,E)}$은 오픈 이어 분해된 경우에만 2Vertex 연결된다$$.

다음 결과는 허버트 로빈스(1939년) 때문이다.

그래프는 귀가 분해된 경우에만 2-엣지로 연결된다.

두 경우 모두 귀의 수는 반드시 주어진 그래프의 회로 등급과 동일하다.로빈스는 로빈스 정리를 증명하기 위한 도구로 2개의 가장자리 연결 그래프의 귀 분해를 소개했는데, 이 그래프들이 바로 강하게 연결된 방향으로 주어질 수 있는 그래프라는 것이다.귀 분해에 관한 휘트니와 로빈스의 선구적인 연구 때문에, 귀 분해를 휘트니-로빈스 합성(Gross & Yellan 2006)이라고도 부르기도 한다.

비분리 귀 분해는 하나의 예외만을 제외하고 각 꼭지점 v에 대해 v가 v의 첫 번째 출현보다 더 늦은 귀 안에 있는 이웃을 갖는 개방 귀 분해다.휘트니의 결과를 일반화하기 위해 이러한 유형의 귀 분해를 사용할 수 있다.

${\displaystyle V}$${\displaystyle (}$ ${\displaystyle 2}$ ${\displaystyle \{\backslash }$$displaystyle$V \geq 2}이$(가)$ 있는$$ 그래프 G${\displaystyle }$= ($V$ , E${\displaystyle }$) ${\displaystyle$ G$=(V,E)}$은 G가 분리되지 않은 귀 분해를 가진 경우에만 3-Vertex 연결된다$$.

만일 그러한 분해가 존재한다면, 그것은 G의 특정 에지 uv에 관해서 u가 첫 번째 귀에 있고, v는 두 개 이상의 에지를 가진 마지막 귀의 새로운 정점이며, uv는 단 에지 귀이다.이 결과는 처음에는 체리얀과 마헤슈와리(1988)에 의해 명시적으로 언급되었지만, 슈미트(2013b)가 기술한 바와 같이 1971년 리 몬드쉐인의 박사학위 논문에서 나온 결과와 맞먹는다.표준 순서라 불리는 최대 평면 그래프의 분리되지 않은 귀 분해와 밀접한 관련이 있는 구조도 그래프 도면의 표준 도구다.

지시된 그래프의 강력한 연결성

위의 정의는 지시된 그래프에도 적용할 수 있다.이어 귀는 모든 내부 정점이 외설적이고 1과 같은 학위가 있는 방향의 경로가 될 것이다.방향 그래프는 모든 꼭지점에서 다른 모든 꼭지점까지의 방향 경로를 포함하는 경우 강하게 연결된다.그러면 우리는 다음과 같은 정리를 하게 된다(Bang-Jensen & Gutin 2007, Orgion 7.2.2).

지시된 그래프는 귀가 분해된 경우에만 강하게 연결된다.

인자중요 그래프

귀 분해는 각각의 귀가 홀수 수의 가장자리를 사용하면 이상하다.인자 임계 그래프는 정점 수가 홀수인 그래프로, 즉 각 꼭지점 v에 대해 v를 그래프에서 제거하면 나머지 정점이 완벽하게 일치한다.로바스 (1972) 라슬로 로바스 (Laszlo Lovasz)는 다음과 같은 사실을 발견했다.

그래프 G는 G가 홀수 귀 분해를 가진 경우에만 인자에 중요하다.

더 일반적으로, 프랭크(1993)의 결과는 어떤 그래프 G에서든 가장 적은 수의 짝수 귀로 귀의 부패를 찾을 수 있게 한다.

시계열-병렬 그래프

나무 귀 분해는 적절한 귀 분해 계약에 따라 최초 귀은 한 가장자리와 각 연속적인 귀에 나는}P{\displaystyle P_{나는}, 하나 귀 Pj{\displaystyle P_{j}}은, 나입니다.;j{\displaystyle i>, j}, Pj.에 있는 것처럼 P의 두 끝점 나는{\displaystyle P_{나는}}거짓말 {\dis$Playstyle$ P_${j}($Khuller 1989).$$중첩 귀 분해는 각 귀 ${\displaystyle P_{}}$ $j{\displaystyle {}_{}}$ ${\$ 내에서$$${\displaystyle P_{}}$ j ${\$ 안에 있는$$ 다른 귀 ${\displaystyle P_{}}$ i ${\$의 끝점 쌍이 중첩된 간격 집합을 형성하는$$ 나무 귀 분해다.직렬-병렬 그래프는 두 가지 방법 중 하나로 작은 직렬-병렬 그래프를 조합하여 재귀적으로 형성할 수 있는 두 개의 지정된 단자 s와 t를 가진 그래프로서, 직렬 구성(작은 그래프에서 한 단자를 다른 작은 그래프에서 한 단자로 식별하고 다른 두 단자를 콤비의 단자로 유지함)이다.네드 그래프) 및 병렬 구성(두 개의 더 작은 그래프에서 두 개의 단자 쌍을 구함).

다음 결과는 데이비드 엡스타인(1992) 때문이다.

2-Vertex 연결 그래프는 중첩된 귀 분해가 있는 경우에만 직렬-병렬이다.

또한 2-Vertex 연결 직렬-병렬 그래프의 모든 오픈 이어 분해는 내포되어야 한다.결과는 두 단자 사이의 경로로 시작하는 오픈 이어 분해물을 사용하여 2-Vertex가 연결되지 않은 직렬-병렬 그래프까지 확장될 수 있다.

매트로이드

귀 분해의 개념은 그래프에서 매트로이드로 확장될 수 있다.매트로이드의 귀 분해는 매트로이드의 회로 시퀀스로 정의되며, 다음 두 가지 특성이 있다.

• 시퀀스의 각 회로는 이전 회로와 비어 있지 않은 교차점을 가지고 있으며,
• 시퀀스의 모든 이전 회로가 수축되더라도 시퀀스의 각 회로는 회로로 유지된다.

그래프 G의 그래픽 매트로이드에 적용했을 때, 이 귀 분해의 정의는 G의 적절한 귀 분해의 정의와 일치한다: 부적절한 분해는 각 회로가 이전 회로에도 속하는 적어도 하나의 에지를 포함해야 한다는 요건에 의해 제외된다.이 정의를 사용하여 매트로이드는 시퀀스의 각 회로가 홀수 수의 새 원소를 갖는 귀 분해(Szegedy & Szegedy 2006)를 가진 경우 인자중요로 정의할 수 있다.

알고리즘

고전적인 컴퓨터에서는, 2개의 엣지로 연결된 그래프의 귀 분해와 2개의 vertex로 연결된 그래프의 오픈 이어 분해는 한 번에 한 개의 귀를 찾는 탐욕스러운 알고리즘에 의해 발견될 수 있다.귀 분해, 귀 분해, 귀 분해, 성 번호 및 방향성을 동시에 선형 시간(존재하는 경우)으로 계산하는 단순한 탐욕적 접근법이 슈미트(2013a)에 제시되어 있다.이 접근방식은 하나의 경로 생성 규칙에 의한 체인 분해라는 특수한 귀 분해 계산에 기초한다.슈미트(2013b)는 분리되지 않은 귀 분해도 선형 시간에 구성될 수 있음을 보여준다.

로바스츠(1985), 마온, 쉬베르&비슈킨(1986), 밀러&라마찬드란(1986)은 다양한 형태의 귀 분해물을 구성하는 효율적인 병렬 알고리즘을 제공했다.예를 들어, 2개의 엣지 연결 그래프의 귀 분해를 찾기 위해 Maon, Schieber & Vishkin(1986)의 알고리즘은 다음 단계에 따라 진행한다.

1. 지정된 그래프의 스패닝 트리를 찾아 트리의 루트를 선택하십시오.
2. 트리의 일부가 아닌 각 에지 uv에 대해 u와 v의 루트 및 가장 낮은 공통 조상 사이의 거리를 결정한다.
3. 트리의 일부인 각 에지 uv에 대해, 나무에 wx를 추가하여 형성된 주기가 uv를 통과하고, 그러한 에지들 중에서 w와 x가 가능한 한 근에 가까운 가장 낮은 공통 조상을 갖는(가장자리 식별자에 의해 부러진) 나무의 일부인 해당 "마스터 에지"를 찾는다.
4. 각 나무 가장자리와 나무 가장자리로 구성된 나무 가장자리로 귀를 형성하고, 가장자리의 가장자리와 뿌리 사이의 거리를 기준으로 귀를 정렬한다(동일한 타이브레이킹 규칙으로).

이러한 알고리즘은 연결 테스트, 직렬-병렬 그래프 인식 및 그래프의 ST 번호 구성(평면성 테스트에서 중요한 서브루틴)을 포함한 다른 문제에 대한 서브루틴으로 사용될 수 있다.

모든 귀에는 매트로이드의 동일한 고정 요소가 포함되어 있다는 추가적인 제약조건과 함께 주어진 매트로이드의 귀 분해는 매트로이드에 대한 독립성 신탁에 대한 접근이 주어진 다항식 시간에 발견될 수 있다(Coullard & Helerstein 1996).

참조