---
title: "Network model (operations research) — 네트워크 모델"
source: "https://systems-analysis.info/int/Network_model_(operations_research)_%E2%80%94_%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC_%EB%AA%A8%EB%8D%B8"
wiki: "systems-analysis.info/int"
article: "Network_model_(operations_research)_—_네트워크_모델"
language: "ko"
categories:
  - "Category:Korean"
  - "Category:Operations research"
revision_id: 4873
wiki_created_at: 2026-09-06T23:41:15Z
wiki_modified_at: 2026-09-06T23:41:15Z
downloaded_at: 2026-09-07T23:05:24Z
---

# Network model (operations research) — 네트워크 모델

**네트워크 모델** (운용 과학 분야; 영어: *Network models*) — 문제를 그래프(네트워크) 형태로 표현하는 수학적 모델의 한 범주로, 꼭짓점(노드)은 객체 또는 상태를 나타내고 간선(호)은 그들 사이의 관계 또는 과정을 나타낸다<sup>[\[1\]](https://systems-analysis.info/int/Network_model_(operations_research)_%E2%80%94_%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC_%EB%AA%A8%EB%8D%B8#cite_note-en-wiki-flow-network-1)</sup>. 최적화의 맥락에서 네트워크는 흔히 방향 그래프를 의미하며, 운용 분석에서는 이를 직접 '네트워크'라 부른다. 이러한 네트워크의 꼭짓점은 노드라 하고, 간선은 호(arc)라 한다<sup>[\[2\]](https://systems-analysis.info/int/Network_model_(operations_research)_%E2%80%94_%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC_%EB%AA%A8%EB%8D%B8#cite_note-belgut-lec-2)</sup>.

네트워크 모델은 물류, 통신, 프로젝트 관리, 금융 등의 분야에서 복잡한 시스템을 분석하고 최적화하는 강력한 도구이다. 그 강점은 높은 수준의 추상화에 있다. 노드는 도시, 컴퓨터 라우터 또는 프로젝트의 단계를 나타낼 수 있으며, 호는 도로, 통신 채널 또는 기술적 작업을 나타낼 수 있다.

## 정의 및 용어

네트워크 모델의 기반은 그래프 이론이다. 핵심 개념은 다음과 같다:

- **흐름 네트워크** (영어: *flow network*): 각 간선에 **용량** (*capacity*)과 **흐름** (*flow*)이 부여된 방향 그래프. 그래프에는 두 개의 특수한 꼭짓점이 존재한다. 흐름이 발생하는 **소스** (*source*)와 흐름이 유입되는 **싱크** (*sink*)가 그것이다<sup>[\[1\]](https://systems-analysis.info/int/Network_model_(operations_research)_%E2%80%94_%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC_%EB%AA%A8%EB%8D%B8#cite_note-en-wiki-flow-network-1)</sup>.
- **흐름 보존 법칙**: 소스 또는 싱크가 아닌 임의의 꼭짓점에서, 총 유입 흐름은 총 유출 흐름과 같아야 한다. 이 조건은 물리적 보존 법칙의 이산적 유사체이다<sup>[\[3\]](https://systems-analysis.info/int/Network_model_(operations_research)_%E2%80%94_%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC_%EB%AA%A8%EB%8D%B8#cite_note-ru-wiki-transport-net-3)</sup>.
- **네트워크 계획법**: 프로젝트를 상호 연관된 작업(호)과 사건(노드)의 집합으로 표현하는 모델. 이러한 네트워크는 방향 비순환 그래프(DAG)이며, 이는 작업의 수행 순서를 반영한다<sup>[\[4\]](https://systems-analysis.info/int/Network_model_(operations_research)_%E2%80%94_%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC_%EB%AA%A8%EB%8D%B8#cite_note-ru-wiki-cpm-pert-4)</sup>.

## 주요 속성 및 정리

네트워크 모델은 고효율 알고리즘의 적용을 가능하게 하는 여러 특수한 속성을 지닌다.

- **해의 정수성**: 많은 네트워크 최적화 문제(예: 최대 흐름 문제 또는 최단 경로 문제)는 제약 행렬의 완전 유니모듈러 성질을 갖는다. 이 덕분에 문제의 매개변수(용량, 길이)가 정수인 경우, 선형 계획법으로 구한 최적해는 추가적인 정수 제약 없이도 정수해가 된다<sup>[\[5\]](https://systems-analysis.info/int/Network_model_(operations_research)_%E2%80%94_%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC_%EB%AA%A8%EB%8D%B8#cite_note-mit-amp-ch8-5)[\[6\]](https://systems-analysis.info/int/Network_model_(operations_research)_%E2%80%94_%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC_%EB%AA%A8%EB%8D%B8#cite_note-ru-wiki-max-flow-6)</sup>.
- **최대 흐름-최소 컷 정리**: 흐름 이론의 핵심 결과. 소스에서 싱크로의 최대 흐름 값은 소스와 싱크를 분리하는 모든 컷 중 최소 용량과 같다고 주장한다. 이 정리는 흐름의 최적성 기준을 확립하며 많은 알고리즘의 기반이 된다<sup>[\[6\]](https://systems-analysis.info/int/Network_model_(operations_research)_%E2%80%94_%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC_%EB%AA%A8%EB%8D%B8#cite_note-ru-wiki-max-flow-6)[\[7\]](https://systems-analysis.info/int/Network_model_(operations_research)_%E2%80%94_%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC_%EB%AA%A8%EB%8D%B8#cite_note-goldberg-tarjan-1990-7)</sup>.
- **최단 경로에 대한 최적성 원리**: A에서 C로의 경로가 최단 경로라면, 그 경로의 임의의 부분(예: 중간 지점 B에서 C까지)도 해당 꼭짓점들 사이의 최단 경로이다. 동적 계획법의 기반이 되는 이 속성은 다익스트라 알고리즘과 같은 알고리즘의 정확성을 보장한다<sup>[\[8\]](https://systems-analysis.info/int/Network_model_(operations_research)_%E2%80%94_%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC_%EB%AA%A8%EB%8D%B8#cite_note-ru-wiki-shortest-path-8)</sup>.
- **최소 신장 트리(MST)의 속성**:
- **컷 속성**: 그래프의 임의의 컷에 대해, 컷을 가로지르는 최소 가중치 간선은 적어도 하나의 MST에 속한다.
- **사이클 속성**: 그래프의 임의의 사이클에서, 최대 가중치 간선은 어떤 MST에도 속하지 않는다.

이러한 속성에 기반하여 프림 알고리즘과 크루스칼 알고리즘의 정확성이 성립한다<sup>[\[9\]](https://systems-analysis.info/int/Network_model_(operations_research)_%E2%80%94_%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC_%EB%AA%A8%EB%8D%B8#cite_note-ru-wiki-mst-9)</sup>.

## 네트워크 최적화의 주요 문제

- **최단 경로 문제**: 두 개의 주어진 노드 사이에서 총 길이(가중치)가 최소인 경로를 구한다. 다익스트라 알고리즘(비음수 가중치의 경우) 또는 벨만-포드 알고리즘(임의의 가중치의 경우)으로 해결된다<sup>[\[8\]](https://systems-analysis.info/int/Network_model_(operations_research)_%E2%80%94_%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC_%EB%AA%A8%EB%8D%B8#cite_note-ru-wiki-shortest-path-8)</sup>.
- **최대 흐름 문제**: 주어진 호의 용량 하에서 소스에서 싱크로의 최대 가능 흐름을 결정한다. 대표적인 해결 방법은 포드-풀커슨 알고리즘이다<sup>[\[6\]](https://systems-analysis.info/int/Network_model_(operations_research)_%E2%80%94_%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC_%EB%AA%A8%EB%8D%B8#cite_note-ru-wiki-max-flow-6)</sup>.
- **최소 신장 트리 문제**: 네트워크의 모든 꼭짓점을 연결하면서 간선의 총 비용이 최소인 부분 그래프를 구한다.
- **주공정법 (CPM)**: 네트워크 계획 모델에서, 전체 프로젝트의 최소 완료 시간을 결정하는 가장 긴 작업 순서를 구한다. 이 경로상의 작업들은 여유 시간이 0이다<sup>[\[10\]](https://systems-analysis.info/int/Network_model_(operations_research)_%E2%80%94_%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC_%EB%AA%A8%EB%8D%B8#cite_note-ru-wiki-cpm-10)</sup>.

## 예시

- **최단 경로**: 도시 지도에서 두 지점 사이의 최적 경로를 내비게이션 시스템이 탐색하는 경우. 도시는 노드, 도로는 거리 또는 이동 시간을 가중치로 갖는 호이다.
- **최대 흐름**: 파이프라인 네트워크의 최대 처리 용량을 결정하는 경우. 펌프 스테이션은 노드, 파이프는 제한된 용량을 가진 호이다.
- **최소 신장 트리**: 여러 도시를 최소 총 케이블 길이로 연결하기 위한 통신 네트워크(예: 광섬유 케이블 포설) 설계.
- **주공정**: 주택 건설 프로젝트에서, 작업(기초 공사, 벽 시공, 지붕 설치)이 정해진 기간과 기술적 선후 관계를 가질 때, 주공정은 최소 완공 기간을 결정한다. 이 경로상의 임의의 작업이 지연되면 전체 프로젝트가 지연된다<sup>[\[10\]](https://systems-analysis.info/int/Network_model_(operations_research)_%E2%80%94_%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC_%EB%AA%A8%EB%8D%B8#cite_note-ru-wiki-cpm-10)</sup>.

## 같이 보기

- 운용 과학
- 그래프 이론
- 수송 문제
- 주공정법
- PERT

## 각주

1.  <span id="cite_note-en-wiki-flow-network-1">↑ <sup>[1.0](https://systems-analysis.info/int/Network_model_(operations_research)_%E2%80%94_%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC_%EB%AA%A8%EB%8D%B8#cite_ref-en-wiki-flow-network_1-0)</sup> <sup>[1.1](https://systems-analysis.info/int/Network_model_(operations_research)_%E2%80%94_%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC_%EB%AA%A8%EB%8D%B8#cite_ref-en-wiki-flow-network_1-1)</sup> "Flow network". *Wikipedia*. <a href="https://en.wikipedia.org/wiki/Flow_network" class="external autonumber" rel="nofollow">[1]</a></span>
2.  <span id="cite_note-belgut-lec-2">[↑](https://systems-analysis.info/int/Network_model_(operations_research)_%E2%80%94_%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC_%EB%AA%A8%EB%8D%B8#cite_ref-belgut-lec_2-0) "Тема 10: Сетевые модели". Учебное пособие. Гомель: БелГУТ. <a href="https://elib.gsu.by/bitstream/123456789/4781/13/Тема10_Сетевые%20модели_net_lec.pdf" class="external autonumber" rel="nofollow">[2]</a></span>
3.  <span id="cite_note-ru-wiki-transport-net-3">[↑](https://systems-analysis.info/int/Network_model_(operations_research)_%E2%80%94_%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC_%EB%AA%A8%EB%8D%B8#cite_ref-ru-wiki-transport-net_3-0) "Транспортная сеть". *Википедия*. <a href="https://ru.wikipedia.org/wiki/Транспортная_сеть" class="external autonumber" rel="nofollow">[3]</a></span>
4.  <span id="cite_note-ru-wiki-cpm-pert-4">[↑](https://systems-analysis.info/int/Network_model_(operations_research)_%E2%80%94_%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC_%EB%AA%A8%EB%8D%B8#cite_ref-ru-wiki-cpm-pert_4-0) "Сетевое планирование". *Википедия*. <a href="https://ru.wikipedia.org/wiki/Сетевое_планирование" class="external autonumber" rel="nofollow">[4]</a></span>
5.  <span id="cite_note-mit-amp-ch8-5">[↑](https://systems-analysis.info/int/Network_model_(operations_research)_%E2%80%94_%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC_%EB%AA%A8%EB%8D%B8#cite_ref-mit-amp-ch8_5-0) Bradley S. P., Hax A. C., Magnanti T. L. (1977). *Applied Mathematical Programming*. Addison-Wesley. Ch.8: Network Models. <a href="https://web.mit.edu/15.053/www/AMP-Chapter-08.pdf" class="external autonumber" rel="nofollow">[5]</a></span>
6.  <span id="cite_note-ru-wiki-max-flow-6">↑ <sup>[6.0](https://systems-analysis.info/int/Network_model_(operations_research)_%E2%80%94_%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC_%EB%AA%A8%EB%8D%B8#cite_ref-ru-wiki-max-flow_6-0)</sup> <sup>[6.1](https://systems-analysis.info/int/Network_model_(operations_research)_%E2%80%94_%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC_%EB%AA%A8%EB%8D%B8#cite_ref-ru-wiki-max-flow_6-1)</sup> <sup>[6.2](https://systems-analysis.info/int/Network_model_(operations_research)_%E2%80%94_%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC_%EB%AA%A8%EB%8D%B8#cite_ref-ru-wiki-max-flow_6-2)</sup> "Задача о максимальном потоке". *Википедия*. <a href="https://ru.wikipedia.org/wiki/Задача_о_максимальном_потоке" class="external autonumber" rel="nofollow">[6]</a></span>
7.  <span id="cite_note-goldberg-tarjan-1990-7">[↑](https://systems-analysis.info/int/Network_model_(operations_research)_%E2%80%94_%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC_%EB%AA%A8%EB%8D%B8#cite_ref-goldberg-tarjan-1990_7-0) Goldberg A. V., Tardos É., Tarjan R. E. (1990). "Network Flow Algorithms". In: *Paths, Flows, and VLSI-Layout*. Springer. <a href="https://www.cs.cornell.edu/~eva/Network.Flow.Algorithms.pdf" class="external autonumber" rel="nofollow">[7]</a></span>
8.  <span id="cite_note-ru-wiki-shortest-path-8">↑ <sup>[8.0](https://systems-analysis.info/int/Network_model_(operations_research)_%E2%80%94_%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC_%EB%AA%A8%EB%8D%B8#cite_ref-ru-wiki-shortest-path_8-0)</sup> <sup>[8.1](https://systems-analysis.info/int/Network_model_(operations_research)_%E2%80%94_%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC_%EB%AA%A8%EB%8D%B8#cite_ref-ru-wiki-shortest-path_8-1)</sup> "Задача о кратчайшем пути". *Википедия*. <a href="https://ru.wikipedia.org/wiki/Задача_о_кратчайшем_пути" class="external autonumber" rel="nofollow">[8]</a></span>
9.  <span id="cite_note-ru-wiki-mst-9">[↑](https://systems-analysis.info/int/Network_model_(operations_research)_%E2%80%94_%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC_%EB%AA%A8%EB%8D%B8#cite_ref-ru-wiki-mst_9-0) "Минимальное остовное дерево". *Википедия*.</span>
10. <span id="cite_note-ru-wiki-cpm-10">↑ <sup>[10.0](https://systems-analysis.info/int/Network_model_(operations_research)_%E2%80%94_%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC_%EB%AA%A8%EB%8D%B8#cite_ref-ru-wiki-cpm_10-0)</sup> <sup>[10.1](https://systems-analysis.info/int/Network_model_(operations_research)_%E2%80%94_%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC_%EB%AA%A8%EB%8D%B8#cite_ref-ru-wiki-cpm_10-1)</sup> "Метод критического пути". *Википедия*. <a href="https://ru.wikipedia.org/wiki/Метод_критического_пути" class="external autonumber" rel="nofollow">[9]</a></span>