무향 그래프편집자 확인

무향 그래프는 그래프 이론에서 가장 기본적인 형태의 그래프이다. 이는 정점들의 집합과 이들을 연결하는 간선들의 집합으로 구성되며, 일반적으로 G = (V, E)로 표기한다. 여기서 V는 정점의 집합을, E는 간선의 집합을 나타낸다. 무향 그래프의 핵심 특징은 간선에 방향이 없다는 점이다. 즉, 두 정점 u와 v를 연결하는 간선은 순서가 없는 쌍 {u, v} (또는 (u, v))로 표현되며, {u, v}와 {v, u}는 완전히 동일한 하나의 간선을 의미한다.

이러한 방향성의 부재는 무향 그래프가 상호적인 관계를 모델링하는 데 적합하게 만든다. 예를 들어, 소셜 네트워크에서 두 사람이 친구 관계라면, 이 관계는 양방향으로 동일하게 적용된다. 마찬가지로 도시들을 연결하는 도로망이나 컴퓨터들을 연결하는 통신 네트워크에서 물리적 연결은 일반적으로 양방향 통행이나 통신이 가능하므로 무향 그래프로 자연스럽게 표현할 수 있다. 이는 한 방향으로만 이동이 가능한 일방통행로나 웹 페이지 간의 하이퍼링크 관계를 표현하는 유향 그래프와 대비되는 점이다.

무향 그래프는 조합론과 이산수학의 중요한 연구 대상이며, 네트워크 분석, 데이터 구조, 알고리즘 설계 등 다양한 컴퓨터 과학 분야에서 광범위하게 활용된다. 간단한 구조에도 불구하고, 연결성, 경로, 사이클, 트리 등 풍부한 하위 개념과 문제들을 포함하고 있어 그래프 이론의 핵심 기초를 이룬다.

무향 그래프의 가장 핵심적인 특징은 간선에 방향이 없다는 점이다. 이는 두 정점 사이의 연결 관계가 상호적이며 양방향으로 해석됨을 의미한다. 예를 들어, 소셜 네트워크에서 두 사람이 '친구' 관계라면, 이 관계는 양쪽 모두에게 동등하게 적용된다. 이러한 특성 때문에 무향 그래프는 상호적인 관계를 모델링하는 데 적합하다.

수학적으로 무향 그래프의 간선은 순서가 없는 정점 쌍 {u, v}로 표현된다. 이 표기에서 {u, v}와 {v, u}는 완전히 동일한 간선을 가리킨다. 이는 유향 그래프에서 간선을 순서쌍 (u, v)로 표현하며, (u, v)와 (v, u)가 서로 다른 간선인 것과 대비된다. 따라서 무향 그래프의 인접 행렬은 대칭 행렬이 된다.

방향성의 부재는 그래프를 표현하는 자료구조와 알고리즘의 복잡도에 영향을 미친다. 인접 리스트를 구성할 때, 정점 u의 리스트에 v를 추가하면 반드시 정점 v의 리스트에도 u를 추가해야 전체 연결 관계를 정확히 표현할 수 있다. 또한 최단 경로 탐색이나 연결 요소 분석과 같은 많은 알고리즘에서 무향 그래프는 유향 그래프보다 간단한 가정을 바탕으로 설계될 수 있다.

이 기본 성질은 도로 네트워크(양방향 통행 도로), 통신 네트워크, 분자 구조 모델링 등 물리적이거나 논리적인 대칭적 연결을 표현하는 광범위한 응용 분야의 수학적 토대를 제공한다.

무향 그래프를 컴퓨터에서 처리하기 위해서는 적절한 자료 구조로 표현해야 한다. 가장 일반적으로 사용되는 두 가지 표현 방식은 인접 행렬과 인접 리스트이다.

