그래프 이론 (Graph Theory) - 1. 그래프에 대해서

알고리즘에서 ‘그래프 이론’은 꽤나 큰 파이를 차지하고 있다.
이번에는 이러한 그래프 이론은 무엇인지, 조금 깊게 파헤쳐보고 정리해보려한다.

ℹ️ 목차

그래프 이론
│
├── 1. 그래프에 대해서
│   ├── 1.1 그래프의 정의
│   └── 1.2 핵심 용어
│
├── 2. 그래프의 표현 방법
│   ├── 2.1 인접 행렬 (Adjacency Matrix)
│   └── 2.2 인접 리스트 (Adjacency List)
│
├── 3. 그래프의 종류
│   ├── 3.1 방향 그래프 (Directed Graph)
│   ├── 3.2 무방향 그래프 (Undirected Graph)
│   ├── 3.3 가중치 그래프 (Weighted Graph)
│   ├── 3.4 연결 그래프 (Connected Graph)
│   ├── 3.5 비순환 그래프 (Acyclic Graph)
│   │   └── DAG (Directed Acyclic Graph)
│   ├── 3.6 이분 그래프 (Bipartite Graph)
│   ├── 3.7 완전 그래프 (Complete Graph)
│   ├── 3.8 트리 (Tree)
│   │   ├── 일반 트리
│   │   ├── 이진 트리 (Binary Tree)
│   │   ├── 이진 탐색 트리 (BST)
│   │   ├── AVL 트리
│   │   ├── 레드-블랙 트리
│   │   ├── B-트리
│   │   └── 힙 (Heap)
│   └── 3.9 평면 그래프 (Planar Graph)
│
└── 4. 연관 알고리즘
    ├── 4.1 그래프 탐색
    │   ├── DFS (Depth-First Search)
    │   └── BFS (Breadth-First Search)
    │
    ├── 4.2 최단 경로
    │   ├── Dijkstra
    │   ├── Bellman-Ford
    │   └── Floyd-Warshall
    │
    ├── 4.3 최소 신장 트리 (MST)
    │   ├── Kruskal
    │   └── Prim
    │
    ├── 4.4 위상 정렬 (Topological Sort)
    │   ├── 진입 차수 방법 (Kahn's Algorithm)
    │   └── DFS 방법
    │
    ├── 4.5 트리 알고리즘
    │   ├── 트리 순회 (Tree Traversal)
    │   └── 최소 공통 조상 (LCA)
    │
    └── 4.6 유니온 파인드 (Union-Find)
        ├── 기본 구현
        ├── 경로 압축
        └── Union by Rank

🅿️ 포스트 목록

그래프 이론 (Graph Theory) - 1. 그래프에 대해서

그래프 이론 (Graph Theory) - 2. 그래프의 표현 방법

 

---

1️⃣ 그래프에 대해서

그래프란 현실에 존재하는 연결관계를 추상화하여 점과 선으로 모델링한 결과물

✅ 그래프의 정의

그래프는 관계(Relation)를 표현하는 추상적 구조이며, 현실의 개체를 소프트웨어로 모델링한 산출물의 일부이다.

🔹존재와 연결

현실의 존재(Entity)는 정점(Vertex)으로, 연결(Connection)은 간선(Edge)로 나타낸다.

이는 독립된 개체와 개체 간의 관계를 소프트웨어로 나타내는 방법이다.

 

🔹구조와 의미

연결에 대해서 두 가지 관점으로 분리하여 생각할 수 있다.

구조 : '어떻게' 연결되어 있는가? (그래프를 바라보는 전체적인 관점)

의미 : '무엇'이 연결되어 있는가? (그래프의 Component를 분석하는 관점)

 

🔹현실을 추상화

복잡한 현실의 연결성을 점(정점)과 선(간선)으로 단순화하여 보이지 않는 관계를 가시화 시키는것이 그래프 이론의 개념.

예로 아래와 같은 현실을 추상화하여 그래프화할 수 있다.

1. 도시(정점) - 도로(간선)
2. 사람(정점) - 친구관계(간선)
3. 컴퓨터(정점) - 네트워크(간선)

 

현실의 연결성을 그래프로 추상화

정점과 간선이 '무엇'이냐라는 의미론적인 부분과 '어떻게' 연결되어 있는지가 중요한 자료구조.

연결되어 있는 구조에 따라서 그래프의 종류가 나뉘며, 이를 관계성(Relationality)이라고 부른다.

 

위 그래프와 같이 현실에서의 위치를 정확히 반영할 필요가 없고, 어떤 지역이 어떻게(고속도로) 연결되어 있는지를 단순하게 추상화한 것을 볼 수 있다. 이처럼 그래프는 정점과 간선으로 중요하게 생각되는 부분에 대해 관계성을 나타낼 수 있다.

 

🔹계층성과 평등성

현실의 연결관계를 추상화할 때 중요한 점은 연결관계의 특성을 그대로 반영하는 것이다.

두 개체의 연결관계가 '친구'일 경우, 두 개체는 평등하다고 볼 수 있다. (관계의 높낮이 관점에서 보았을 때.)

만약 부모-자식 관계일 경우에는 이러한 높낮이를 계층을 통해 표현해야 한다.

 

이러한 계층은 '트리' 혹은 '방향 그래프'를 통해 상하 관계 또는 선후 관계(의존성)로 추상화할 수 있다.

평등 관계일 경우에는 방향성이 없는 즉, 무방향 그래프로 대칭적 관계임을 표현할 수 있을 것이다.

 

위의 개념과 기법들을 활용하여 우리는 복잡한 현실의 연결관계를 추상화를 통해 단순하게 표현하고 관리할 수 있다.

(수십억 노드로 연결된 네트워크 망, 80억 인구의 관계, 뇌 속 860억의 뉴런 등을 그래프로 단순화할 수 있다니 얼마나 편리한가.)

 

🔹그래프의 가치

소프트웨어 속 그래프를 통해 우리는 아래와 같은 일들을 할 수 있다.

1. 패턴 인식
   • 현실에서는 보이지 않는 것들을 시각화
   • 예시 : 커뮤니티 구조, 영향력의 흐름, 취약점
2. 추론의 도구
   1. A와 B가 친구, B와 C가 친구일 경우 A와 C가 친구일 가능성을 추론
   2. 관계를 통한 추천 시스템
3. 최적화
   1. 더 나은 해답을 탐색
   2. 최단 경로 : 효율성 탐색
   3. 최소 신장 트리 : 비용 절감
4. 분류
   1. 자료구조의 종류를 통해 현실의 복잡성을 특징이라는 큰 틀에서 쉽게 이해.
   2. 트리 : 계층적, 순환 없음.
   3. 이분 그래프 : 두 집단으로 분리.
   4. 완전 그래프 : 모두 연결.

---

✅ 핵심 용어

🔹정점 (Vertex/Node)

    🔸그래프를 구성하는 기본 단위

    🔸 보통 V로 표기, 개수는 |V| 또는 n

    🔸 데이터를 저장할 수 있음

🔹간선 (Edge)

    🔸 두 정점을 연결하는 선

    🔸 보통 E로 표기, 개수는 |E| 또는 m

    🔸 관계, 연결, 경로를 나타냄

🔹인접 (Adjacent)

    🔸 두 정점이 간선으로 직접 연결된 상태

    🔸 u와 v가 간선 (u, v)로 연결되면 "u와 v는 인접하다"

    🔸 인접한 정점을 이웃(neighbor)이라고도 함

🔹차수 (Degree)

    🔸 무방향 그래프: 정점에 연결된 간선의 개수

        ▪️deg(v) = 정점 v의 차수

        ▪️ 예: 정점에 3개의 간선이 연결되어 있으면 차수는 3

    🔸 방향 그래프:

        ▪️ 진입 차수 (In-degree): 정점으로 들어오는 간선의 수

        ▪️ 진출 차수 (Out-degree): 정점에서 나가는 간선의 수

        ▪️ deg(v) = in-deg(v) + out-deg(v) //총합

🔹경로 (Path)

    🔸 정점들의 연속된 나열

    🔸 경로 상의 모든 간선이 존재해야 함

    🔸 경로의 길이: 지나는 간선의 수

    🔸 단순 경로 (Simple Path): 같은 정점을 두 번 이상 지나지 않는 경로

🔹사이클 (Cycle)

    🔸 시작 정점과 끝 정점이 같은 경로

    🔸 같은 간선을 두 번 이상 지나지 않음

    🔸 단순 사이클: 시작/끝 정점을 제외하고 같은 정점을 두 번 지나지 않음

🔹가중치 (Weight)

    🔸 간선에 할당된 값

    🔸 거리, 비용, 시간, 용량 등을 나타냄

    🔸 w(u, v) = 간선 (u, v)의 가중치

🔹거리 (Distance)

    🔸 두 정점 사이의 최단 경로의 길이

    🔸 dist(u, v) = u에서 v까지의 최단 거리