홀 위반자

그래프 이론에서 홀 위반자는 홀의 결혼 정리 조건에 위배되는 그래프의 꼭지점 집합이다.^[1]

공식적으로, 초당적 $그래프$ G = $(X$ + Y, $E)$ 가 주어지면, $X$ 의 홀-바이올레이터는 $X$ 의 부분집합 $W$ 이며, $N G (W)$ < $W$ , 여기서 $N G (W)$ 은 $G$ 의 $W$ 의 이웃집 집합이다.

$만약$ W가 홀 위반자라면, $W$ 의 모든 정점을 포화시키는 매칭은 없다.따라서 $X$ 를 포화시키는 매칭도 없다.홀의 결혼 정리는 그 반대도 사실이라고 말한다: 홀 위반자가 없다면 $X$ 를 포화시키는 매칭이 존재한다.

알고리즘

홀 위반자 찾기

홀 위반자는 효율적인 알고리즘으로 찾을 수 있다.아래의 알고리즘은 다음과 같은 용어를 사용한다.

M 대체 경로는, 어떤 일치하는 $M$ 에 대해, 첫 번째 $에지$ 가 M의 에지가 아니고, 두 번째 에지가 $M$ 의 에지가 아니며, 세 번째 에지가 $M$ 의 에지가 아닌 등의 경로다.
꼭지점 $z$ 는 $x$ 에서 $z$ 까지의 M 대체 경로가 있는 경우 일부 꼭지점 $x$ 에서 M-접근 가능하다.

예를 들어, 수직(파란색) 모서리가 일치하는 $M$ 을 나타내는 오른쪽의 그림을 고려해 보십시오.정점 집합 $Y 1,$ X, $Y 1 2,$ $X$ 는₂ $x 0$ (또는 $X$ 의₀ 다른 정점)에서 M-접근 가능하지만 $Y$ 와₃ $X$ 는₃ $x$ 에서₀ M-접근 가능하지 않다.

홀 위반자를 찾기 위한 알고리즘은 다음과 같이 진행된다.

최대 일치 $M$ 을 찾으십시오(Hopcroft-Karp 알고리즘으로 찾을 수 있음).
$X$ 의 모든 정점이 일치하는 경우, "홀 위반자가 없음"을 반환하십시오.
그렇지 않으면 $x$ 가₀ 비할 데 없는 꼭지점이 되게 한다.
$W$ 는 $X$ 로부터₀ M-접근 가능한 $X$ 의 모든 정점의 집합이 되게 하라(Width-first search를 사용하여 찾을 수 있다, 그림에서 $W$ 는 $X$ 와₀ $X$ 를₁₂ 포함한다).
$W$ 를 반환하십시오.

이 $W$ 는 다음과 같은 사실 때문에 실로 홀 폭력이 된다.

$N G (W)$ 의 모든 정점은 $M$ 으로 일치한다.모순에 의해 $N G (W)$ 의 일부 정점 $y$ 가 $M$ 과 일치하지 않는다고 가정하자. $x$ 를 $W$ 에서 이웃으로 삼아라. $x$ 에서₀ $x$ 에서 $y$ 까지의 경로는 M-증강 경로 - M-대체로 되어 있으며, 일치하지 않는 정점으로 시작하고 끝나기 때문에 "인버팅"함으로써 $M$ 을 증가시킬 수 있고, 그 최대성과 모순된다.
$W$ 는 $M$ 에 의한 $N G (W)$ 의 모든 일치를 포함한다.왜냐하면 이 모든 $성냥$ 은₀ x에서 M-reach가 가능하기 때문이다.
$W$ 는 정의상 $M$ 으로 일치하지 않는 또 다른 꼭지점인 $x$ 를₀ 포함한다.
따라서 $W$ = $N G (W)$ + $1$ > $N G (W)$ , 따라서 $W$ 는 실제로 홀 위반자의 정의를 만족한다.

최소 및 최소 홀 위반자 찾기

포함 최소 홀 위반자는 홀 위반자로, 각 하위 세트가 홀 위반자가 아니다.

