[그래프] 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)\ge w(x,y)\mathrm{\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)

---