유향 그래프

방향성 간선은 유향 그래프를 구성하는 핵심 요소이다. 이 간선은 두 정점 사이의 연결을 나타내지만, 그 연결에 명확한 방향이 존재한다는 점에서 무향 그래프의 간선과 구분된다. 수학적으로는 정점의 순서쌍 (u, v)로 표현되며, 이는 정점 u에서 정점 v로 향하는 화살표를 의미한다. 이러한 방향성은 관계의 비대칭성을 자연스럽게 모델링할 수 있게 해준다.

방향성 간선의 표기와 관련된 기본 용어가 있다. 정점 u에서 v로 향하는 간선 (u, v)에서, u를 꼬리 또는 시작점이라고 부르고, v를 머리 또는 도착점이라고 부른다. 이때 u는 v의 직접적인 선행자, v는 u의 직접적인 후속자가 된다. 이러한 방향성 때문에 한 정점의 차수는 진입차수와 진출차수로 나뉘어 계산된다. 진입차수는 해당 정점을 머리로 하는 간선의 수이고, 진출차수는 해당 정점을 꼬리로 하는 간선의 수이다.

방향성 간선은 단방향적인 관계나 흐름을 표현하는 데 필수적이다. 예를 들어, 웹페이지 간의 하이퍼링크, 소셜 미디어의 팔로우 관계, 도로의 일방통행로, 작업 간의 선후행 의존성 등은 모두 방향성을 가진 연결로, 유향 그래프를 통해 효과적으로 분석할 수 있다. 또한 오토마타 이론에서의 상태 전이, 네트워크 라우팅에서의 패킷 경로, 데이터베이스에서의 참조 무결성 제약 조건 등 다양한 분야에서 그 응용을 찾아볼 수 있다.

방향성 간선만으로 구성된 유향 그래프는 무향 그래프와는 다른 독특한 특성과 문제를 제기한다. 가장 대표적인 예로, 모든 정점 쌍 사이에 양방향 경로가 존재하는 강연결 그래프 여부를 판단하거나, 방향성 사이클이 존재하지 않는 DAG (방향성 비순환 그래프)를 활용한 위상 정렬 등이 있다. 이러한 특성들은 알고리즘 설계에 직접적인 영향을 미친다.

유향 그래프에서 정점은 네트워크의 개별 요소나 객체를 나타내는 기본 단위이다. 각 정점은 고유하게 식별되며, 방향을 가진 간선에 의해 다른 정점들과 연결된다. 정점의 집합은 일반적으로 V로 표기한다.

정점의 연결 관계를 정량적으로 나타내는 개념이 차수이다. 무향 그래프와 달리 유향 그래프에서는 방향성을 고려하여 진입차수와 진출차수로 구분한다. 진입차수는 해당 정점으로 들어오는 간선의 수를, 진출차수는 해당 정점에서 나가는 간선의 수를 의미한다. 예를 들어, 작업 간 선행 관계를 모델링할 때, 어떤 작업의 진입차수가 0이라면 이는 선행 작업이 없는 시작 작업임을 나타낸다.

차수는 그래프의 구조와 특성을 분석하는 데 중요한 지표가 된다. 모든 정점의 진입차수와 진출차수의 총합은 동일하며, 이는 전체 간선의 수와 직접적인 관련이 있다. 또한, 위상 정렬이 가능한 방향성 비순환 그래프에서는 반드시 진입차수가 0인 정점이 하나 이상 존재한다.

이러한 정점과 차수의 개념은 네트워크 라우팅에서의 라우터 중요도 분석이나, 소셜 네트워크 분석에서의 영향력 지표 계산 등 다양한 응용 분야의 기초를 이룬다.

인접 행렬은 유향 그래프를 표현하는 가장 기본적인 방법 중 하나이다. 이 방법은 그래프의 정점들 간의 연결 관계를 정방형의 2차원 배열, 즉 행렬로 나타낸다. 주로 정점의 개수가 비교적 적고 간선의 밀도가 높은 조밀 그래프를 표현할 때 효율적이다.

