그래프의 표현과 기본 성질 | SW 전공

1. 그래프의 구성

그래프 G=(V,E)는 정점 집합 V와 정점 사이 관계인 간선 집합 E로 구성된다.

무방향 그래프에서는 모든 정점 차수의 합이 2|E|이다. 방향 그래프에서는 진입차수 합과 진출차수 합이 각각 |E|이다.

정점 수가 V일 때 V×V 배열을 사용한다.

각 정점마다 연결된 이웃 목록을 저장한다.

트리는 사이클이 없는 연결 무방향 그래프이다. 정점이 V개인 트리는 간선이 정확히 V-1개이며, 임의의 두 정점 사이의 단순 경로가 하나뿐이다.

무방향 그래프의 간선이 {A-B, A-C, B-D, C-D}라 하자.

CODE코드 영역 안에서 좌우로 이동할 수 있습니다.

A ----- B
|       |
|       |
C ----- D

인접행렬과 인접리스트는 다음처럼 대응한다.

CODE코드 영역 안에서 좌우로 이동할 수 있습니다.

    A B C D            A: B, C
A [ 0 1 1 0 ]          B: A, D
B [ 1 0 0 1 ]          C: A, D
C [ 1 0 0 1 ]          D: B, C
D [ 0 1 1 0 ]

무방향 인접행렬은 주대각선을 기준으로 대칭이다. 자기 루프가 있으면 대각 원소가 1 또는 가중치를 가질 수 있다.

무방향 그래프의 차수 합은 2|E|이다. 완전 무방향 그래프 K_n의 간선 수는 n(n-1)/2, 완전 방향 그래프에서 자기 루프를 제외한 간선 수는 n(n-1)이다.

이분 그래프의 정점을 두 집합으로 나눌 수 있고 같은 집합 내부에는 간선이 없다. 완전 이분 그래프 K_{p,q}의 간선 수는 pq이다.

방향 그래프에서 u→v가 가능하다고 v→u도 가능한 것은 아니다.

정점이 V개인 단순 무방향 그래프에서 다음 조건은 서로 밀접하다.

단, 조건 일부만 보고 트리라고 단정할 때는 연결성 또는 사이클 여부가 함께 보장되는지 확인한다.

인접리스트에서 모든 정점의 이웃을 순회하면 무방향 간선은 양쪽 목록에 한 번씩 나타나 총 O(V+E)이다. 인접행렬은 모든 칸을 확인해 O(V²)이다.

PYTHON코드 영역 안에서 좌우로 이동할 수 있습니다.

adj = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C']
}

간선 존재 질의가 매우 많고 V가 작거나 밀집 그래프라면 행렬이, 대규모 희소 그래프에서 이웃 순회가 중심이면 리스트가 유리하다.