[Graph] Graph란? (Undirected, Directed)

Definitions

• Graph, Vertex, Edge
  • 그래프 이론에 대해 공부하기 위해 가장 기본이 되는 정의(definition)부터 살펴보자.
  • 그래프(graph)와 정점(vertex or node), 그리고 에지(edge)에 대한 정의는 다음과 같다.
  • G(V, E) : Graph G는 V(vertex set)와 E(edge set)로 이루어져있다.

Undirected / Directed graph

• edge set을 어떻게 정해 주느냐에 따라 Undirected graph, Directed graph로 나뉘게 된다.

• Undirected graph

  • 대칭 행렬이다.

    • e = (a, b) = (b, a)
    • edge에 방향이 없어 (a,b)를 (b,a)로 나타내도 상관 없는 그래프를 의미한다.

  • 예) Snap Stanford의 Nodes : 334863, Edges : 925872인 Undirected graph 데이터

      1    88160
      1    118052
      1    161555
      .
      .
      .
      548368    548454
      548391    548411
      548411    548458

    • Node의 유니크한 숫자 개수는 334863개이며 한 쪽 방향의 Edge(line)의 개수는 925872개이다.
    • 만약, 해당 Undirected Graph data를 Matrix data로 사용하고 싶다면
    • Node를 정렬해서 Node의 index를 0 ~ 334863 로 재설정하고
    • 한쪽 방향의 edge만 표현 되어있으므로 반대 방향의 edge도 추가해야한다.
    • 또한 모든 edge에 element도 할당해줘야한다.

• Directed graph

  • 대칭 행렬이 아니다.

    • e = (a, b) ≠ (b, a)
    • edge에 방향이 있어 (a,b)와 (b,a)가 다른 그래프를 의미한다.

  • 예) Snap Stanford의 Nodes : 1005 , Edges : 25571인 Directed graph 데이터

      0 1
      2 3
      2 4
      .
      .
      .
      258 1003
      1003 258
      55 1004

    • Node는 0~1004로 표현 되어있으며 모든 Edge(line)의 개수는 25571개이다.
    • 만약, 해당 Directed Graph data를 Matrix data로 사용하고 싶다면
    • 모든 edge에 element도 할당해줘야한다.
    • 행,열에 해당하는 element도 할당해줘야한다.

• [Graph] SNAP Stanford의 Undirected Graph data를 Matrix data로 변환하는 방법

  • https://wooono.tistory.com/177

Self loop and paralled edge

• 자기 자신을 연결하는 edge 가 있을 수 있는데, 이를 loop 또는 self loop 라고 한다.
• 때에 따라 graph 는 두 vertex 에 대해 하나 이상의 edge 로 연결되어 있는 경우가 있는데
• 이를 multiple edge 또는 parallel edge 라고 한다.

Graph data site

• SNAP Stanford
  • https://snap.stanford.edu/data/