인접 행렬 M은 정점의 개수가 n개일 때 n x n 크기의 정방행렬로 정의된다. 행렬의 각 요소 M[i][j]는 정점 i에서 정점 j로 가는 간선이 존재하는지 여부를 나타낸다. 일반적으로 간선이 존재하면 1, 존재하지 않으면 0의 값을 가진다. 유향 그래프에서는 간선의 방향성이 중요하므로, M[i][j]와 M[j][i]의 값이 서로 다를 수 있다. 이는 무향 그래프의 인접 행렬이 대칭행렬인 것과 대비되는 점이다.

인접 행렬 표현법의 주요 장점은 두 정점 사이의 연결 관계를 상수 시간(O(1))에 확인할 수 있다는 점이다. 또한 행렬 연산을 활용하여 그래프의 경로나 연결성을 분석하는 데 유용하다. 반면, 정점 수 n에 대해 n^2의 공간을 필요로 하므로, 정점이 많고 간선이 적은 희소 그래프의 경우 메모리 사용이 비효율적일 수 있다. 또한 특정 정점에 연결된 모든 이웃 정점을 찾기 위해서는 해당 행 또는 열 전체를 탐색해야 하므로 O(n)의 시간이 소요된다.

인접 행렬은 그래프의 구조를 명확하게 시각화할 수 있어 학습 도구로 자주 사용되며, 플로이드-워셜 알고리즘과 같이 모든 정점 쌍 간의 최단 경로를 구하는 알고리즘 등에서도 활용된다.

인접 리스트는 유향 그래프를 표현하는 또 다른 주요 방법이다. 각 정점마다 그 정점에서 출발하는 간선이 연결된 목적지 정점들의 리스트를 저장하는 방식으로, 그래프의 희소성에 따라 효율적인 공간 활용이 가능하다.

인접 행렬이 모든 정점 쌍에 대한 연결 여부를 행렬로 저장하는 것과 달리, 인접 리스트는 실제로 존재하는 간선만을 저장한다. 따라서 정점의 수가 많지만 간선의 수가 상대적으로 적은 희소 그래프에서 메모리 사용 측면에서 매우 유리하다. 각 정점 v에 대해, v에서 시작하여 도달 가능한 모든 정점 u를 리스트(또는 배열, 동적 배열)에 저장한다. 이때 간선의 방향성이 중요하므로, (u, v) 순서쌍에서 출발점 u의 리스트에만 목적지 v가 추가된다.

인접 리스트의 구조는 구현 방식에 따라 약간의 차이가 있을 수 있다. 일반적으로는 정점의 집합 V 크기만큼의 배열을 만들고, 각 배열 요소가 연결 리스트나 벡터와 같은 동적 컨테이너를 가리키도록 구성한다. 이 표현법을 사용하면 특정 정점에서 나가는 모든 이웃 정점을 탐색하는 작업은 매우 효율적이다. 반면, 두 정점 u와 v 사이에 특정 방향의 간선이 존재하는지 확인하려면 u의 리스트를 선형 검색해야 하므로, 인접 행렬에 비해 검색 시간이 더 걸릴 수 있다.

대부분의 그래프 알고리즘, 특히 깊이 우선 탐색이나 너비 우선 탐색처럼 특정 정점에 연결된 모든 간선을 순회하는 작업이 빈번한 경우에는 인접 리스트 표현이 더 선호된다. 이는 실제 연결된 이웃만을 빠르게 접근할 수 있기 때문이다.

강연결 그래프는 방향 그래프에서 모든 정점 쌍 사이에 양방향 경로가 존재하는 그래프를 말한다. 구체적으로, 그래프 내의 임의의 두 정점 u와 v에 대해, u에서 v로 가는 방향 경로와 v에서 u로 가는 방향 경로가 모두 존재해야 한다. 이는 그래프의 연결성이 매우 강력함을 의미하며, 모든 정점들이 서로 왕복할 수 있는 하나의 강력한 집합을 형성한다.