인접 행렬은 정점의 개수를 n이라고 할 때, n x n 크기의 2차원 배열을 사용한다. 행렬의 i행 j열 원소는 정점 i와 정점 j 사이에 간선이 존재하는지 여부를 나타낸다. 무향 그래프에서는 간선 {i, j}가 존재할 경우, 행렬의 (i, j)와 (j, i) 위치 모두에 1(또는 가중치)을 저장하여 대칭 행렬이 된다. 이 방식은 두 정점 사이의 연결 관계를 상수 시간(O(1))에 확인할 수 있는 장점이 있지만, 정점 수에 비해 간선이 적은 희소 그래프의 경우 메모리 공간을 비효율적으로 사용한다.

반면, 인접 리스트는 각 정점마다 연결된 이웃 정점들의 목록(리스트)을 관리하는 방식이다. 예를 들어, 정점 v에 대한 리스트에는 v와 직접 연결된 모든 정점 u가 저장된다. 이 방법은 실제 존재하는 간선의 수에 비례하는 메모리만 사용하므로 공간 효율성이 높다. 특히 소셜 네트워크나 도로망처럼 연결이 상대적으로 적은 대규모 그래프를 표현할 때 유리하다. 다만, 두 정점이 연결되었는지 확인하려면 한 정점의 리스트를 선형 탐색해야 할 수 있어 인접 행렬에 비해 시간이 더 소요될 수 있다.

두 표현법의 선택은 해결하려는 문제의 특성에 따라 달라진다. 빈번한 연결 확인이 필요한 경우 인접 행렬이, 그래프 탐색 알고리즘이나 모든 간선을 순회하는 작업이 주를 이루는 경우 인접 리스트가 일반적으로 더 효율적이다. 많은 현대 그래프 알고리즘 라이브러리들은 기본적으로 공간 효율성을 고려하여 인접 리스트 기반의 표현을 채택하고 있다.

완전 그래프는 그래프 이론에서 매우 기본적이면서도 중요한 특수 형태의 무향 그래프이다. 완전 그래프는 주어진 정점 집합에 대해 가능한 모든 쌍의 정점 사이에 정확히 하나의 간선이 존재하는 그래프를 말한다. 즉, 그래프의 모든 정점 쌍이 서로 직접 연결되어 있다.

n개의 정점을 가진 완전 그래프는 보통 기호 K_n으로 표기한다. K_n의 간선의 수는 조합론 공식 n(n-1)/2로 계산된다. 이는 n개의 정점 중 서로 다른 두 개를 선택하는 조합의 수와 같다. 가장 작은 완전 그래프인 K_1은 간선이 없는 단일 정점이며, K_2는 두 정점을 연결하는 하나의 간선을 가진다. K_3는 정삼각형 모양의 삼각형을 이루고, K_4는 사면체의 모서리와 같이 모든 꼭짓점이 연결된 형태를 가진다.

완전 그래프는 이론적 연구나 알고리즘의 복잡도 분석에서 기준이 되는 모델로 자주 사용된다. 예를 들어, 완전 그래프에서의 최단 경로 문제나 여행하는 외판원 문제는 모든 정점 쌍이 직접 연결되어 있어 특수한 성질을 보인다. 또한 네트워크 이론에서 완전 연결은 이상적인 통신 네트워크를 모델링할 때 고려된다.

완전 그래프의 밀도는 1로, 가능한 최대의 연결성을 가진다. 이와 대조적으로 간선이 매우 적은 그래프는 희소 그래프라고 부른다. 완전 그래프의 대칭성과 단순한 구조는 그래프의 색칠 문제나 해밀턴 경로 존재성과 같은 다양한 그래프 이론 문제를 이해하는 데 핵심적인 역할을 한다.

연결 그래프는 그래프 내의 임의의 두 정점 사이에 경로가 존재하는 그래프를 말한다. 즉, 그래프가 하나의 컴포넌트로 이루어져 있어 모든 정점들이 서로 연결되어 있다. 반면, 비연결 그래프는 두 개 이상의 분리된 연결 요소로 구성된 그래프로, 서로 다른 연결 요소에 속한 정점들 사이에는 경로가 존재하지 않는다.

