[자료구조] 이분그래프 (Bipartite Graph)

이분그래프란?

• 2가지 특성으로 나눌 수 있는, 이분되어 있는 그래프
• vertex를 2개의 그룹으로 나눌 수 있는데, 같은 그룹의 vertex끼리는 인접할 수 없는 그래프

 

특징

• 하나의 edge의 양 끝 vertex는 서로 다른 그룹에 속해 있어야 함
• 같은 그룹의 vertex끼리는 하나의 edge로 이어질 수 없음
• cycle이 발생했을 때, 그 cycle을 잇는 edge의 개수는 짝수여야 함
• edge가 없고 vertex만 있는 경우도 이분그래프

 

응용

• 각 그룹에 포함되어 있는 원소끼리의 관계를 나타낼 수 있다
  • 학생 - 수업 : 학생들이 어떤 수업을 듣고 있는지, 각각의 수업을 듣고 있는 학생들은 누군지 관계를 나타낼 수  있다
  • 구직자 - 선호 회사 : 구직자가 어떤 회사를 선호하는지 관계를 나타낼 수 있다
  • 유저 - 선호 영화 : 각 유저들이 어떤 영화를 선호하는지 관계를 나타낼 수 있다
• 두 그룹간의 다양한 관계를 나타내는 이분그래프와 매칭 알고리즘을 이용해 관계를 확인할 수 았을 뿐만 아니라 매칭 프로그램, 추천 프로그램을 만들 수 있다
  • 학생 - 수업 : 각 학생들이 어떤 수업을 듣고 있는지 확인, 각 수업을 듣고 있는 학생들이 누군지 확인
  • 구직자 - 선호 회사 : 구직자 별 선호 회사를 확인하고 취업 확률이 높아지도록 구직자들에게 회사를 매칭시켜줌