최대 일치 가능한 에지

그래프 이론에서 그래프에서 최대 일치 가능한 에지는 그래프에서 적어도 하나의 최대 카디널리티 일치에 포함되는 에지다.^[1]대체 용어는 가장자리가 허용된다.^[2][3]

일치 이론의 근본적인 문제는 다음과 같다: 그래프 G를 주어 G에서 최대 일치 가능한 모든 가장자리 집합을 찾아라.이는 G에서 모든 최대 일치 항목의 조합을 찾는 것과 같다(G에서 단일 최대 일치 항목을 찾는 간단한 문제와는 다르다).이 문제에 대한 몇 가지 알고리즘이 알려져 있다.

동기

남녀 공용의 중매 대행사를 생각해 보십시오.후보자들의 선호도를 고려해, 이 기관은 남성과 여성이 양립할 수 있는 경우, 양립할 수 있는 양립형 그래프를 구성한다.에이전시의 궁극적인 목표는 가능한 한 많은 호환 가능한 커플을 만드는 것이다. 즉, 이 그래프에서 최대 카디널리티 매칭을 찾는 것이다.이 목표를 향해 기획사는 먼저 그래프에서 가장자리를 고르고, 가장자리 양 끝에 있는 남녀에게 만나자고 제안한다.이제 에이전시는 최대한 매치할 수 있는 엣지만을 선택하도록 신경을 써야 한다.최대 일치성이 없는 에지를 선택하면 최대 카디널리티 매칭까지 완료할 수 없는 에지로 고착될 수 있기 때문이다.^[1]

정의

G = (V,E)를 그래프로 표시하십시오. 여기서 V는 정점이고 E는 에지입니다.G에서의 일치는 E의 부분 집합 M으로, V의 각 정점이 M의 단일 에지에 거의 인접해 있다. 최대 일치는 최대 카디널리티의 일치가 된다.

E의 에지 e는 e를 포함하는 최대 일치 M이 있는 경우 최대 일치 가능(또는 허용)이라고 한다.

일반 그래프 알고리즘

현재 일반 그래프의 가장 잘 알려진 결정론적 알고리즘은 시간 $O{\displaystyle (V}$ E$){\displaystyle$ O$(VE)}$ 로 실행된다.$$^[2]

시간 $O{\displaystyle \stackrel{}{}}$~ (${\displaystyle {}^{}}$ $){\displaystyle {O}}(V^{2.376})$에 일반 그래프에 대한 랜덤화 알고리즘이 있다.$$^[4]

초당적 그래프 알고리즘

초당적 그래프에서 단일 최대 카디널리티 일치가 알려진 경우 선형 시간 - O${\displaystyle (V}$+ ${\displaystyle E}$) ${\displaystyle O(V+E)}$에서 최대 일치 가능한 모든 에지를 찾을 수 있다$.$^[1]

최대 일치를 알 수 없는 경우 기존 알고리즘으로 찾을 수 있다.In this case, the resulting overall runtime is ${\displaystyle O(V^{1/2}E)}$ for general bipartite graphs and ${\displaystyle O((V/\log V)^{1/2}E)}$ for dense bipartite graphs with ${\displaystyle E=\$$세타(V^{2})}$.

완벽하게 일치하는 초당적 그래프

최대 일치 가능한 가장자리를 찾기 위한 알고리즘은 그래프가 완벽한 일치를 인정할 때 더 간단하다.^{[1]: sub.2.1}