연결 그래프의 대표적인 예로는 트리나 완전 그래프가 있으며, 네트워크 분석에서 중요한 개념이다. 비연결 그래프는 서로 독립된 여러 개의 그래프 컴포넌트로 볼 수 있으며, 그래프 탐색 알고리즘을 실행하면 각 연결 요소별로 탐색이 이루어진다. 깊이 우선 탐색이나 너비 우선 탐색을 통해 그래프 내의 연결 요소의 개수를 쉽게 셀 수 있다.

실제 응용에서는 소셜 네트워크에서 서로 친구 관계로 연결된 사용자 집단을 찾거나, 통신망에서 고립된 장비 그룹을 식별하는 데 연결 요소 분석이 사용된다.

가중치 무향 그래프는 각 간선에 숫자 값인 가중치가 할당된 무향 그래프이다. 이 가중치는 두 정점 사이의 관계를 수치적으로 표현하며, 예를 들어 도로망에서 두 도시를 연결하는 도로의 길이, 통신망에서 두 노드 간의 대역폭이나 비용, 소셜 네트워크에서 두 사람 간의 친밀도 등을 나타낼 수 있다. 이러한 그래프는 네트워크 이론과 조합 최적화 문제를 모델링하는 데 핵심적으로 사용된다.

가중치 무향 그래프는 기본적인 무향 그래프의 표현 방식에 가중치 정보를 추가하여 표현한다. 인접 행렬을 사용할 경우, 행렬의 각 원소는 해당 두 정점을 연결하는 간선의 가중치를 저장하며, 간선이 존재하지 않으면 0이나 무한대(∞) 같은 특수 값으로 표시한다. 인접 리스트를 사용할 경우, 각 정점에 연결된 인접 정점과 함께 해당 간선의 가중치를 쌍으로 저장하여 표현한다.

가중치 무향 그래프에서 해결하는 대표적인 문제로는 최소 신장 트리 문제와 최단 경로 문제가 있다. 최소 신장 트리 문제는 모든 정점을 연결하는 간선의 가중치 합이 최소가 되는 부분 그래프를 찾는 것이며, 크루스칼 알고리즘이나 프림 알고리즘으로 해결한다. 최단 경로 문제는 특정 시작 정점에서 다른 모든 정점까지, 또는 두 정점 사이의 경로 중 가중치 합이 최소인 경로를 찾는 문제로, 다익스트라 알고리즘이 널리 사용된다. 이러한 알고리즘들은 물류, 통신, 교통 계획 등 다양한 분야의 실용적 문제 해결에 적용된다.

트리는 무향 그래프의 특수한 형태로, 사이클이 존재하지 않으면서 모든 정점이 연결된 그래프이다. 즉, 임의의 두 정점 사이에 정확히 하나의 경로만 존재하는 연결된 무향 그래프를 트리라고 정의한다. 이러한 성질 때문에 트리는 계층적 구조를 표현하거나 데이터를 효율적으로 조직화하는 데 널리 사용된다.

트리의 주요 성질로는 정점의 수가 V개일 때, 간선의 수는 항상 V-1개라는 점이 있다. 또한 트리에서 임의의 한 간선을 제거하면 그래프는 두 개의 연결 요소로 분리되며, 임의의 두 정점 사이에 새로운 간선을 하나 추가하면 정확히 하나의 사이클이 생성된다. 이러한 최소 연결성과 최대 비순환성은 트리를 그래프 이론의 핵심 구조로 만든다.

트리의 대표적인 예와 응용 분야는 다음과 같다.

트리는 알고리즘 설계와 자료 구조의 기초가 된다. 깊이 우선 탐색이나 너비 우선 탐색 과정에서 생성되는 탐색 트리는 그래프의 구조를 이해하는 데 도움을 주며, 힙이나 이진 탐색 트리와 같은 데이터 구조는 효율적인 데이터 접근과 관리를 가능하게 한다. 또한, 파일 시스템의 디렉토리 구조나 조직도는 트리로 자연스럽게 모델링될 수 있다.

이분 그래프는 그래프의 정점 집합을 두 개의 독립적인 부분 집합으로 나눌 수 있는 특수한 형태의 무향 그래프이다. 두 부분 집합을 각각 U와 V라고 할 때, 모든 간선은 U의 정점 하나와 V의 정점 하나를 연결하며, 같은 부분 집합 내의 두 정점 사이에는 간선이 존재하지 않는다. 즉, 그래프의 색칠 수가 2인 그래프로도 설명할 수 있다.