실제로 위의 알고리즘은 포함 최소 홀 위반자를 찾아낸다.왜냐하면, $W$ 에서 정점을 제거한 경우, 나머지 정점을 $N G (W)$ 의 정점과 완벽하게 일치시킬 수 있기 때문이다( $M$ 의 가장자리 또는 $x$ 의₀ M 대체 경로의 가장자리).^[2]

위의 알고리즘이 반드시 최소 카디널리티 홀 위반자를 찾는 것은 아니다.예를 들어 위의 그림에서 홀 위반자는 크기가 5인 반면, $X$ 는₀ 크기가 3인 홀 위반자를 반환한다.

사실, 최소 카디널리티 홀 위반자를 찾는 것은 NP-hard이다.이것은 클라이크 문제로부터의 축소를 통해 증명할 수 있다.^[3]

홀 위반자 또는 증축 경로 찾기

다음 알고리즘은^[4]^[5] 그래프에서 임의로 일치하는 $M$ 을 입력하고, M에 $의해$ 포화되지 $않는$ X의 꼭지점 $x$ 를₀ 입력하는 것으로 한다.

$그것$ 은₀ x를 포함하는 홀 위반자 또는 $M$ 을 증가시키는 데 사용할 수 있는 경로 중 하나로서 출력으로 반환된다.

$k$ = $0$ , $W k$ $:=$ { $x 0$ }, $Z k$ $:= {}$ 을(를) 설정하십시오.
주장:
- $W k =$ { $x 0,..., x k},$ $여기$ 서_i x는 $X$ 의 뚜렷한 정점이다.
- $Z k =$ { $y 1,..., y k},$ 여기서 $y$ 는_i $Y$ 의 뚜렷한 정점이다.
- 모든 $i$ ≥ $1$ 에 대해 $y$ 는_i $m$ 로 $x$ 와_i 일치한다.
- 모든 $i$ ≥ $1$ 에 대해 $y$ 는_i $M$ 이 아닌 가장자리로 일부 $x$ 에_j_<i 연결된다.
$N G k$ $(W k)$ ⊆ $Z이면 k$ W = k $+1$ > $k k$ = Z ≥ $N G (W k)$ 이므로 $W$ 는_k 홀 위반자. 홀 폭력자 $W$ 를_k 반환한다.
그렇지 않으면 $N k +1 G (W k)$ \ $Z$ 의_k 꼭지점이 되게 한다 $.$ 다음 두 가지 경우를 고려하십시오.
사례 1: $y$ 는_k+1 $M$ 과 일치한다.
- $x$ 는₀ 일치하지 않고, $W$ 의_k $모든 i$ x는 $Z$ 의_i_k y와 일치하므로, $이 k +1$ y의 파트너는 반드시 $W$ 에_k 있지 $않은$ X의 꼭지점일 것이다. $x$ 로_k+1 그것을 나타낸다.
- $W k +1 := W k U$ { $x k +1}$ 과( $와 k)$ $Z k +1$ :=Z U { $y k +1}$ 과(와) $k$ $:= k$ + $1$ 로 한다.
- 2단계로 돌아가십시오.
사례 2: $y$ 는_k+1 $M$ 과 일치하지 않는다.
- $y$ 는_k+1 $N G (W k$ )에 있으므로 $,$ $일부 i$ $x$ ( $i$ < k + 1)에 M에 있지 않은 가장자리로 연결된다. $x$ 는_i M의 가장자리로 $y$ 에_i 연결된다. $y$ 는_i $M$ 에 있지 않은 가장자리로 일부 x $(j$ < $i$ 의 경우)에_j 연결된다.이러한 연결을 따르는 것은 결국 $x$ 로₀ 이어져야 하는데, 이는 타의 추종을 불허한다.그래서 우리는 M-증강로가 있다.M-증강 경로를 반환하십시오.

각각의 반복에서 $W$ 와_k $Z$ 는_k 하나의 꼭지점만큼 자란다.따라서 알고리즘은 최대 $X번$ 반복 후에 완료되어야 한다.

