그래프의 여러 얼굴

핵심 개념

지금까지 본 단순 그래프(simple graph)는 두 노드 사이에 엣지가 많아야 하나이고, 자기 자신으로 돌아오는 엣지가 없습니다. 실제 데이터는 이 조건을 자주 벗어납니다. 어떤 종류의 그래프를 쓸지 정하는 일은 ‘어떤 사실을 잃지 않고 적을 것인가’를 정하는 일이며, 이 결정이 저장 방식과 질의 방식을 함께 바꿉니다.

이분 그래프(bipartite graph)는 노드가 두 종류로 나뉘고, 엣지가 항상 서로 다른 종류를 잇는 그래프입니다. 사람–프로젝트, 학생–수업, 고객–상품이 대표적입니다. ‘같은 프로젝트를 한 사람끼리’의 관계가 필요하면 프로젝트를 거치는 두 홉을 사람 사이 엣지로 바꾼 투영(projection)을 만듭니다. 투영하면 어느 프로젝트를 함께 했는지, 몇 개를 함께 했는지는 사라집니다.

다중 그래프(multigraph)는 같은 두 노드 사이에 엣지를 여러 개 허용합니다. 민수와 지아가 같은 반이면서 같은 동아리라면 엣지 두 개로 적어 관계의 종류를 구분합니다. 자기 루프(self-loop)는 노드가 자기 자신과 이어진 엣지로, 자기 논문을 인용하는 저자나 자기 계좌로의 이체 같은 경우에 생깁니다.

하이퍼그래프(hypergraph)는 엣지 하나가 셋 이상의 노드를 한꺼번에 잇습니다. 민수·지아·서준이 함께한 회의를 하이퍼엣지 하나로 적으면 ‘세 명이 한자리에 있었다’는 사실이 그대로 남습니다. 쌍 엣지 세 개로 쪼개면 세 번의 따로 만남과 구분되지 않습니다. 회의를 노드로 두고 참석자를 잇는 방법은 하이퍼그래프를 이분 그래프로 바꾸는 흔한 기법이며, 42회차의 이벤트 노드로 이어집니다.

작은 예제로 따라가기

이번에는 직접 풀어 보세요

정답을 보기 전에 계산과 이유를 적어 보세요. 해설과 비교하고 확인 표시를 남기면 완료할 수 있습니다.

풀이와 확인 표시는 이 브라우저에 저장됩니다.