이분 그래프는 다양한 관계를 모델링하는 데 유용하다. 예를 들어, 구직자와 직무, 학생과 수업, 소셜 네트워크에서 사용자와 관심 그룹 사이의 연결을 표현할 때 자주 사용된다. 이러한 구조는 두 종류의 서로 다른 객체 간의 매칭 문제를 분석하는 데 적합하다.

이분 그래프가 가지는 중요한 성질 중 하나는 홀수 길이의 사이클을 포함하지 않는다는 점이다. 이 성질은 그래프가 이분 그래프인지 판별하는 데 사용될 수 있으며, 깊이 우선 탐색이나 너비 우선 탐색을 이용한 색칠을 통해 효율적으로 확인할 수 있다.

이분 그래프의 특수한 형태로 완전 이분 그래프가 있다. 이는 두 부분 집합 U와 V 사이의 모든 가능한 간선이 존재하는 그래프를 말하며, 표기법으로 K_{m,n}을 사용한다. 여기서 m과 n은 각 부분 집합의 정점 개수를 나타낸다.

깊이 우선 탐색은 그래프의 모든 정점을 체계적으로 방문하기 위한 기본적인 그래프 순회 알고리즘 중 하나이다. 이 방법은 한 정점에서 시작하여, 가능한 한 깊게, 즉 더 이상 새로운 인접 정점이 없을 때까지 탐색을 진행한 후, 되돌아가서 다른 경로를 탐색하는 방식을 취한다. 스택 자료구조를 명시적으로 사용하거나 재귀 호출을 통해 구현되는 것이 일반적이다.

알고리즘의 동작 과정은 다음과 같다. 먼저 시작 정점을 방문하고 방문했다는 표시를 한다. 그리고 해당 정점에 인접한 아직 방문하지 않은 정점 중 하나를 선택해 그 정점으로 이동하여 같은 과정을 재귀적으로 반복한다. 더 이상 방문할 수 있는 인접 정점이 없으면, 이전 정점으로 돌아가서 다른 인접 정점을 탐색한다. 이 과정은 모든 정점을 방문할 때까지 계속된다. 이 방식은 트리의 전위 순회와 유사한 패턴을 보인다.

깊이 우선 탐색은 다양한 그래프 문제 해결에 활용된다. 예를 들어, 무향 그래프가 연결 그래프인지 판별하거나, 그래프 내의 연결 요소를 찾는 데 사용할 수 있다. 또한 사이클의 존재 여부를 검출하거나, 위상 정렬 문제를 해결하는 데에도 적용된다. 특히 미로 탐색이나 퍼즐 해결과 같은 백트래킹이 필요한 문제에서 유용하게 쓰인다.

이 알고리즘의 시간 복잡도는 인접 리스트로 그래프를 표현했을 경우 정점 수 V와 간선 수 E에 대해 O(V+E)이다. 이는 각 정점과 간선을 한 번씩만 처리하기 때문이다. 공간 복잡도는 재귀 호출 스택의 깊이에 영향을 받으며, 최악의 경우 O(V)이다.

너비 우선 탐색은 그래프 또는 트리의 모든 정점을 체계적으로 방문하는 그래프 순회 알고리즘이다. 이 알고리즘은 시작 정점에서 가장 가까운, 즉 거리가 같은 정점들을 우선적으로 탐색하는 방식으로 동작한다. 깊이 우선 탐색이 한 방향으로 깊게 탐색하는 것과 대비되며, 주로 최단 경로를 찾거나 그래프의 연결 구조를 분석하는 데 활용된다.

알고리즘은 일반적으로 큐 자료구조를 사용하여 구현된다. 시작 정점을 큐에 넣고 방문 표시를 한 후, 큐가 빌 때까지 정점을 하나씩 꺼내면서 그 정점에 인접한 아직 방문하지 않은 모든 정점을 큐에 추가하는 과정을 반복한다. 이 과정을 통해 시작 정점으로부터의 거리(간선의 개수)가 1인 정점, 2인 정점 순으로 레벨별로 탐색이 이루어진다.