강연결성을 확인하는 대표적인 알고리즘으로는 코사라주 알고리즘과 타잔 알고리즘이 있다. 이 알고리즘들은 깊이 우선 탐색을 기반으로 하여 그래프를 한 번 또는 두 번 탐색하는 과정에서 모든 강연결 요소를 찾아낸다. 여기서 강연결 요소란, 해당 부분 그래프 내에서는 강연결성을 만족하지만, 더 큰 상위 그래프로 확장하면 강연결성이 깨지는 최대 부분 그래프를 의미한다.

강연결 그래프의 개념은 네트워크 라우팅이나 웹 크롤링과 같은 분야에서 중요하게 활용된다. 예를 들어, 월드 와이드 웹을 페이지를 정점으로, 하이퍼링크를 방향 간선으로 모델링했을 때, 강연결 요소를 분석하면 서로 밀접하게 연결된 웹 페이지들의 커뮤니티를 발견할 수 있다. 또한, 강연결 그래프는 시스템의 신뢰성 분석에서도 사용되며, 모든 구성 요소가 서로 직접적 또는 간접적으로 의사소통할 수 있는 네트워크 토폴로지를 설계하는 데 기초가 된다.

유향 그래프에서 사이클은 시작 정점과 종료 정점이 동일한, 방향성을 가진 닫힌 경로를 의미한다. 즉, 간선의 방향을 따라 이동했을 때, 같은 정점으로 되돌아올 수 있는 경로가 존재하는 경우를 말한다. 사이클이 존재하는 유향 그래프는 순환 그래프라고도 불린다.

사이클의 존재 여부는 그래프의 성질과 이를 활용하는 알고리즘에 큰 영향을 미친다. 예를 들어, 위상 정렬 알고리즘은 사이클이 존재하지 않는 방향성 비순환 그래프에서만 적용 가능하다. 또한 네트워크 라우팅 프로토콜에서 라우팅 루프를 방지하거나, 작업 스케줄링에서 선행 조건의 순환 의존성을 검출하는 데 사이클 탐지가 핵심적으로 사용된다.

사이클을 탐지하는 대표적인 방법으로 깊이 우선 탐색을 활용한 방법이 있다. 탐색 과정에서 현재 방문 중인 경로 상에서 이미 방문한 정점을 다시 만나게 되면, 이는 사이클이 존재한다는 것을 의미한다. 이 기법은 그래프의 모든 정점을 한 번씩 방문하므로, 시간 복잡도는 O(V+E)로 효율적이다.

DAG는 방향성 비순환 그래프의 약자로, 방향이 있는 간선들로 이루어져 있으면서 사이클이 존재하지 않는 유향 그래프를 의미한다. 즉, 어떤 정점에서 출발하여 간선의 방향을 따라 이동했을 때, 다시 출발점으로 돌아오는 경로가 절대 존재하지 않는 구조를 가진다. 이는 그래프에 방향성은 있지만, 그 관계가 순환하지 않고 일정한 방향성을 유지한다는 점이 핵심 특징이다.

DAG는 위상 정렬이 가능한 그래프로, 모든 정점들을 간선의 방향을 거스르지 않는 선형 순서로 나열할 수 있다. 이 성질은 작업 스케줄링이나 의존성 관리와 같은 문제를 모델링하는 데 매우 유용하다. 예를 들어, 특정 작업이 다른 작업의 완료를 전제로 할 때, 이러한 선후 관계를 DAG로 표현하면 작업들을 실행할 올바른 순서를 쉽게 찾아낼 수 있다.

DAG는 다양한 분야에서 응용된다. 데이터 흐름 시스템이나 빅데이터 처리 파이프라인에서 각 처리 단계의 의존성을 표현하는 데 사용되며, 버전 관리 시스템에서의 커밋 히스토리, 인공지능의 베이지안 네트워크, 그리고 컴파일러가 코드의 문장들을 실행 순서로 정렬할 때도 DAG가 활용된다. 이러한 넓은 활용도는 DAG가 복잡한 관계를 계층적이고 비순환적인 구조로 명확하게 표현할 수 있기 때문이다.

