이분 그래프
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
이분 그래프는 그래프 이론의 한 종류로, 그래프의 꼭짓점 집합을 두 개의 부분 집합으로 분할하여, 각 간선이 서로 다른 부분 집합에 속한 꼭짓점을 연결하도록 구성된다. 이는 그래프의 색칠수가 2 이하인 경우와 동일하며, 홀수 길이의 사이클을 포함하지 않는 그래프와 동치이다. 이분 그래프는 다양한 방식으로 특징지을 수 있으며, 쾨니그의 정리를 비롯한 여러 정리와 관련이 있다. 이분 그래프는 깊이 우선 탐색 또는 너비 우선 탐색을 통해 선형 시간 내에 판별할 수 있으며, 최대 매칭은 다항 시간 내에 구할 수 있다. 이분 그래프는 부호 이론, 컴퓨터 과학, 사영 기하학 등 다양한 분야에서 응용되며, 사회 연결망 분석, 철도 최적화 문제, 화폐학 등에서도 활용된다.
더 읽어볼만한 페이지
- 이분 그래프 - 나무 그래프
나무 그래프는 사이클이 없는 연결된 무방향 그래프로서, 꼭짓점 수보다 변의 수가 하나 적고 임의의 두 꼭짓점 사이에 유일한 경로가 존재하여 다양한 분야에 활용된다. - 홀짝성 - 패리티 비트
패리티 비트는 이진 데이터에서 1의 개수가 짝수인지 홀수인지 나타내는 비트로서, 오류 감지 및 수정에 사용되며, 통신 프로토콜과 RAID 시스템 등 다양한 분야에서 활용된다. - 홀짝성 - 반정수
반정수는 정수에 1/2을 더한 수로 표현되며, 정수와 함께 덧셈 연산에 대해 군을 형성하지만 환은 형성하지 않고, 양자역학, 페르미온의 스핀, 4차원 격자 포장 등 다양한 분야에 응용된다. - 그래프족 - 척도 없는 네트워크
척도 없는 네트워크는 네트워크 과학에서 연결 정도 분포가 멱법칙을 따르는, 즉 일부 허브 노드가 압도적으로 많은 연결을 가지는 불균등한 연결 구조를 가진 네트워크를 의미하며, 바라바시-앨버트 모델로 설명된다. - 그래프족 - 정규 그래프
정규 그래프는 그래프 이론에서 모든 꼭짓점의 차수가 동일한 그래프를 의미하며, 각 꼭짓점이 k개의 변에 잇닿아 있는 그래프를 k-정규 그래프라고 하고, 여러 성질 및 다양한 분야에 응용된다.
이분 그래프 |
---|
2. 정의
그래프 Γ=(V,E)와 자연수 k∈N가 주어졌다고 하자. 만약 V가 다음과 같은 조건을 만족시키는 집합의 분할
:V=V1 ⊔ V2 ⊔ ... ⊔ Vk
을 가질 수 있다면, Γ를 '''k분 그래프'''라고 한다.
- 변으로 연결된 두 꼭짓점은 서로 다른 분할 성분에 속한다. 즉, Γ의 색칠수가 k 이하이어야 한다.
k=2일 때, 이를 '''이분 그래프'''라고 한다. k=3일 때는 '''삼분 그래프'''라고 한다.
3. 성질
임의의 유한 그래프에 대해 다음 두 조건은 서로 동치이다.
- 이분 그래프이다.
- 홀수 길이의 순환이 존재하지 않는다.
특히, 홀수 길이의 순환 그래프는 이분 그래프가 될 수 없다.
이분 그래프의 색칠수는 2 이하이므로, 비징의 정리에 따라 이분 그래프는 항상 1종 그래프이다. (꼭짓점의 최대 차수가 1 이하인 그래프는 자명하게 1종 그래프이다.)
- 이분 그래프의 최대 매칭은 다항 시간에 구할 수 있다. (최대 흐름 문제 참조)
- 트리는 이분 그래프이다.
- 사이클 그래프는 정점이 짝수 개인 경우에만 이분 그래프이다.
- 쾨니그의 정리: 이분 그래프에서 최대 매칭의 변의 수는 최소 정점 덮개의 정점 수와 같다.
3. 1. 판별 알고리즘
주어진 그래프가 이분 그래프인지 확인하는 것은 깊이 우선 탐색(DFS) 또는 너비 우선 탐색(BFS)을 사용하여 선형 시간(''O''(|''V''|+|''E''|)) 내에 가능하다.깊이 우선 탐색을 이용할 경우, 각 정점을 이웃 정점과 다른 색으로 칠하면서 모순 발생 여부를 확인한다.[28] 각 정점에 깊이 우선 탐색 트리의 부모와 다른 색상을 할당하며, 색상은 전위 순회로 할당된다. 깊이 우선 탐색 숲에서 숲이 아닌 가장자리의 두 끝점 중 하나가 다른 끝점의 조상일 때, 두 정점이 다른 색상을 갖는지 확인해야 한다. 그렇지 않으면 조상에서 자손으로 가는 숲의 경로와 잘못 색칠된 가장자리가 함께 홀수 사이클을 형성하며, 그래프가 이분 그래프가 아니라는 결과와 함께 알고리즘에서 반환된다.[28]
너비 우선 탐색을 이용할 경우, 정점이 색칠될 때 이전에 색칠된 정점과 같은 색으로 연결된 간선이 있는지 확인하고, 있다면 홀수 사이클을 찾는다.[29] 이전에 색칠된 정점과 같은 색으로 연결된 가장자리가 존재한다면, 이 가장자리와 두 끝점을 해당 최소 공통 조상에 연결하는 너비 우선 탐색 숲의 경로가 홀수 사이클을 형성한다.[29]
3. 2. 쾨니히의 정리와 완전 그래프
최소 정점 덮개의 크기는 최대 매칭의 크기와 같은데, 이것이 쾨니그의 정리이다.[18][19] 이 정리의 또 다른 동치 형태는 최대 독립 집합의 크기와 최대 매칭의 크기를 더한 것이 정점의 수와 같다는 것이다. 고립 정점이 없는 모든 그래프에서 최소 변 덮개의 크기에 최대 매칭의 크기를 더한 것은 정점의 수와 같다.[20] 이 등식을 쾨니그의 정리와 결합하면 이분 그래프에서 최소 변 덮개의 크기가 최대 독립 집합의 크기와 같고, 최소 변 덮개의 크기에 최소 정점 덮개의 크기를 더한 것이 정점의 수와 같다는 사실을 알 수 있다.모든 이분 그래프, 모든 이분 그래프의 여 그래프, 모든 이분 그래프의 선 그래프, 그리고 모든 이분 그래프의 선 그래프의 여 그래프는 모두 완전 그래프이다. 이분 그래프의 완전성은 쉽게 알 수 있지만(색칠수는 2이고 최대 클릭의 크기도 2이다), 이분 그래프의 여 그래프의 완전성은 덜 자명하며 쾨니그의 정리의 또 다른 재진술이다. 이것은 완전 그래프의 초기 정의를 유도한 결과 중 하나였다.[21] 완전 그래프의 선 그래프의 여 그래프의 완전성은 쾨니그의 정리의 또 다른 재진술이며, 선 그래프 자체의 완전성은 모든 이분 그래프가 최대 차수와 같은 수의 색상을 사용하는 변 색칠을 가진다는 쾨니그의 이전 정리의 재진술이다.
강 완전 그래프 정리에 따르면, 완전 그래프는 이분 그래프와 유사한 금지 그래프 특성을 갖는다. 그래프가 이분 그래프인 것은 그래프가 홀수 사이클을 부분 그래프로 갖지 않을 때만 해당하며, 그래프가 완전 그래프인 것은 그래프가 홀수 사이클 또는 그 여 그래프를 유도된 부분 그래프로 갖지 않을 때만 해당한다. 이분 그래프, 이분 그래프의 선 그래프, 그리고 이들의 여 그래프는 강 완전 그래프 정리의 증명에 사용된 완전 그래프의 다섯 가지 기본 클래스 중 네 가지를 형성한다.[22]
3. 3. 차수
정점과 인접한 정점의 수는 차수라고 하며, 로 표시한다. 이분 그래프에 대한 차수 합 공식은 다음과 같다.[24]:
이분 그래프의 차수열은 두 부분 와 의 차수를 각각 포함하는 두 개의 목록 쌍이다. 예를 들어, 완전 이분 그래프 ''K''3,5는 차수열 를 갖는다. 동형 이분 그래프는 동일한 차수열을 갖는다. 그러나 차수열은 일반적으로 이분 그래프를 고유하게 식별하지 않으며, 경우에 따라 동형이 아닌 이분 그래프가 동일한 차수열을 가질 수 있다.
이분 그래프 실현 문제는 주어진 차수열을 갖는 단순 이분 그래프를 찾는 문제이다. (꼬리가 0인 경우는 방향 그래프에 적절한 수의 고립된 정점을 추가하여 사소하게 실현되므로 무시할 수 있다.)
3. 4. 하이퍼그래프 및 유향 그래프와의 관계
이분 그래프 의 인접 행렬은 인접한 정점 쌍에는 1, 인접하지 않은 정점에는 0을 갖는 크기의 (0,1) 행렬이다.[25] 이분 인접 행렬은 이분 그래프, 하이퍼그래프, 유향 그래프 간의 동치 관계를 설명하는 데 사용될 수 있다.하이퍼그래프는 무향 그래프처럼 정점과 변을 갖지만, 변이 정확히 두 개의 끝점을 가져야 하는 대신 임의의 정점 집합이 될 수 있는 조합 구조이다. 이분 그래프 는 U|U영어가 하이퍼그래프의 정점 집합이고, V|V영어가 하이퍼 모서리 집합이며, E|E영어에 하이퍼그래프 정점 v|v영어에서 하이퍼그래프 변 e|e영어로의 변이 v|v영어가 e|e영어의 끝점 중 하나일 때 정확히 포함되는 하이퍼그래프를 모델링하는 데 사용될 수 있다. 이러한 대응 관계에서 이분 그래프의 이분 인접 행렬은 해당 하이퍼그래프의 인접 행렬과 정확히 일치한다. 이분 그래프와 하이퍼그래프 간의 이러한 대응 관계의 특별한 경우로, 모든 멀티그래프 (동일한 두 정점 사이에 두 개 이상의 변이 있을 수 있는 그래프)는 일부 하이퍼 모서리가 동일한 끝점 집합을 갖는 하이퍼그래프로 해석될 수 있으며, 다중 인접이 없고 이분 분할의 한쪽 정점이 모두 차수 2를 갖는 이분 그래프로 표현된다.[26]
인접 행렬의 유사한 재해석은 유향 그래프 (주어진 수의 레이블이 지정된 정점에서 자기 루프 허용)와 균형 이분 그래프 간의 일대일 대응 관계를 보여주는 데 사용될 수 있다. 여기서 균형 이분 그래프는 이분 분할의 양쪽에 동일한 수의 정점을 갖는 그래프를 의미한다. 유향 그래프의 인접 행렬은 n|n영어개의 정점을 갖는 크기의 모든 (0,1) 행렬일 수 있으며, 이를 이분 분할의 각 측면에 n|n영어개의 정점을 갖는 이분 그래프의 인접 행렬로 재해석할 수 있다.[27] 이 구성에서 이분 그래프는 유향 그래프의 이분 이중 덮개이다.
4. 예
0분 그래프는 공 그래프(꼭짓점과 변이 없는 그래프) 밖에 없다. 1분 그래프는 변이 없는 이산 그래프와 같다.
모든 나무는 순환이 없으므로 이분 그래프이다. 짝수 길이의 순환은 이분 그래프이지만, 홀수 길이의 순환은 이분 그래프가 아니다.
이분 그래프는 두 가지 다른 종류의 대상 간의 관계를 나타내는 데 유용하다. 예를 들어, 축구 선수와 클럽 간의 관계를 나타내는 그래프에서 선수가 해당 클럽에서 뛴 적이 있다면 선수와 클럽 사이에 간선을 연결하는 것은 사회 연결망 분석에서 사용되는 이분 그래프의 한 유형인 ''소속 네트워크''의 예시이다.[6]
이분 그래프가 나타나는 또 다른 예는 철도 최적화 문제이다. 이 문제는 모든 열차가 선택된 정류장 중 적어도 하나를 방문하도록 하면서 가능한 가장 작은 집합의 기차역을 찾는 문제이다. 이 문제는 각 열차와 역에 정점을 두고, 각 역과 해당 역에 정차하는 열차를 간선으로 연결하는 이분 그래프에서 지배 집합 문제로 나타낼 수 있다.[7]
다른 예시는 화폐학 분야에서 찾을 수 있다. 고대 동전은 디자인의 두 가지 양각(앞면과 뒷면)을 사용하여 만들어진다. 화폐학자들이 동전 생산을 나타내기 위해 제작하는 차트는 이분 그래프이다.[8]
더 추상적인 예는 다음과 같다.
- 모든 트리는 이분 그래프이다.[3]
- 정점의 수가 짝수인 사이클 그래프는 이분 그래프이다.[3]
- 모든 평면 그래프의 면의 길이가 모두 짝수이면 이분 그래프이다.[9]
- ''m''과 ''n''개의 정점을 갖는 완전 이분 그래프 ''Kn,m''은 인 이분 그래프이다. 여기서 ''U''와 ''V''는 각각 크기가 ''m''과 ''n''인 서로소 집합이며, ''E''는 ''U''의 모든 정점을 ''V''의 모든 정점과 연결한다. 따라서 ''Km,n''은 ''mn''개의 간선을 갖는다.[11]
- 하이퍼큐브 그래프, 부분 큐브, 중앙값 그래프는 이분 그래프이다.
4. 1. 완전 k분 그래프
집합 의 조각 분할:
가 주어졌다고 하자. 이 집합의 분할에 대응하는 '''완전 분 그래프'''(complete -partite graph영어)는 위와 같은 분할에 대하여 분 그래프를 이루는, 가장 변을 많이 갖는 그래프이다. 즉, 그 변의 집합은 다음과 같은 꼴이다.
:
5. 응용
이분 그래프는 서로 다른 두 종류의 객체 간의 관계를 모델링할 때 유용하게 사용된다.
- 사회 연결망 분석: 축구 선수와 클럽 간의 관계를 나타내는 그래프는 사회 연결망 분석에서 사용되는 이분 그래프의 한 예시이다. 선수가 해당 클럽에서 뛴 적이 있다면 선수와 클럽 사이에 간선을 연결한다.[6]
- 철도 최적화 문제: NP-완전 문제인 철도 최적화 문제는 이분 그래프를 이용하여 지배 집합 문제로 모델링할 수 있다. 이 문제는 주어진 열차와 정류장 시간표에서 모든 열차가 선택된 정류장 중 적어도 하나를 방문하도록 하는 최소 크기의 정류장 집합을 찾는 것이다. 각 열차와 역에 정점을 두고, 각 역에 정차하는 열차 쌍에 간선을 갖는 이분 그래프를 구성하면, 이 문제는 지배 집합 문제로 변환된다.[7]
- 화폐학: 고대 동전은 앞면과 뒷면, 두 가지 양각을 사용하여 만들어지는데, 화폐학자들이 동전 생산을 나타내는 차트는 이분 그래프로 표현된다.[8]
이 외에도 다음과 같은 추상적인 예시들이 있다.
- 모든 트리는 이분 그래프이다.[3]
- 정점의 수가 짝수인 사이클 그래프는 이분 그래프이다.[3]
- 모든 평면 그래프 중 각 면의 길이가 모두 짝수인 경우는 이분 그래프이다. 격자 그래프와 정사각형 그래프가 이에 해당한다.[9]
- 완전 이분 그래프 ''Kn,m''은 ''m''개와 ''n''개의 정점을 갖는 두 그룹 사이의 모든 연결을 나타내는 그래프이다.[11]
- 하이퍼큐브 그래프, 부분 큐브, 중앙값 그래프는 이분 그래프이며, 비트 벡터를 이용하여 표현할 수 있다.[13]
이분 그래프는 부호 이론에서 채널에서 수신된 부호어를 해독하는 데 사용된다. 요인 그래프와 태너 그래프가 그 예시이다.[40]
페트리 넷은 동시 시스템 분석 및 시뮬레이션에 사용되는 도구이며, 이분 유향 그래프로 모델링된다.[42]
사영 기하학에서 레비 그래프는 배치 (기하학)의 점과 선 사이의 관계를 모델링하는 데 사용되는 이분 그래프이다.[43]
5. 1. 사회 연결망 분석
축구 선수와 클럽의 그래프에서, 선수가 해당 클럽에서 뛴 적이 있다면 선수와 클럽 사이에 간선을 두는 것은 사회 연결망 분석에서 사용되는 이분 그래프의 한 유형인 ''소속 네트워크''의 자연스러운 예이다.[6]5. 2. 철도 최적화 문제
NP-완전 문제인 철도 최적화 문제는 이분 그래프를 이용하여 지배 집합 문제로 모델링할 수 있다. 이 문제의 입력은 열차와 정류장의 시간표이고, 목표는 모든 열차가 선택된 정류장 중 적어도 하나를 방문하도록 하면서 가능한 가장 작은 집합의 기차역을 찾는 것이다. 각 열차와 각 역에 정점을 두고, 각 역과 해당 역에 정차하는 열차 쌍에 간선을 갖는 이분 그래프를 구성하면, 이 문제는 지배 집합 문제로 변환된다.[7]5. 3. 화폐학
고대 동전은 디자인의 두 가지 양각(앞면과 뒷면)을 사용하여 만들어진다. 화폐학자들이 동전 생산을 나타내기 위해 제작하는 차트는 이분 그래프이다.[8]5. 4. 기타 응용
이분 그래프는 서로 다른 두 종류의 객체 간의 관계를 모델링할 때 유용하게 사용된다. 예를 들어, 축구 선수와 클럽 간의 관계를 나타내는 그래프는 사회 연결망 분석에서 사용되는 이분 그래프의 한 예시이다.[6]이분 그래프는 철도 최적화 문제에도 응용될 수 있다. 이 문제는 주어진 열차와 정류장 시간표에서 모든 열차가 선택된 정류장 중 적어도 하나를 방문하도록 하는 최소 크기의 정류장 집합을 찾는 문제이다. 이 문제는 이분 그래프를 이용하여 지배 집합 문제로 모델링할 수 있다.[7]
화폐학에서도 이분 그래프가 활용된다. 고대 동전은 앞면과 뒷면, 두 가지 양각을 사용하여 만들어지는데, 화폐학자들이 동전 생산을 나타내는 차트는 이분 그래프로 표현된다.[8]
이 외에도 다음과 같은 추상적인 예시들이 있다.
- 모든 트리는 이분 그래프이다.[3]
- 정점의 수가 짝수인 사이클 그래프는 이분 그래프이다.[3]
- 모든 평면 그래프 중 각 면의 길이가 모두 짝수인 경우는 이분 그래프이다.[9] 격자 그래프와 정사각형 그래프가 이에 해당한다.[10]
- 완전 이분 그래프 ''Kn,m''은 ''m''개와 ''n''개의 정점을 갖는 두 그룹 사이의 모든 연결을 나타내는 그래프이다.[11]
- 하이퍼큐브 그래프, 부분 큐브, 중앙값 그래프는 이분 그래프이며, 비트 벡터를 이용하여 표현할 수 있다.[13]
이분 그래프는 부호 이론에서 채널에서 수신된 부호어를 해독하는 데 사용된다. 요인 그래프와 태너 그래프가 그 예시이다.[40]
페트리 넷은 동시 시스템 분석 및 시뮬레이션에 사용되는 도구이며, 이분 유향 그래프로 모델링된다.[42]
사영 기하학에서 레비 그래프는 배치 (기하학)의 점과 선 사이의 관계를 모델링하는 데 사용되는 이분 그래프이다.[43]
6. 알고리즘
홀수 사이클 횡단은 그래프 ''G'' = (''V'',''E'')와 숫자 ''k''가 주어졌을 때, ''G''에서 제거하면 결과 그래프가 이분 그래프가 되는 꼭짓점 집합이 있는지 묻는 NP-완전 알고리즘 문제이다.[31] 이 문제는 고정 매개변수 추적 가능하며, 그래프 크기의 다항 함수에 ''k''의 더 큰 함수를 곱한 값으로 실행 시간을 제한할 수 있는 알고리즘이 있다.[32] "홀수 사이클 횡단"이라는 이름은 그래프가 홀수 사이클이 없는 경우에만 이분 그래프가 된다는 사실에서 유래했다. 따라서 이분 그래프를 얻기 위해 그래프에서 꼭짓점을 삭제하려면 "모든 홀수 사이클을 치는" 즉, 소위 홀수 사이클 횡단 집합을 찾아야 한다.
엣지 이분화(edge bipartization) 문제는 그래프를 이분 그래프로 만들기 위해 가능한 한 적은 수의 간선을 삭제하는 알고리즘 문제이며, 그래프 수정 알고리즘에서도 중요한 문제이다. 이 문제 또한 고정 매개변수 추적 가능하며, O영어(2k m2) 시간에 해결할 수 있다.[33] 여기서 ''k''는 삭제할 간선의 수이고 ''m''은 입력 그래프의 간선 수이다.
그래프에서 매칭은 두 개의 끝점을 공유하지 않는 간선의 부분 집합이다.[34] 다항 시간 알고리즘은 최대 매칭(가능한 많은 간선을 사용하는 매칭 찾기), 최대 가중치 매칭, 안정 결혼 문제를 포함하여 매칭에 대한 많은 알고리즘 문제에 대해 알려져 있다. 많은 경우, 매칭 문제는 이분 그래프에서 비이분 그래프보다 해결하기 더 간단하며,[35] 최대 기수 매칭에 대한 호프크로프트-카프 알고리즘과 같은 많은 매칭 알고리즘은 이분 입력에서만 올바르게 작동한다.[36]
일반적인 예로, 모든 사람이 모든 직업에 적합하지 않은 상황에서, 사람들 집합이 직업 집합에서 직업을 구하는 상황을 생각해 보자. 이 상황은 각 구직자를 각 적합한 직업과 연결하는 간선이 있는 이분 그래프로 모델링할 수 있다.[37] 완전 매칭은 모든 구직자를 동시에 만족시키고 모든 직업을 채우는 방법을 설명한다. 홀의 결혼 정리는 완전 매칭을 허용하는 이분 그래프의 특성을 제공한다. 전국 레지던트 매칭 프로그램은 그래프 매칭 방법을 적용하여 미국 의대생 구직자와 병원 레지던시 직업에 대한 이 문제를 해결한다.[38]
둘마지-멘델존 분해는 최대 매칭을 찾는 데 유용한 이분 그래프의 구조적 분해이다.[39]
6. 1. 홀수 사이클 횡단
홀수 사이클 횡단은 그래프 ''G'' = (''V'',''E'')와 숫자 ''k''가 주어졌을 때, ''G''에서 제거하면 결과 그래프가 이분 그래프가 되는 꼭짓점 집합이 있는지 묻는 NP-완전 알고리즘 문제이다.[31] 이 문제는 고정 매개변수 추적 가능하며, 그래프 크기의 다항 함수에 ''k''의 더 큰 함수를 곱한 값으로 실행 시간을 제한할 수 있는 알고리즘이 있다.[32] "홀수 사이클 횡단"이라는 이름은 그래프가 홀수 사이클이 없는 경우에만 이분 그래프가 된다는 사실에서 유래했다. 따라서 이분 그래프를 얻기 위해 그래프에서 꼭짓점을 삭제하려면 "모든 홀수 사이클을 치는" 즉, 소위 홀수 사이클 횡단 집합을 찾아야 한다. 그림에서 그래프의 모든 홀수 사이클에는 파란색(가장 아래쪽) 꼭짓점이 포함되어 있으므로 해당 꼭짓점을 제거하면 모든 홀수 사이클이 제거되고 이분 그래프가 남는다.
엣지 이분화(edge bipartization) 문제는 그래프를 이분 그래프로 만들기 위해 가능한 한 적은 수의 모서리를 삭제하는 알고리즘 문제이며, 그래프 수정 알고리즘에서도 중요한 문제이다. 이 문제 또한 고정 매개변수 추적 가능하며, O|오영어(2k m2) 시간에 해결할 수 있다.[33] 여기서 ''k''는 삭제할 모서리의 수이고 ''m''은 입력 그래프의 모서리 수이다.
6. 2. 간선 이분화 (Edge Bipartization)
간선 이분화(edge bipartization) 문제는 그래프를 이분 그래프로 만들기 위해 가능한 한 적은 수의 간선을 삭제하는 알고리즘 문제이며, 그래프 수정 알고리즘에서도 중요한 문제이다.[33] 이 문제 또한 고정 매개변수 추적 가능하며, O영어(2k m2) 시간에 해결할 수 있다.[33] 여기서 ''k''는 삭제할 간선의 수이고 ''m''은 입력 그래프의 간선 수이다.6. 3. 매칭 (Matching)
그래프에서 매칭은 두 개의 끝점을 공유하지 않는 간선의 부분 집합이다.[34] 다항 시간 알고리즘은 최대 매칭(가능한 많은 간선을 사용하는 매칭 찾기), 최대 가중치 매칭, 안정 결혼 문제를 포함하여 매칭에 대한 많은 알고리즘 문제에 대해 알려져 있다. 많은 경우, 매칭 문제는 이분 그래프에서 비이분 그래프보다 해결하기 더 간단하며,[35] 최대 기수 매칭에 대한 호프크로프트-카프 알고리즘과 같은 많은 매칭 알고리즘은 이분 입력에서만 올바르게 작동한다.[36]간단한 예로, 모든 사람이 모든 직업에 적합하지 않은 상황에서, 사람들 의 집합이 직업 의 집합에서 직업을 구한다고 가정해 보자. 이 상황은 각 구직자를 각 적합한 직업과 연결하는 간선이 있는 이분 그래프 로 모델링할 수 있다.[37] 완전 매칭은 모든 구직자를 동시에 만족시키고 모든 직업을 채우는 방법을 설명한다. 홀의 결혼 정리는 완전 매칭을 허용하는 이분 그래프의 특성을 제공한다. 전국 레지던트 매칭 프로그램은 그래프 매칭 방법을 적용하여 미국 의대생 구직자와 병원 레지던시 직업에 대한 이 문제를 해결한다.[38]
둘마지-멘델존 분해는 최대 매칭을 찾는 데 유용한 이분 그래프의 구조적 분해이다.[39]
참조
[1]
서적
Graph Theory
http://diestel-graph[...]
Springer
2012-02-27
[2]
서적
Bipartite Graphs and their Applications
https://archive.org/[...]
Cambridge University Press
[3]
서적
Mathematics: A Discrete Introduction
https://books.google[...]
Cengage Learning
[4]
서적
Chromatic Graph Theory
https://books.google[...]
CRC Press
[5]
간행물
[6]
서적
Social Network Analysis: Methods and Applications
https://books.google[...]
Cambridge University Press
[7]
서적
Invitation to Fixed Parameter Algorithms
Oxford University Press
[8]
서적
Judaea and Rome in Coins 65 BCE – 135 CE: Papers Presented at the International Conference hosted by Spink, 13th – 14th September 2010
Spink & Son
[9]
서적
The Mathematical Coloring Book
Springer-Verlag
[10]
논문
Combinatorics and geometry of finite and infinite squaregraphs
[11]
간행물
[12]
논문
Cycle systems in the complete bipartite graph minus a one-factor
[13]
서적
Graphs and Cubes
Springer
[14]
간행물
[15]
서적
Digraphs: Theory, Algorithms and Applications
https://www.cs.rhul.[...]
Springer
2023-01-02
[16]
논문
A proof of McKee's Eulerian-bipartite characterization
[17]
서적
Algebraic Graph Theory
https://books.google[...]
Cambridge University Press
[18]
논문
Gráfok és mátrixok
[19]
서적
Graph Theory and Its Applications
https://books.google[...]
CRC Press
[20]
서적
A First Course in Graph Theory
https://books.google[...]
Courier Dover Publications
[21]
서적
Modern Graph Theory
https://books.google[...]
Springer
[22]
논문
The strong perfect graph theorem
[23]
웹사이트
Matchings
http://www.sfu.ca/~m[...]
Simon Fraser University
[24]
서적
Combinatorial Problems and Exercises
https://books.google[...]
Elsevier
[25]
간행물
[26]
간행물
Hypergraph
[27]
논문
Bigraphs versus digraphs via matrices
[28]
서적
Algorithms in Java, Part 5: Graph Algorithms
Addison Wesley
[29]
서적
Algorithm Design
Addison Wesley
[30]
논문
Testing bipartiteness of geometric intersection graphs
[31]
간행물
Proceedings of the 10th ACM Symposium on Theory of Computing (STOC '78)
[32]
논문
Finding odd cycle transversals
[33]
논문
Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
[34]
서적
Network Flows: Theory, Algorithms, and Applications
Prentice Hall
[35]
간행물
[36]
논문
An ''n''5/2 algorithm for maximum matchings in bipartite graphs
[37]
harvtxt
[38]
간행물
Are Medical Students Meeting Their (Best Possible) Match?
http://www.siam.org/[...]
2003-04
[39]
harvtxt
[40]
서적
Error Correction Coding: Mathematical Methods and Algorithms
https://books.google[...]
John Wiley & Sons
[41]
harvtxt
[42]
서적
Introduction to Discrete Event Systems
https://books.google[...]
Springer
[43]
서적
Configurations of Points and Lines
https://books.google[...]
American Mathematical Society
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com