너비 우선 탐색의 시간 복잡도는 그래프를 인접 리스트로 표현했을 때 O(V+E)이다. 여기서 V는 정점의 수, E는 간선의 수를 의미한다. 이는 각 정점과 간선을 정확히 한 번씩만 검사하기 때문에 가능하다. 공간 복잡도는 큐에 저장될 수 있는 최대 정점 수에 비례한다.

이 알고리즘은 가중치가 없는 그래프에서 두 정점 사이의 최단 경로를 찾는 문제, 연결 요소를 구분하는 문제, 이분 그래프 판별 문제 등 다양한 응용 분야에서 핵심적인 역할을 한다. 또한 네트워크 분석이나 퍼즐 해결과 같은 실제 문제 해결에도 널리 적용된다.

최소 신장 트리는 무향 그래프에서 파생되는 중요한 개념이다. 주어진 연결된 무향 그래프의 모든 정점을 포함하면서, 사용된 간선의 가중치 합이 최소가 되는 부분 그래프를 의미한다. 이때 결과물은 사이클이 없는 트리 구조를 이루며, 이를 최소 신장 트리라고 부른다. 이 개념은 네트워크 설계, 통신 인프라 구축, 클러스터링 등 다양한 최적화 문제에 폭넓게 응용된다.

최소 신장 트리를 구하는 대표적인 알고리즘으로는 크루스칼 알고리즘과 프림 알고리즘이 있다. 크루스칼 알고리즘은 모든 간선을 가중치 순으로 정렬한 후, 사이클을 형성하지 않으면서 가장 가중치가 작은 간선부터 차례로 선택하는 탐욕 알고리즘 방식을 따른다. 반면 프림 알고리즘은 하나의 정점에서 시작하여 트리를 점점 확장해 나가는 방식을 사용한다. 두 알고리즘 모두 효율적으로 최소 신장 트리를 찾을 수 있다.

최소 신장 트리는 그래프가 연결되어 있어야 정의될 수 있으며, 그래프에 여러 개의 연결 요소가 존재하는 경우 각 연결 요소에 대해 별도의 최소 신장 트리를 구할 수 있다. 또한 모든 간선의 가중치가 동일한 경우, 최소 신장 트리는 단순히 간선의 수가 (정점 수 - 1)인 신장 트리가 된다. 이 개념은 네트워크 이론과 조합 최적화 분야의 핵심 주제 중 하나이다.

무향 그래프에서 최단 경로 문제는 두 정점 사이를 연결하는 경로 중 간선의 가중치 합이 최소가 되는 경로를 찾는 문제이다. 여기서 가중치는 일반적으로 거리, 비용, 시간 등을 의미한다. 무향 그래프의 간선은 양방향 이동이 가능하므로, 정점 u에서 v로의 최단 경로는 v에서 u로의 최단 경로와 동일하다는 점이 유향 그래프와의 주요 차이점이다.

이 문제를 해결하는 대표적인 알고리즘으로는 다익스트라 알고리즘과 플로이드-워셜 알고리즘이 있다. 다익스트라 알고리즘은 하나의 출발 정점에서 다른 모든 정점까지의 최단 경로를 찾는 데 사용되며, 그리디 알고리즘 접근법을 기반으로 한다. 플로이드-워셜 알고리즘은 모든 정점 쌍 사이의 최단 경로를 한 번에 계산하는 알고리즘이다.

최단 경로 알고리즘은 내비게이션 시스템, 네트워크 라우팅, 물류 운송 경로 최적화 등 실생활의 다양한 최적화 문제에 널리 응용된다. 무향 그래프 모델은 실제 도로망이나 통신망과 같이 연결이 상호적인 네트워크를 표현하는 데 적합하여, 이러한 응용 분야에서 핵심적인 역할을 한다.