Let the bipartite graph be ${\displaystyle G=(X+Y,E)}$, where ${\displaystyle X=(x_{1},\ldots ,x_{n})}$ and ${\displaystyle Y=(y_{1},\ldots ,y_{n})}$. Let the perfect matching be ${\displayst$$yle M=\{(x_{1},y_{1}),\ldots ,(x_{n},y_{n$

정리: 일부 M 대체 사이클에 포함된 경우 에지 e는 최대 일치 가능 - M의 에지와 M이 아닌 에지 사이에서 교대하는 사이클. 증명:

• e가 교대 사이클인 경우, e가 M에 있거나 - 사이클을 뒤집음으로써 e가 포함된 새로운 완벽한 일치를 얻는다.따라서 e는 최대한 일치할 수 있다.
• 반대로, e가 최대 일치할 수 있다면, 완전히 일치하는 N에 있다.M과 N의 대칭적인 차이를 취함으로써 e를 포함하는 교대 사이클을 구성할 수 있다.

Now, consider a directed graph ${\displaystyle H=(Z,E)}$, where ${\displaystyle Z=(z_{1},\ldots ,z_{n})}$ and there is an edge from ${\displaystyle z_{i}}$ to ${\displaystyle z_{j}}$ in H iff ${\displaystyle i\neq j}$ and there is an edge between ${\displaystyle x_{}}$${\displaystyle {}_{}}$G의$$i {\$displaystyle x_{$i$$$$} ${\displaystyle {및}_{}}$ y j ${\$ G의 각 M 대체 주기는 H의 지시된 주기에 해당한다. 두 끝점이 모두 동일한 강하게 연결된 구성 요소에 속할 경우 지시된 주기에 속한다.선형 시간 내에 강하게 연결된 모든 구성요소를 찾아내는 알고리즘이 있다.따라서 최대 일치 가능한 모든 가장자리 집합을 다음과 같이 찾을 수 있다.

• 간접적인 초당적 $그래프{\displaystyle }$ G${\displaystyle }$=${\displaystyle }$( ${\displaystyle X}$+ ${\displaystyle Y}$, E${\displaystyle }$) ${\displaystyle$ G$=(X+Y,E)}$ 및 완벽하게$$ 일치하는 M을 볼 때 모든 에지$({\displaystyle {}_{}}$ ${\displaystyle i_{}}$, y ${\displaystyle i_{}}$) ${\displaystyle (x_{i},y_{i}}}})$를 M에 최대 일치 가능으로 표시하십시오.
• 위와 같이$$ 방향 그래프 $H{\displaystyle }$=${\displaystyle }$( ${\displaystyle Z}$, E${\displaystyle }$) ${\displaystyle H=(Z,E)}$을(를) 생성하십시오.
• H에서 강하게 연결된 모든 구성 요소를 찾으십시오.
• 각 i에 대해 j (${\displaystyle {}_{}}$ ${\displaystyle i_{}}$, ${\displaystyle {}_{}}$ ${\displaystyle j_{}}$) ${\displaystyle (z_{i},z_{j}})$이 동일한 구성 요소에 있도록$$ 에지$({\displaystyle {}_{}}$ ${\displaystyle i_{}}$, y ${\displaystyle j_{}}$) ${\displaystyle (x_{i},y_{j}})$를 최대 일치 가능으로$$ 표시하십시오.
• 나머지 모든 가장자리는 최대 일치되지 않는 것으로 표시하십시오.

완벽한 일치가 없는 초당적 그래프

Let the bipartite graph be ${\displaystyle G=(X+Y,E)}$, where ${\displaystyle X=(x_{1},\ldots ,x_{n})}$ and ${\displaystyle Y=(y_{1},\ldots ,y_{n'})}$ and ${\displaystyle n\leq n'}$. Let the given maximum matching be ${\displaystyle M=\{(x_1}$${\displaystyle {}_{},}$ ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$)${\displaystyle }$, , ,${\displaystyle }$( ${\displaystyle x_{}}$ t${\displaystyle {}_{}}$, ${\displaystyle {}_{}{t}_{}}$ ) ${\displaystyle \}}$ ${\displaystyle M=\{(x_{1},y_{1}),\ldots ,(x_{t},y_{t$ 여기서 $t{\displaystyle }$ ${\displaystyle \le }$ n$$ $′{\$E의 가장자리는 두 가지 등급으로 분류할 수 있다.

• 두 끝점이 모두 M으로 포화되어 있는 가장자리.우리는 그러한 가장자리를 M-upper라고 부른다.
• M에 의해 포화되는 정확히 하나의 끝점이 있는 가장자리.우리는 그러한 가장자리를 M-lower라고 부른다.
• 두 끝점이 모두 M에 의해 불포화되지 않은 가장자리는 없다는 점에 유의하십시오. 이는 M의 최대성과 모순되기 때문이다.

정리:모든 $M{\displaystyle }$ ${\displaystyle M}$ -하단$$ 가장자리는 최대 일치한다.^{[1]: sub.2.2} 증명: $e{\displaystyle }$=${\displaystyle }$( x ${\displaystyle i_{}}$, ${\displaystyle y_{}}$ ${\displaystyle {}_{}}$) ${\displaystyle$ e$=(x_{i},y_{j}}},$ 여기서$$ $x{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$$displaystyle x_{i}}}$은(는$$) 포화 상태이고 ${\displaystyle y_{}}$ i {\displaysty $y_{i}$은(는)가$$ 아니라고 가정한다.그런 다음 $M{\displaystyle }$ ${\displaystyle M}$에서 $e{\displaystyle }$=${\displaystyle }$( x ${\displaystyle i_{}}$, ${\displaystyle y_{}}$ j${\displaystyle {}_{}}$) ${\displaystyle$ e$=($${\displaystyle {}_{}}$${i},y_{j}}}$를 제거하고$$ e = ( x${\displaystyle }i{\displaystyle }$, ${\displaystyle y_{}}$ ) ${\displaystyle {}_{}{displaystyle}_{}}$ e=($x_{i$},$y_{j}}})$를 추가하면 새로운$$ 최대 카디널리티 일치가 생성된다.

따라서 M-upper 중에서 최대 일치 가능한 가장자리를 찾아야 한다.

H를 M-포화 노드에 의해 유도된 G의 서브그래프가 되게 한다.M은 H에서 완벽하게 일치한다는 것에 주목하라.따라서 이전 하위섹션의 알고리즘을 사용하면 H에서 최대 일치할 수 있는 모든 가장자리를 찾을 수 있다.타사는^[1] 그래프가 변경될 때 최대 일치 가능한 에지 집합을 동적으로 업데이트하는 방법뿐만 아니라 나머지 에지를 최대 일치 가능한 에지를 찾는 방법을 설명한다.

참조