DAG와 관련된 중요한 알고리즘으로는 위상 정렬 외에도, 최단 경로를 찾는 알고리즘을 DAG에 특화시켜 일반 그래프보다 효율적으로 동작하도록 만든 DAG 기반 최단 경로 알고리즘이 있다. 또한, 동적 계획법에서 부분 문제 간의 의존 관계를 나타내는 메모이제이션 DAG를 구성하여 문제를 해결하는 방법도 있다.

깊이 우선 탐색(DFS)은 유향 그래프를 탐색하는 기본적인 알고리즘 중 하나이다. 이 방법은 그래프의 한 정점을 시작점으로 하여, 가능한 한 깊게 탐색을 진행한 후, 더 이상 진행할 수 없을 때 이전 정점으로 돌아와 다른 경로를 탐색하는 방식으로 작동한다. 스택 자료구조를 명시적으로 사용하거나 재귀 호출을 통해 구현할 수 있으며, 그래프의 모든 정점을 체계적으로 방문하는 데 사용된다.

유향 그래프에서 DFS는 그래프의 구조를 이해하는 데 핵심적인 역할을 한다. 탐색 과정에서 각 정점의 발견 시간과 탐색 완료 시간을 기록하면, 그래프에 사이클이 존재하는지 판별하거나, 후속 순서 관계를 분석하는 데 활용할 수 있다. 또한, 이 알고리즘은 위상 정렬이나 강연결 요소를 찾는 알고리즘의 기반이 된다.

DFS 알고리즘의 구체적인 동작은 다음과 같다. 먼저 모든 정점을 '방문하지 않음' 상태로 초기화한다. 시작 정점을 방문 처리하고 스택에 넣거나 재귀 함수를 호출한다. 현재 정점에서 방문하지 않은 인접 정점이 있다면 그 정점으로 이동하여 동일한 과정을 반복한다. 더 이상 이동할 정점이 없다면 이전 정점으로 돌아가서 다른 인접 정점을 탐색한다. 이 과정을 스택이 비거나 모든 정점을 방문할 때까지 반복한다.

이 탐색 방법은 유향 그래프의 다양한 응용 분야, 예를 들어 네트워크 라우팅에서 경로 탐색이나 작업 스케줄링에서의 의존성 분석 등에 널리 적용된다. DFS를 통해 얻은 정보는 그래프의 위상적 특성을 파악하는 데 중요한 단서를 제공한다.

위상 정렬은 방향성 비순환 그래프(DAG)의 모든 정점을 방향성 간선의 방향을 거스르지 않도록 순서를 나열하는 알고리즘이다. 즉, 그래프에 존재하는 모든 간선 (u, v)에 대해, 정렬 결과에서 정점 u가 정점 v보다 반드시 앞에 오도록 하는 선형 순서를 찾는 과정이다. 이러한 특성 때문에 작업 간의 선후관계가 명확한 작업 스케줄링이나 의존성 해결, 컴파일러에서의 코드 최적화 등에 널리 응용된다.

위상 정렬을 수행하는 대표적인 방법은 깊이 우선 탐색(DFS)을 이용하는 것이다. DFS를 수행하며 각 정점의 탐색이 완료되는 순서를 역순으로 기록하면 위상 정렬된 순서를 얻을 수 있다. 또 다른 방법은 각 정점으로 들어오는 간선의 수, 즉 진입차수를 계산하는 것이다. 진입차수가 0인 정점들을 큐에 넣고 순차적으로 제거하면서, 해당 정점에서 나가는 간선을 제거하고 새롭게 진입차수가 0이 된 정점을 큐에 추가하는 과정을 반복한다.