무향 그래프에서 연결 요소는 그래프 내에서 서로 연결된 정점들의 최대 부분 집합을 의미한다. 정확히는, 그래프의 어떤 두 정점 u와 v가 같은 연결 요소에 속한다는 것은 u에서 v로 가는 경로가 존재한다는 것과 동치이다. 즉, 하나의 연결 요소 내에서는 모든 정점 쌍이 서로 도달 가능하지만, 서로 다른 연결 요소에 속한 정점들 사이에는 경로가 존재하지 않는다.

연결 요소의 개념은 그래프 이론에서 그래프의 연결성을 분석하는 기본 도구이다. 특히 네트워크 분석이나 클러스터링 문제에서 중요한 역할을 한다. 예를 들어, 소셜 네트워크에서 연결 요소는 서로 친구 관계를 통해 연결된 사용자들의 그룹을 식별하는 데 사용될 수 있으며, 통신 네트워크에서는 서로 통신 가능한 장치들의 집합을 파악하는 데 적용된다.

연결 요소를 찾는 대표적인 알고리즘은 깊이 우선 탐색 또는 너비 우선 탐색을 이용한다. 알고리즘은 아직 방문하지 않은 정점에서 탐색을 시작하여 도달할 수 있는 모든 정점을 방문하고, 이들을 하나의 연결 요소로 표시한다. 이 과정을 모든 정점이 방문될 때까지 반복한다. 이 알고리즘의 시간 복잡도는 인접 리스트 표현을 사용할 경우 O(|V| + |E|)로 매우 효율적이다.

연결 요소의 수는 그래프의 중요한 위상적 성질 중 하나이다. 연결 요소가 하나뿐인 그래프를 연결 그래프라고 하며, 두 개 이상인 그래프는 비연결 그래프라고 한다. 또한, 각 연결 요소 내에서 정점과 간선만을 고려한 부분 그래프는 그 자체로 연결 그래프가 된다.

위상 정렬은 유향 그래프에서만 정의되는 알고리즘으로, 무향 그래프에는 적용되지 않는다. 위상 정렬은 사이클이 없는 유향 그래프, 즉 DAG의 모든 정점을 간선 방향을 거스르지 않는 순서로 나열하는 것을 목표로 한다. 이는 작업 간 선후 관계가 명확한 작업 스케줄링이나 의존성 해결 같은 문제를 해결하는 데 사용된다.

무향 그래프는 간선에 방향성이 없기 때문에 정점 사이의 선후 관계를 정의할 수 없다. 무향 그래프에서 두 정점이 연결되어 있다는 것은 단순히 대등한 인접 관계만을 의미할 뿐, 한쪽이 다른 쪽보다 먼저 와야 한다는 순서를 암시하지 않는다. 따라서 위상 정렬의 기본 전제인 방향성과 비순환성이 무향 그래프에는 존재하지 않아, 위상 정렬 알고리즘을 적용하는 것이 무의미하다.

대신 무향 그래프에서는 정점을 방문하는 순서와 관련하여 깊이 우선 탐색이나 너비 우선 탐색과 같은 일반적인 그래프 순회 알고리즘이 주로 사용된다. 또한, 무향 그래프에서 순서를 찾는 대표적인 문제는 모든 정점을 한 번씩 방문하는 경로를 찾는 해밀턴 경로 문제나, 모든 간선을 한 번씩 지나는 경로를 찾는 오일러 경로 문제 등이 있다.

무향 그래프와 대비되는 개념으로 유향 그래프가 있다. 무향 그래프의 간선은 단순히 두 정점을 연결하는 관계를 나타내지만, 유향 그래프의 간선은 화살표처럼 한 정점에서 다른 정점으로의 방향성을 가진다. 따라서 유향 그래프에서 간선 (u, v)는 u에서 v로의 방향을 의미하며, (v, u)는 그 반대 방향의 별개 간선이 된다.

이러한 구조적 차이는 알고리즘과 문제 해결 접근법에 큰 영향을 미친다. 예를 들어, 무향 그래프에서 두 정점 사이의 연결성을 확인하는 것은 상대적으로 단순한 반면, 유향 그래프에서는 경로의 방향성을 고려해야 한다. 또한 위상 정렬이나 강한 연결 요소 탐색과 같은 알고리즘은 방향성이 존재하는 유향 그래프에서만 의미를 가진다.

