[기말고사] 6-(1). 그래프 종류

그래프 알고리즘 내용

• 그래프 데이터 구조
  • 종류
  • 매트릭스
  • 인접 리스트
• 그래프 탐색
  • BFS 및 응용
  • DFS 및 응용
• 탐욕적 그래프 알고리즘
• DP 그래프 알고리즘

그래프

• 그래프는 컴퓨터 과학의 통일 주제 중 하나입니다.
• 그래프 G = (V, E)는 정점 집합 V와 V에서 온 순서 있는 또는 없는 정점 쌍으로 구성된 간선 집합 E로 정의됩니다.
• 그래프와 네트워크의 예:
  • 도로 네트워크 모델링에서 정점은 도시나 교차점을 나타내며, 이들 중 일부 쌍은 도로/간선으로 연결됩니다.
  • 전자 회로에서, 교차점은 정점으로, 구성 요소는 간선으로 나타냅니다.
  • 소셜 네트워크
  • 월드 와이드 웹
  • 컴퓨터 프로그램 내의 제어 흐름
  • 항목 간의 쌍별 유사성'

그래프 용어

• 무방향 그래프에서 경로는 각 정점과 그 후속 정점 사이에 간선이 있는 정점의 시퀀스입니다.
• 무방향 그래프는 모든 정점 쌍 간에 경로가 있으면 연결되었다고 합니다.
• 무방향 그래프에서, 세 정점 이상을 포함하고 모든 중간 정점이 서로 다른 경로를 단순 사이클이라고 합니다.
• 트리(정확히는 자유 트리)는 비순환적이고 연결된 무방향 그래프입니다.
• 이 정의에 따르면, 루트로 지정된 정점이 없으며, 루트가 있는 트리는 하나의 정점이 루트로 지정된 트리입니다.

방향 그래프 vs 무방향 그래프

• 그래프 G = (V, E)가 무방향 그래프라면, 간선 (x, y)가 E에 포함되어 있으면 (y, x)도 E에 포함됩니다.
• 도시 간 도로 네트워크는 일반적으로 무방향 그래프입니다.
• 도시 내의 도로 네트워크는 거의 항상 방향 그래프입니다.
• 대부분의 그래프 이론에서는 무방향 그래프가 더 중요합니다.

가중 그래프 vs 비가중 그래프

• 가중 그래프에서는 각 간선(또는 정점)에 수치 값 또는 가중치가 할당됩니다.
• 도로 네트워크 그래프의 간선은 길이, 주행 시간 또는 속도 제한으로 가중될 수 있습니다.
• 비가중 그래프에서는 다양한 간선과 정점 간에 비용 구별이 없습니다.

단순 그래프 vs 비단순 그래프

• 단순 그래프: 두 정점 사이에 하나의 에지만 존재
• 비단순 그래프
  • 자기 루프: 하나의 정점을 포함하는 간선 (x, x)
  • 다중 루프: 두 정점 사이에 여러 개의 에지가 존재하는 경우를 의미

희소 그래프 vs 밀집 그래프

• 희소 그래프: 10개의 도시가 있고 그 중 몇 개만이 서로 직접적으로 도로로 연결되어 있을 때
  • 즉, 희소는 간선 적은 거 ∴ 간선 수 ∝ 정점 수
• 밀집 그래프: 10개의 도시가 있고 모든 도시가 서로 직접적으로 도로로 연결되어 있을 때
  • 즉, 밀집은 간선 많은 거 ∴ 간선 수 ∝ 정점 수^2

Cycle 그래프 vs  Acycle 그래프 // 자기 자신을 돌아올 수 있는가? 없는가?

• tree는 acycle이며, undirected graph이다.
• acycle + directed graph = DAG

Embedded vs Topological 그래프

• embedded는 기하학적인 위치를 할당 받았을 때
  • ex) Grid Graphs(격자) & planar graph(평면)
• topological은 연결 관계만 고려했을 때(기하학적 위치 X).
  • ex) TSP, 최단 경로