Graph
그래프 G는 (V, E)의 페어로 나타내고, 여기서 V는 vertices로써 노드들의 집합, E는 edges로써 vertices의 페어의 집합이다.
- Edge Types
Directed edge:
- ordered된 vertices 페어 (u, v)
- u는 origin/tail
- v는 destination/head eg. 비행 경로
Undirected edge - unordered된 vertices 페어 (u, v) eg. 양방향 도로
- Terminology
–이미지 추가–
Undirected Graph Edges는 endpoint들을 연결해준다. Edges are incident on endpoints. Adjacent vertices are connected. Degree is # of edges on a vertex. Parallel edges share same endpoints. Self-loop has only one endpoint. Simple graphs have no parallel or self-loops.
Directed Graph Edges go from tail to head. Out-degree is # of edges out of a vertex. In-degree is # of edges into a vertex. Parallel edges share tail and head. Self-loop has same head and tail. Simple directed graphs have no parallel or self-loops, but are allowed to have anti-parallel loops like f and a.
–이미지 추가–
Path A path is a sequence of vertices such that every pair of consecutive vertices are connected with an edge. A simple path is one where all vertices are distinct.
–이미지 추가–
Cycle A cycle is defined by a path that starts and ends at the same vertex. A simple cycle is one where all vertices are distinct. An acyclic graph has no cycles.
–이미지 추가–
Subgraph Let $G = (V, E)$ be a graph. We say $S = (U, F)$ is a subgraph of $G$ if $U \subset V$ and $F \subset E$. A subset $U \subset V$ induces a graph $G[U] = (U, E[U])$ where $E[U]$ are the edges in $E$ with endpoints in $U$. A subset $F \subset E$ induces a graph $G[F] = (V[F], F)$ where $V[F]$ are the endpoints of edges in $F$.
–이미지 추가–
Connectivity A graph $G = (V, E)$ is connected if there is a path between every pair of vertices in $V$. A connected component of a graph $G$ is a maximal connected subgraph of $G$.
Trees and Forests An unrooted tree $T$ is a graph such that $T$ is connected and $T$ has no cycles. A forest is a graph without cycles. In other words, its connected components are trees. Every tree on $n$ vertices has $n - 1$ edges.
Spanning Trees and Forests A spanning tree is a connected subgraph on the same vertex set. A spanning tree is not unique unless the graph is a tree. Spanning trees have applications to the design of communication networks. A spanning forest of a graph is a spanning subgraph that is a forest.
- Graph ADT 우리는 그래프를 세 개의 타입: Vertex, Edge, Graph로 추상화 시킨다. Vertex는 관련 객체 (예. 공항 번호)를 저장하고 getElement()로 이를 가져올 수 있다. Edge는 관련 객체 (예. 비행기편 번호, 비행 거리)를 저장하고 getElement()로 이를 가져올 수 있다.
–관련 method 추가–
Vertex 시퀀스는 vertex들의 나열으로써, 각 vertex 객체는 시퀀스에서 자신의 위치를 저장한다. Edge 시퀀스는 edge들의 나열으로써, 각 edge 객체는 시퀀스에서 자신의 위치를 저장한다. 또, 자신으로 인해 연결되는 두 개의 vertices를 가르킨다.
–이미지 추가–
-Adjacency List Structure
추가적으로, 각 vertex는 자신에 대해 incident한 edge들의 시퀀스를 저장하고, edge는 자신들의 endpoints의 incidence 시퀀스에서의 포지션에 대한 레퍼런스를 저장한다.
–이미지 추가–
- Adjacency Matrix Structure Vertex 배열은 각 vertex에 대해 인덱스 0, …, n - 1을 갖는다. 이를 2D-배열로 표현할 수도 있을 것이다. Non-adjacent하면 null 값을 가진다.
–이미지 추가–
-
Graph Traversals 그래프에 수행할 수 있는 근원적인 알고리즘은 edge와 vertice들을 traverse하는 것이다. Traversal이란 그래프의 vertices와 edges를 방문하는 체계적인 절차를 뜻한다. 예를 들어, 검색 엔진의 web crawler는 데이터 수집 부분으로써 hypertext document 그래프의 vertices(documents)와 edges(documents간의 하이퍼링크)를 방문하며 검사한다. 만약 traversal이 모든 vertices와 edges를 linear time에 방문을 한다면 효율적이라고 한다. 즉, $O(n + m), n = \text{number of vertices}, m = \text{number of edges}$
-
Graph Traversal Techniques 그래프의 모든 vertices와 edges를 체계적으로 방문하는 방법으로 두 가지 주요 방법이 있다. 1) Depth First Search 2) Breadth First Search
$n$개의 vertices와 $m$개의 edges를 가진 그래프에 대한 adjacency list representation이 주어졌을 때, 위 두 가지 방법은 O(n + m)의 시간 복잡도를 가진다.
- Depth First Search (DFS) 이 방법은 가능할때마다 outgoing edges를 따라서 아직 방문하지 않은 vertices를 방문하고, “어디든 갈 수 없는 상황”이면 backtrack하는 전략을 따른다. 만약 어떠한 edge가 새로운 vertex를 찾기 위해 사용된다면, 그 edge를 우리는 DFS edge라고 부르고, 그렇지 않다면 back edge라고 부른다.
–이미지 추가–
Leave a comment