무향 그래프는 많은 실제 시스템을 모델링하는 데 적합하다. 소셜 네트워크에서의 친구 관계, 도로 네트워크에서의 양방향 통행 가능 도로, 전기 회로의 연결선 등은 자연스럽게 방향성이 없는 관계로 표현될 수 있다. 이는 두 요소 간의 상호적이고 대칭적인 관계를 강조할 때 유용하다.

따라서 그래프를 활용할 때는 모델링하려는 관계의 본질이 상호적인지, 아니면 비대칭적인 방향성을 가지는지를 먼저 고려해야 한다. 이에 따라 무향 그래프 또는 유향 그래프 중 더 적절한 수학적 모델을 선택하게 된다.

다중 그래프는 그래프 이론에서 두 정점 사이에 여러 개의 간선이 존재할 수 있는 그래프를 말한다. 기본적인 무향 그래프나 유향 그래프는 두 정점 사이에 최대 하나의 간선만을 허용하는 단순 그래프로 정의되는 경우가 많다. 이에 반해 다중 그래프는 동일한 두 정점을 연결하는 중복 간선, 즉 평행 간선을 허용한다는 점이 핵심적인 차이이다.

다중 그래프는 현실 세계의 복잡한 연결 관계를 모델링할 때 유용하게 사용된다. 예를 들어, 두 도시 사이에 여러 개의 서로 다른 고속도로나 철도 노선이 존재하는 경우, 각 노선을 별도의 간선으로 표현하기 위해 다중 그래프를 활용할 수 있다. 또한 특정 통신 채널에서 두 노드 간에 여러 경로가 공존하는 네트워크를 표현하거나, 분자 구조에서 원자 사이의 다중 결합을 나타내는 데에도 적용된다.

다중 그래프의 수학적 표현은 기본 그래프와 마찬가지로 정점 집합 V와 간선 집합 E를 사용하지만, 간선 집합이 다중집합이 된다는 점이 다르다. 이로 인해 인접 행렬 표현 시 단순 그래프처럼 0과 1만으로는 표현이 불충분하며, 각 원소가 간선의 개수를 나타내는 정수 값을 가지게 된다. 대안적으로 인접 리스트 표현에서는 하나의 정점에 연결된 리스트에 동일한 이웃 정점이 여러 번 등장할 수 있다.

하이퍼그래프는 그래프 이론의 일반화된 형태로, 기존의 무향 그래프에서 하나의 간선이 정확히 두 개의 정점을 연결하는 것과 달리, 하나의 하이퍼에지가 두 개 이상의 정점을 동시에 연결할 수 있는 구조이다. 즉, 무향 그래프의 간선이 2-튜플이라면, 하이퍼그래프의 하이퍼에지는 임의의 크기의 정점 집합이다. 이는 복잡한 다자간 관계나 그룹 상호작용을 모델링하는 데 유용하다.

하이퍼그래프는 G = (V, E)로 표기되며, V는 정점 집합, E는 하이퍼에지 집합이다. 각 하이퍼에지는 V의 공집합이 아닌 부분집합으로 표현된다. 예를 들어, 학술 논문의 공동 저자 네트워크를 생각해볼 수 있다. 각 논문은 하나의 하이퍼에지가 되며, 해당 논문의 모든 저자 정점들을 연결한다. 이는 기존의 그래프로 표현하려면 모든 저자 쌍 사이에 간선을 그려야 하는 번거로움을 해결한다.

하이퍼그래프의 주요 응용 분야는 데이터 마이닝, 기계 학습, 데이터베이스 설계, 화학 정보학 등 다양하다. 특히 복잡계의 고차원 상관관계를 분석하거나, 소셜 네트워크에서의 그룹 동질성, 추천 시스템에서의 사용자-아이템 상호작용 모델링에 활용된다. 하이퍼그래프를 기반으로 한 군집화 알고리즘인 하이퍼그래프 커팅은 중요한 연구 주제이다.