일치 전폐

Matching preclusion

수학의 한 분야인 그래프 이론에서, 그래프 G(표시가 있는 mp(G))의 일치된 전폐 번호는 삭제로 인해 완벽한 일치 또는 거의 완벽한 일치(정점 수가 홀수인 그래프에서 하나의 정점을 제외한 모든 정점을 포함하는 일치)가 파괴되는 최소 에지 수입니다.[1]매칭 프리클로저는 분산 시스템의 각 노드를 이웃 파트너 노드와 일치시켜야 하는 분산 알고리즘의 통신 네트워크 토폴로지로서 그래프의 견고성을 측정한다.[2]

대부분의 그래프에서 mp(G)는 단일 정점에 입사하는 모든 가장자리를 삭제하면 일치되지 않기 때문에 그래프에서 모든 정점의 최소 정도와 동일하다.이 가장자리 집합을 사소한 일치 사전 폐색 집합이라고 한다.[2]변형 정의인 조건부 일치 사전 폐색 번호는 완벽하거나 거의 완벽한 일치 또는 분리된 정점이 없는 그래프를 생성하는 최소 에지 수를 요구한다.[3][4]

주어진 그래프의 일치하는 사전 폐색 번호가 지정된 임계값 미만인지 여부를 테스트하는 것은 NP 완료다.[5]

강력한 일치 사전 폐색 번호(또는 단순하게 SMP 번호)는 일치하는 사전 폐색 번호의 일반화이며, 그래프 G, smp(G)의 SMP 번호는 완벽한 일치 항목도 거의 완벽한 일치 항목도 없는 그래프로 삭제되는 정점 및/또는 가장자리의 최소 수입니다.[6]

비방향 그래프에서 가장자리 삭제에 의해 유사한 방식으로 정의된 다른 수에는 가장자리 연결, 그래프 연결을 해제하기 위해 삭제할 최소 가장자리 수, 모든 사이클을 제거하기 위해 삭제할 최소 가장자리 수인 사이클로메틱 수가 포함된다.

참조

  1. ^ Brigham, Robert C.; Harary, Frank; Violin, Elizabeth C.; Yellen, Jay (2005), "Perfect-matching preclusion", Congressus Numerantium, Utilitas Mathematica Publishing, Inc., 174: 185–192.
  2. ^ a b Cheng, Eddie; Lipták, László (2007), "Matching preclusion for some interconnection networks", Networks, 50 (2): 173–180, doi:10.1002/net.20187.
  3. ^ Cheng, Eddie; Lesniak, Linda; Lipman, Marc J.; Lipták, László (2009), "Conditional matching preclusion sets", Information Sciences, 179 (8): 1092–1101, doi:10.1016/j.ins.2008.10.029.
  4. ^ Park, Jung-Heum; Son, Sang Hyuk (2009), "Conditional matching preclusion for hypercube-like interconnection networks", Theoretical Computer Science, 410 (27–29): 2632–2640, doi:10.1016/j.tcs.2009.02.041.
  5. ^ Dourado, Mitre Costa; Meierling, Dirk; Penso, Lucia D.; Rautenbach, Dieter; Protti, Fabio; de Almeida, Aline Ribeiro (2015), "Robust recoverable perfect matchings", Networks, 66 (3): 210–213, doi:10.1002/net.21624.
  6. ^ Mao, Yaping; Wang, Zhao; Cheng, Eddie; Melekian, Christopher (2018), "Strong matching preclusion number of graphs", Theoretical Computer Science, 713: 11–20, doi:10.1016/j.tcs.2017.12.035.


Stub icon

이 콤비네이터 관련 기사는 단조롭다.위키피디아를 확장하여 도울 수 있다.