[그래프] Feasible labeling 이란? (Graph labeling)

 

 

---

Feasible labeling 이란?

 

---

우선, 라벨링 한다는 것은 어떤 의미 일까요? (Labeling)

 

임의로 객체를 구별할 수 있는 무엇인가를 부여한다는 의미입니다.

예를 들어서, 딥러닝에서 학습하기위해 사용하는 정답 데이터들이 라벨링의 결과입니다.

 

---

그래프 표현 : 인접행렬(Adjacency matrix)

 

보통 그래프의 경우 인접행렬(Adjacency_matrix)로 표현하는 경우가 많습니다. 

• 행과 열의 index 로 각 정점(vertex)을 표현하게 됩니다.
• 행렬의 값(value)는 연결의 가중도(weight) 또는 연결 여부를 표현하게 됩니다.

---

그렇다면, 그래프에서 라벨링 한다는 것은 어떤 의미일까요? (Graph Labeling)

 

 

그래프_번호매김(Graph labeling)은 정수로 표현되는 라벨을 그래프의 모서리나 꼭짓점 또는 둘다에 붙이는 것을 의미합니다.

 

\(G=(V,E)\) 라고 정의된 수식에서,

 

Vertex labeling 의 경우 V 에서 라벨의 집합으로 가는 함수라고 할 수 있습니다.

Edge labeling 의 경우 E 에서 라벨의 집합으로 가는 함수라고 할 수 있습니다.

 

---

Feasible labeling 은 무엇인가요?

 

그래프 라벨링의 한 방법입니다.

우선 영어로된 정의는 다음과 같습니다.

[정의]
\((x)+l(y)\geq w(x,y)\ \forall x\in X,y\in Y\), where
 
\(X\) is the set of nodes on one side of the bipartite graph, \(Y\) is the other set of nodes, \(l(x)\) is the label of \(x\), etc., and \(w(x,y)\) is the weight of the edge between \(x\) and \(y\).

 

하나씩 이해해 봅시다.

 

\(X,Y\) : Bipartite_graph 의 각 집합(set)을 의미합니다. 

 

 

\(x \in X,y \in Y \) : 각 집합에서 뽑은 정점(vertex)를 \(x,y\)라고 합니다.

\(l(x)\) : 정점 \(x\) 에 부여하는 라벨 값

\(l(y)\) : 정점 \(y\) 에 부여하는 라벨 값

\(w(x,y)\) : 두 정점 \(x,y\) 를 연결한 edge의 weight 값

 

정리하자면,  

두개의 분리된 집합 \(X,Y\) 에서 각각 두 정점 \(x,y\) 을 뽑아서 라벨링을 할 건데,

두 정점을 각각 라벨링하여 합친 값(\((x)+l(y)\))이
두 정점 \(x,y\) 를 연결한 edge의 weight 값보다 크거나 같게 하겠다는 의미 입니다.

 

예시를 통해 알아봅시다.

 

간단한 feasible labeling 은 node(vertex)에 라벨링 하는 것을 의미합니다.

아래는 두 노드의 라벨링 값을 합친 것이 두 노드의 연결 weight 보다 크거나 같도록만 설정한 예시 입니다.

 

붉은색 값으로 노드에 대해서 라벨링을 진행했습니다.

모든 연결(edge) weight의 조건을 만족하여 라벨링이 진행된 것을 볼 수 있습니다.

 

---

Feasible Labeling 활용

Hungarian Algorithm을 통해 Bipartite Graph의 Perfect matching of maximum weight를 찾을 수 있습니다.

 

2022.04.12 - [SW/자료구조 & 알고리즘] - [알고리즘] Hungarian Maximum Matching Algorithm (Kuhn-Munkres algorithm)

---