위상 정렬은 그래프에 사이클이 존재할 경우 유효한 결과를 도출할 수 없다. 사이클이 존재하면 선후관계에 모순이 생기기 때문이다. 따라서 위상 정렬 알고리즘을 수행한 후, 정렬된 정점의 수가 전체 정점 수보다 적다면 해당 그래프에는 사이클이 존재함을 알 수 있다. 이는 그래프가 방향성 비순환 그래프인지 여부를 판별하는 한 방법으로도 사용된다.

강연결 요소는 방향 그래프에서 매우 중요한 개념이다. 이는 그래프 내에서 서로 강하게 연결된 정점들의 최대 부분 집합을 의미한다. 구체적으로, 강연결 요소 내의 임의의 두 정점 u와 v에 대해, u에서 v로 가는 경로와 v에서 u로 가는 경로가 모두 존재해야 한다. 즉, 두 정점이 서로 왕복할 수 있어야 같은 강연결 요소에 속한다. 이 정의에 따라, 하나의 정점만으로도 그 자체로 강연결 요소가 될 수 있다.

강연결 요소를 찾는 대표적인 알고리즘으로는 코사라주 알고리즘과 타잔 알고리즘이 있다. 두 알고리즘 모두 깊이 우선 탐색을 기반으로 하지만, 접근 방식에 차이가 있다. 코사라주 알고리즘은 그래프와 그 전치 그래프에 대해 각각 DFS를 수행하는 방식을 취하는 반면, 타잔 알고리즘은 한 번의 DFS 수행 중에 스택을 활용하여 강연결 요소를 식별한다. 이 알고리즘들은 그래프 알고리즘 분야에서 기본적으로 다루어진다.

강연결 요소를 찾는 것은 그래프의 구조를 단순화하고 분석하는 데 필수적이다. 각 강연결 요소를 하나의 슈퍼 정점으로 압축하면, 원래의 방향 그래프는 방향성 비순환 그래프가 된다. 이렇게 변환된 DAG는 위상 정렬이 가능해지며, 복잡한 시스템의 모듈 간 의존 관계를 명확히 이해하거나, 컴파일러가 함수 호출 그래프를 분석하는 데 유용하게 활용된다. 또한, 소셜 네트워크에서 밀집된 커뮤니티를 발견하거나, 웹 페이지 간의 링크 구조에서 중요한 페이지 군집을 식별하는 등 다양한 분야에 응용된다.

유향 그래프는 네트워크 라우팅에서 경로 탐색과 데이터 패킷의 전송 경로를 결정하는 핵심 모델로 활용된다. 특히 인터넷이나 통신 네트워크에서 라우터는 네트워크 토폴로지를 유향 그래프로 모델링하여, 한 노드(라우터)에서 다른 노드로 데이터가 이동할 최적의 경로를 계산한다. 이때 간선의 방향은 통신 링크의 단방향性或 가용 대역폭 등의 제약 조건을 반영한다.

라우팅 알고리즘은 이 그래프 구조 위에서 동작한다. 대표적인 거리 벡터 라우팅 프로토콜과 링크 상태 라우팅 프로토콜 모두 네트워크를 그래프로 간주하며, 각각 벨만-포드 알고리즘과 다익스트라 알고리즘 같은 그래프 알고리즘을 응용하여 최단 경로를 찾는다. 유향 그래프를 사용하면 특정 방향으로의 통신만 가능한 비대칭 링크나, 네트워크 정책에 따른 제한된 경로를 정확히 표현할 수 있다.

이러한 라우팅 과정은 단순한 경로 찾기를 넘어, 네트워크의 트래픽 엔지니어링이나 장애 복구에도 적용된다. 예를 들어, 주요 링크에 장애가 발생하면 라우터는 유향 그래프에서 해당 간선을 제거하거나 비용을 높게 조정한 새로운 토폴로지 그래프를 구성하고, 이를 바탕으로 대체 경로를 신속하게 계산하여 네트워크의 안정성을 유지한다.