절차를 반복적으로 사용할 수 있다: $M$ 이 빈 일치로 시작하거나, 홀 위반자가 발견되거나, 일치하는 $M$ 이 $X$ 의 모든 정점을 포화시킬 때까지 절차를 반복해서 호출한다.이것은 홀의 정리에 건설적인 증거를 제공한다.

외부 링크

제약 프로그래밍에서 홀 위반자의 적용.^[6]
"Finding a subset in bipartite graph violating Hall's condition". Computer science stack exchange. 2014-09-15. Retrieved 2019-09-08.{{cite web}}: CS1 maint : url-status (링크)

참조

^ Lenchner, Jonathan (2020-01-19). "On a Generalization of the Marriage Problem". arXiv:1907.05870v3 [math.CO].
^ Gan, Jiarui; Suksompong, Warut; Voudouris, Alexandros A. (2019-09-01). "Envy-freeness in house allocation problems". Mathematical Social Sciences. 101: 104–106. arXiv:1905.00468. doi:10.1016/j.mathsocsci.2019.07.005. ISSN 0165-4896. S2CID 143421680.
^ 아 디트야 카브라"최소 k Union 문제의 파라미터화된 복잡성".MS Statement.정리 3.2.5.이것은 또한 [4] Marek Cygan, Fedor V의 연습 13.28이다.포민, 루카스 코왈릭, 다니엘 롯샤나노프, 드니엘 마르크스, 마르신 필립스쿠크, 미차 필립스쿠크, 사켓 사우라브, "파라미터화된 알고리즘", 스프링거, 2016.CS stackexchange post도 참조하십시오.
^ Mordecai J. Golin (2006). "Bipartite Matching & the Hungarian Method" (PDF).
^ Segal-Halevi, Erel; Aigner-Horev, Elad (2019-01-28). "Envy-free Matchings in Bipartite Graphs and their Applications to Fair Division". arXiv:1901.09527v2 [cs.DS].
^ Elffers, Jan; Gocht, Stephan; McCreesh, Ciaran; Nordström, Jakob (2020-04-03). "Justifying All Differences Using Pseudo-Boolean Reasoning". Proceedings of the AAAI Conference on Artificial Intelligence. 34 (2): 1486–1494. doi:10.1609/aaai.v34i02.5507. ISSN 2374-3468. S2CID 208242680.

[1] Lenchner, Jonathan (2020-01-19). "On a Generalization of the Marriage Problem". arXiv:1907.05870v3 [math.CO].

[2] Gan, Jiarui; Suksompong, Warut; Voudouris, Alexandros A. (2019-09-01). "Envy-freeness in house allocation problems". Mathematical Social Sciences. 101: 104–106. arXiv:1905.00468. doi:10.1016/j.mathsocsci.2019.07.005. ISSN 0165-4896. S2CID 143421680.

[3] 아 디트야 카브라"최소 k Union 문제의 파라미터화된 복잡성".MS Statement.정리 3.2.5.이것은 또한 [4] Marek Cygan, Fedor V의 연습 13.28이다.포민, 루카스 코왈릭, 다니엘 롯샤나노프, 드니엘 마르크스, 마르신 필립스쿠크, 미차 필립스쿠크, 사켓 사우라브, "파라미터화된 알고리즘", 스프링거, 2016.CS stackexchange post도 참조하십시오.

[4] Mordecai J. Golin (2006). "Bipartite Matching & the Hungarian Method" (PDF).

[5] Segal-Halevi, Erel; Aigner-Horev, Elad (2019-01-28). "Envy-free Matchings in Bipartite Graphs and their Applications to Fair Division". arXiv:1901.09527v2 [cs.DS].

[6] Elffers, Jan; Gocht, Stephan; McCreesh, Ciaran; Nordström, Jakob (2020-04-03). "Justifying All Differences Using Pseudo-Boolean Reasoning". Proceedings of the AAAI Conference on Artificial Intelligence. 34 (2): 1486–1494. doi:10.1609/aaai.v34i02.5507. ISSN 2374-3468. S2CID 208242680.

[1]

[2]

[3]

[4]

[5]

[6]

Search