[CS | 자료구조 | 그래프]

📊

1. 그래프의 정의

2. 그래프 표현법

3. 필수 공식

4. 관련 문제

1. 그래프의 정의

• G = (V, E)

  V = 정점(V, vertex(버텍스), 노드)의 유한집합. V(G)

  E = 간선의 유한집합. E(G)

• 정점끼리 연결이 안되어있어도 그래프임 (단, 정점이 공백(공집합)은 아니어야함)

• 사이클이 발생해도 됨

• 계층적 구조를 가짐(비선형 구조)

• 탐색(DFS/BFS)

  • DFS : 깊이 우선 탐색 - 스택 사용

  • BFS : 너비 우선 탐색 - 큐 사용

• 그래프 유형(무방향/방향)

  • 연결 정도에 따라 구분

    • 완전그래프 : 전부 연결된 그래프=최대 간선을 갖는 그래프

      • 무방향 완전그래프의 최대 간선 수 : n(n-1)/2

      • 방향 완전그래프의 최대 간선 수 : n(n-1)

    • 연결 그래프 :

    • 단절 그래프 :

  • 간선의 방향에 따라 구분

    • 무방향 그래프

      • E(G) = (v1, v2) : v1과 v2 서로 인접, (v1, v2)는 v1과 v2에 부속

      • 완전그래프의 최대 간선 수 : n(n-1)/2

    • 방향 그래프

      • E(G) = <v1, v2> : v1 → v2 인 간선을 의미

      • 완전그래프의 최대 간선 수 : n(n-1)

2. 그래프 표현법

• 인접 행렬

  • 대각선(a-a)을 기준으로 본다!

    • 대칭 = 무방향

      • e(간선 개수) = 행렬의 1의 개수/2

      • 완전 연결그래프 일 때

      : e(간선 개수) = v(v-1)/2 = n (노드 개수)(n-1)/2

    • 비대칭 = 방향

      • 1의 개수 = e(간선의 개수)

      • → = 각 노드의 진출 차수, ↓ = 각 노드의 진입 차수

• 인접 리스트

  • 모든 !!! e(간선 개수)

3. 필수 공식

💡

n : 전체 노드의 수 | e(=B) : 간선 | h : 트리 높이 | Nx : 차수가 x인 노드 N의 수 |
T : 카탈린 수(=만들어질 수 있는 트리의 수)

$$① \ e = n -1 \\ - \\ (이진트리)\\ . \\ ② \ N_0 = N_2 + 1\\ - \\ ③ \ T = \ 1/(n+1) * \ _{2n}C_n \\ \ \ \ \ \ \ \ \ \ \ \ \ \ = \ {2n}!/((n+1) \ * \ n!)\\ - \\ (완전이진트리)\\. \\④ \ 2^{h-1}-1 < n ≤ 2^h-1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ (로그를 \ 취하면) => h-1 < log(n+1) ≤ h \\ \ \ \ \ \ \ \ \ \ => h = [log(n)] \\ \ \ \ \ \ \ =>O(log(n)) \\ - \\ ⑤ \ n = 2^h-1$$

4. 관련 문제

Uploaded by N2T