둘마지-멘델손 분해

Dulmage–Mendelsohn decomposition

그래프 이론에서 둘마지-멘델손 분해초당적 그래프의 정점을 부분 집합으로 분할한 것으로, 인접한 정점 두 개가 그래프의 완벽한 일치를 위해 서로 쌍을 이루는 경우에만 동일한 부분 집합에 속하는 속성이 있다.1958년 이 책을 출간한 A. L. Dulmage와 Nathan Mendelson의 이름을 따서 지은 것이다.어떤 그래프에 대한 일반화는 Blooming 알고리즘을 사용한 Edmonds-Gallai 분해다.

거친 분해

G = (X+Y,E)를 양분 그래프로 하고, D적어도 G의 최대 일치에서 일치되지 않는 G의 정점 집합으로 한다.그러면 D는 반드시 독립된 집합이므로 G는 다음과 같은 세 부분으로 분할할 수 있다.

  • DX의 정점 및 그 이웃.
  • D ∩ Y의 꼭지점 및 그 이웃
  • 나머지 정점.

G의 모든 최대 매칭은 D의 모든 이웃과 일치하는 첫 번째와 두 번째 부분의 매칭과 나머지 정점의 완벽한 매칭으로 구성된다.

대체 조분해

굵은 분해의 대체 정의는 에 제시되어 있다(이 정의는 그것을 에 속하게 되는 사람에 기인한다).

G를 초당적 그래프로 하고, MG로 최대 일치로 하며, V0 M과 일치하지 않는 G의 정점 집합("자유 정점")으로 한다.그런 다음 G를 세 부분으로 나눌 수 있다.

E-O-U 분해
  • E - 짝수 정점 - 짝수 길이의 M 대체 경로를 통해 V로부터0 정점에 도달할 수 있다.
  • O - 홀수 정점 - 홀수 길이의 M 대체 경로를 통해 V로부터0 정점에 도달할 수 있다.
  • U - 연결할 수 없는 정점 - M 대체 경로를 통해 V에서0 연결할 수 없는 정점.

왼쪽에 삽화가 있다.굵은 선은 M의 가장자리.약한 선들은 G의 다른 가장자리들이다.빨간 점은 M과 일치하지 않는 정점이다.

이 분해에 기초하여 G의 가장자리는 끝점에 따라 E-U, E-E, O-O, O-U, E-O, U-U의 6부분으로 분할할 수 있다. 이 분해는 다음과 같은 특성을 가지고 있다.

  1. E, O, U 세트는 쌍으로 분리된다.
  2. 집합 E, O, U는 최대 매칭 M에 의존하지 않는다(즉, 모든 최대 매칭은 정확히 동일한 분해를 정의한다).
  3. G에는 O-O, O-U, E-O, U-U 에지만 들어 있다.
  4. G의 모든 최대 매칭은 E-OU-U 에지만 포함한다.
  5. G의 모든 최대 매칭은 O의 모든 정점과 U의 모든 정점을 포화시킨다.
  6. G에서 최대 매칭 크기는 O + U / 2이다.

미세 분해

굵은 분해의 세 번째 정점 집합(또는 완전히 일치하는 그래프의 모든 정점 집합)은 다음 단계에 의해 하위 집합으로 추가로 분할될 수 있다.

  • G의 완벽한 짝을 찾아라.
  • 정점이 G의 일치된 가장자리인 방향 그래프 H를 형성한다.G의 각 일치하지 않는 에지(x,y)에 대해, x의 일치된 에지에서 y의 일치된 에지까지 H에 지시된 에지를 추가한다.
  • 결과 그래프의 강하게 연결된 구성 요소를 찾으십시오.
  • H의 각 성분에 대해, 성분에 있는 가장자리의 끝점인 G의 정점으로 구성된 덜마게-멘델손 분해의 하위 집합을 형성한다.

하위 집합으로 분할된 이 하위 집합의 하위 집합이 완벽한 일치에 속하는 가장자리의 특성을 나타내도록 하려면 G의 두 꼭지점 xy가 동일한 분해 하위 집합에 속하지만 초기 완전 일치에 의해 이미 일치하지는 않는다고 가정하십시오.그리고 H에는 에지 x,y를 포함하는 강하게 연결된 구성 요소가 있다.이 에지는 반드시 G의 교대 사이클(가장자리가 일치하고 일치하지 않는 가장자리를 교대하는 사이클)에 해당하는 H의 단순한 사이클에 속해야 한다.이 교대 주기는 에지 x,y를 포함하는 새로운 일치를 생성하기 위해 초기 완벽한 일치를 수정하는 데 사용될 수 있다.

그래프 G의 에지 x,y는 분해에서 xy가 그들 집합의 유일한 구성원인 경우에만 G의 모든 완벽한 일치에 속한다.이러한 에지는 그래프의 일치하는 사전 폐색 번호가 1인 경우에만 존재한다.

코어

둘마지-멘델손 분해의 또 다른 구성 요소로서, 둘마지와 멘델손은 그래프의 핵심을 최대 일치의 조합으로 정의했다.[4]단, 이 개념은 그래프 동형성의 의미에서 핵심과 구별되어야 하며, 저도 정점의 제거에 의해 형성된 k-core와 구별되어야 한다.

적용들

이 분해는 유한 요소 분석에서 메쉬를 분할하고 비선형 방정식의 시스템에서 지정, 과소 지정 및 과지정 방정식을 결정하는 데 사용되어 왔다.

참조

  1. ^ "Dulmage Mendelsohn Decomposition" (PDF).
  2. ^ a b Irving, Robert W.; Kavitha, Telikepalli; Mehlhorn, Kurt; Michail, Dimitrios; Paluch, Katarzyna E. (2006-10-01). "Rank-maximal matchings". ACM Transactions on Algorithms. 2 (4): 602–610. doi:10.1145/1198513.1198520.
  3. ^ Pulleyblank, W.R. (1995). "Matchings and Extensions". Handbook of Combinatorics. Amsterdam, North-Holland: Elsevier Science. pp. 179–232.
  4. ^ Harary, Frank; Plummer, Michael D. (1967), "On the core of a graph", Proceedings of the London Mathematical Society, Third Series, 17: 305–314, doi:10.1112/plms/s3-17.2.305, hdl:2027.42/135576, MR 0209184.

외부 링크

  • 비선형 방정식 시스템에 대한 적용에 대한 좋은 설명은 이 논문에서 확인할 수 있다. [1]
  • 알고리즘의 오픈 소스 구현을 스파스 매트릭스 라이브러리의 일부로 사용할 수 있다: SPOOLES
  • SST 프로젝트에서 제약조건 해결의 그래프 이론적 측면: [2]