작업 스케줄링은 유향 그래프의 대표적인 응용 분야 중 하나이다. 특히, 여러 작업 간의 선후 관계가 존재하는 상황에서 모든 작업을 순서대로 완료할 수 있는 일정을 구성하는 데 유향 그래프가 핵심적으로 사용된다. 이때 각 작업은 그래프의 정점으로, 작업 A가 작업 B보다 먼저 수행되어야 한다는 의존 관계는 A에서 B를 향하는 방향성 간선으로 표현된다.

이렇게 구성된 그래프에서 사이클이 존재하면, 예를 들어 작업 A가 B에, B가 C에, C가 다시 A에 의존하는 경우처럼 모순된 선후 관계가 생겨 유효한 스케줄을 만들 수 없다. 따라서 유효한 작업 스케줄을 찾기 위한 전제 조건은 그래프가 DAG (방향성 비순환 그래프)라는 것이다. DAG 위에서 위상 정렬 알고리즘을 수행하면 모든 의존 관계를 만족시키는 작업의 수행 순서를 얻을 수 있다.

작업 스케줄링은 소프트웨어 빌드 시스템, 프로젝트 관리의 CPM 및 PERT, 운영체제의 작업 처리 순서 결정 등 다양한 분야에서 활용된다. 또한 각 작업에 소요 시간이나 자원에 대한 가중치를 부여하여 최소 완료 시간을 계산하는 등 보다 복잡한 스케줄링 문제로도 확장되어 연구된다.

소셜 네트워크 분석은 개인, 조직, 집단 간의 관계를 구조적으로 연구하는 분야이다. 유향 그래프는 이러한 관계에서 방향성을 명확히 모델링하는 핵심 도구로 활용된다. 예를 들어, 소셜 미디어 플랫폼에서의 팔로우 관계나 이메일 통신 흐름은 한 노드에서 다른 노드로 향하는 단방향 연결로 자연스럽게 표현될 수 있다. 이러한 유향 그래프를 통해 네트워크 내에서 정보의 확산 경로, 영향력의 방향, 그리고 커뮤니티의 위계 구조를 분석할 수 있다.

구체적인 분석 지표로는 연결 중심성, 매개 중심성, 근접 중심성 등이 있으며, 이들은 유향 그래프에서 방향성을 고려하여 계산된다. 예를 들어, 많은 노드로부터 링크를 받는 정점(진입 차수가 높은 노드)은 영향력 있는 인플루언서나 허브로 해석될 수 있다. 반대로 많은 노드로 링크를 보내는 정점(진출 차수가 높은 노드)은 적극적인 정보 전파자 역할을 할 가능성이 있다.

유향 그래프를 이용한 소셜 네트워크 분석은 다양한 분야에 적용된다. 마케팅에서는 바이럴 캠페인의 최적 경로를 예측하고, 보안 분야에서는 사이버 범죄 네트워크나 가짜 뉴스의 확산 경로를 추적하는 데 사용된다. 또한, 학술적 인용 네트워크 분석을 통해 연구 흐름과 학문적 영향력을 방향성 있게 파악하는 데에도 중요한 역할을 한다.

무향 그래프는 유향 그래프와 대비되는 개념으로, 간선에 방향성이 없는 그래프이다. 즉, 두 정점을 연결하는 간선은 양방향 관계를 나타낸다. 무향 그래프에서 간선은 순서가 없는 정점 쌍 {u, v}로 표현되며, 이는 정점 u와 v가 서로 연결되어 있음을 의미한다. 이는 소셜 네트워크에서의 친구 관계나 도로망에서의 양방향 통행로를 모델링하는 데 적합하다.

무향 그래프는 그래프 이론의 기본이 되는 구조로, 자료구조와 알고리즘에서 널리 연구된다. 대표적인 알고리즘으로는 최소 신장 트리를 찾는 크루스칼 알고리즘이나 프림 알고리즘, 그리고 최단 경로 문제를 푸는 다익스트라 알고리즘 등이 무향 가중치 그래프를 주요 대상으로 한다. 이러한 알고리즘들은 네트워크 과학이나 물류 시스템 최적화 등 다양한 분야에 응용된다.

