Python Algorithm class (Graph - 1)

nathan·2021년 5월 11일
0

Python Algorithm class

목록 보기
17/27

Graph (그래프)

  • 그래프의 정의
  • 용어 설명
  • 그래프 표현

1. 그래프의 정의

  • 그래프(Graph) 혹은 무향 그래프(undirected graph) G는 다음의 두 집합 V, E로 정의 된다. : G = (V, E)

    • V : 정점(Vertex)들의 집합 (정점 대신 노드를 사용하기도 함)
    • E : 에지(Edge, 간선)들의 집합 (정점들 사이의 관계를 나타냄)
      • E의 원소(에지 or 간선)는 정점들의 쌍 (v, w) (순서 고려 X)
  • 방향 그래프(유향 그래프, directed graph or digraph) G는 두 집합 V, E로 정의 된다. : G = (V, E)

    • V : 정점들의 집합
    • E : 에지들의 집합
      • E의 원소(에지, 유향에지, 간선)는 정점들의 순서쌍 (v, w) (순서 고려)
  • 그래프의 graphical representation

    • vertex u는 u🔘
    • (무향) 그래프의 에지 (u, v) : u🔘⎯⎯⎯⎯🔘v
    • 방향 그래프의 에지 (u, v) : u🔘⟶🔘v
  • ex. 그래프 G = (V, E)

    • V = {a, b, c, d, e}
    • E = {(a,b), (b,c), (d,e), (a,e), (a,c)}
  • ex. 방향그래프 G = (V, E)

    • V = {a, b, c, d, e}
    • E = {(a,b), (b,c), (d,e), (a,e), (a,c)}

  • 쾨니히스베르크의 다리문제

프로이센의 쾨니히스베르크에는 프로셀 강이 흐르는데, 이 강에는 안 쪽에 두 개의 큰 섬과 각 섬을 연결하는 총 7개의 다리가 있었다. 이 때 7개의 다리들을 한 번씩만 건너면서 처음 시작한 위치로 돌아오는 길이 존재하는가?

  • 오일러(Euler)가 그러한 길이 존재하지 않음을 증명하였다. (한붓그리기 불가)
    • 오일러는 모든 정점이 짝수 개의 차수(Degree)를 갖는다면 모든 다리를 한 번씩만 건너서 도달하는 것이 성립한다고 말했다. (이 후 오일러의 정리..)
  • 이 문제는 평면 그래프에서의 한붓그리기 문제로 그래프 이론의 시초이다.
  • Euler Path : 꼭 시작 지점으로 돌아오지 않아도 됨
  • Euler Cycle : 꼭 시작 지점으로 돌아와야 함

그래프 응용 분야

(1) 도로망

  • 도시 : vertex
  • 두 도시를 직접 연결하는 도로 : edge

(2) 컴퓨터 망

  • 컴퓨터 : vertex
  • 두 컴퓨터 사이의 통신 link : edge

(3) 웹 그래프 (Web Graph)

  • web page : vertex
  • hiperlink : edge

(4) Social Networks

  • person : vertex
  • relation : edge

그래프와 관련한 문제들

(실생활 여러 문제들을 그래프로 모델링하여 해결 가능)

  • 도로망에서 도시 A로 갈 수 있는 모든 도시들 찾기
  • 도시 A에서 도시 B까지 가장 빨리가는 경로
  • 에지에 가중치를 둘 수도 있음
    • 지하철 두 역 사이를 지나는 데 걸리는 시간

2. 용어 설명

  • 그래프 G = (V, E)의 부그래프(subgraph)

    • V' ⊆ V and E' ⊆ E 인 그래프 G' = (V', E')를 G의 부그래프라고 함.
  • 완전 그래프(A complete graph) : 모든 두 정점 사이에 에지가 있는 그래프

  • v와 w가 인접하다(v is adjacent to w) : 모든 두 정점 사이에 에지가 있는 그래프

  • 에지 (v, w)는 정점 v, w에 부속(incident) 되어있다.

  • 정점 v로 부터 정점 w까지의 경로(path)

    • v0 = v, vk = w인 일련의 정점들 (v0, v1, ..., vk-1, vk)로서 다음 조건을 만족한다.
      • 0≤i≤k-1에 대하여 (vi, vi+1)은 E에 속한다.
      • 이 경로의 길이는 k이다.
  • v0, v1, ..., vk 들이 모두 다르면 이 경로를 단순경로(simple path)라고 함.

  • 정점 v로 부터 정점 w까지의 경로가 존재하면 w는 v로부터 도달가능(reachable)하다고 함.

  • 사이클

    • 1) 무향(or 양방향) 그래프에서의 사이클
      • 시작 정점과 마지막 정점이 같은 경로 (A -> B , B -> A 모두 가능)
      • ** 단순 사이클 : 시작 정점과 마지막 정점이 같은 것을 제외하고 어떤 정점도 중복되지 않는 사이클
    • 2) 방향 그래프에서의 사이클
      • 시작 정점과 마지막 정점이 같은 경로
      • ** 단순 사이클 : 첫 째 정점과 마지막 정점이 같은 것을 제외하고 어떤 정점도 중복되지 않는 사이클
  • 사이클 없는 (무향) 그래프 : 포리스트

  • 사이클 없고, 모든 에지가 연결된 (무향) 그래프 : 트리

  • 사이클 없는 방향 그래프 : DAG(directed acyclic graph)

  • 연결 그래프(connected graph) : 임의의 두 정점 u, v에 대하여, u에서 v까지의 경로가 존재하는 그래프

  • 강연결 (유향) 그래프 (strongly connected graph) : 임의의 두 정점 u,v에 대하여, u에서 v까지 경로가 존재하는 방향 그래프

  • 그래프 G의 (연결) 성분(connected component) : 그래프 G의 최대 연결 부그래프(maximal connected subgraph of G)

  • 방향그래프 G의 강연결성분(strongly connected component) : 방향 그래프 G의 최대 강 연결 부그래프(maximal strongly connected subgraph of G)

  • Strongly Connected Component (SCC)
    • 위 그래프는 정점 8개인 그래프를 3개의 SCC로 분할한 것
    • SCC는 일종의 서브 그래프로써, 하나의 SCC안에는 어떤 정점 u, v 두 개를 골라도 u->v로 가는 직, 간접적인 경로가 존재한다.
    • 또한 Maximal한 성질을 갖는데, 이 말은 각 SCC가 가능한 한 커야한다는 것
      • 예를들어, 우측의 SCC인 {c, d, h}의 하위 집합 중 {c, d} 역시 SCC의 첫 번째 성질은 만족하지만, 여기에 정점 h를 더 추가해도 여전히 성질이 만족되므로 h는 반드시 추가되어 있어야 한다.

참고 : Ries's Naver Blog


  • 가중치 그래프(weihgted graph) : 에지에 가중치(weight)가 있는 그래프
    • (V, E, W)로 정의됨
      W는 E에서 실수 집합 R로 매핑되는 함수
      • 에지의 가중치 : 비용, 길이, 용량 등 에지의 성질을 나타냄
        (에지 뿐만 아니라 정점에도 가중치를 둘 수 있다.)

profile
나는 날마다 모든 면에서 점점 더 나아지고 있다.

0개의 댓글