유향 그래프와 무향 그래프는 표현 방법에서도 차이를 보인다. 무향 그래프의 인접 행렬은 대칭 행렬인 반면, 유향 그래프의 인접 행렬은 일반적으로 비대칭이다. 또한 무향 그래프에서 정점의 차수는 해당 정점에 인접한 간선의 수로 정의되지만, 유향 그래프에서는 진입차수와 진출차수로 세분화된다.

이처럼 방향성의 유무는 그래프의 수학적 성질과 이를 처리하는 알고리즘에 근본적인 영향을 미치며, 문제의 본질에 따라 적절한 그래프 모델을 선택하는 것이 중요하다.

가중치 그래프는 그래프의 각 간선에 가중치라는 추가적인 수치 정보가 부여된 그래프를 말한다. 이 가중치는 비용, 거리, 시간, 용량, 강도 등 연결의 특정 속성을 수치화하여 표현한다. 유향 그래프에 가중치가 부여된 경우를 가중치 유향 그래프라고 하며, 이는 네트워크 흐름 분석이나 최단 경로 탐색 등에서 중요한 모델이 된다.

가중치 그래프는 다양한 형태로 표현된다. 인접 행렬을 사용할 경우, 행렬의 각 원소가 두 정점 사이의 가중치를 저장하며, 간선이 존재하지 않음을 나타내기 위해 무한대(∞)나 0 등의 특수 값을 사용한다. 인접 리스트를 사용할 경우, 각 정점에 연결된 간선의 정보를 (연결된 정점, 가중치)의 쌍으로 저장하여 표현한다.

가중치 그래프의 대표적인 알고리즘으로는 다익스트라 알고리즘이나 벨만-포드 알고리즘과 같은 최단 경로 알고리즘이 있다. 이 알고리즘들은 가중치의 합을 최소화하는 경로를 찾는 데 사용된다. 또한, 네트워크 이론에서 최대 유량 최소 컷 정리를 적용하거나, 운영 연구에서 최소 비용 유량 문제를 풀 때도 가중치 유향 그래프가 핵심 모델로 활용된다.

가중치 그래프는 도로 네트워크, 통신 네트워크, 물류 시스템, 프로젝트 관리의 임계 경로법 등 현실 세계의 복잡한 관계와 제약 조건을 모델링하는 데 필수적인 도구이다.

다중 그래프는 두 정점 사이에 여러 개의 간선이 존재할 수 있는 그래프 구조이다. 일반적인 그래프 이론에서 정의하는 단순 그래프는 두 정점 사이에 최대 하나의 간선만을 허용하지만, 다중 그래프는 동일한 두 정점을 연결하는 중복 간선, 즉 평행 간선을 허용한다는 점이 핵심 차이이다.

이 개념은 방향성 유무에 따라 유향 그래프와 무향 그래프 모두에 적용될 수 있다. 예를 들어, 두 도시를 연결하는 여러 개의 서로 다른 항공편이나 버스 노선을 모델링할 때, 각 노선을 하나의 간선으로 표현하면 자연스럽게 다중 그래프가 된다. 또한, 가중치 그래프와 결합되어 각 간선에 서로 다른 가중치(예: 요금, 소요 시간)를 부여하는 형태로도 널리 사용된다.

다중 그래프는 복잡한 관계나 다중 연결을 표현해야 하는 실제 시스템 모델링에 유용하다. 통신 네트워크의 백업 경로, 분산 시스템에서의 다중 채널 연결, 또는 소셜 네트워크 분석에서 두 사람 사이의 다양한 유형의 관계(친구, 동료, 가족)를 각각 다른 간선으로 나타내는 경우 등이 그 예시이다. 이러한 모델은 네트워크 과학과 데이터 구조 설계에서 중요한 도구로 활용된다.