9장 Graphs

undirected edge : 두 vertices를 있는 방향이 없는 선

directed edge : 두 vertices를 있는 방향이 있는 선

multiple edges : 같은 vertices를 잇는 여러개 edges

multiple directed edges : 같은 vertices를 잇는 방향이 같은 edges

loop : vertex 자기 자신을 연결하는 edge

undirected graph : vertices와 undirected edges의 모음

simple graph : multiple edges나 loops가 없는 undirected 그래프

multigraph : multiple edges를 가지나 loops는 가지지 않는 undirected 그래프

pseudograph : multiple edges와 loops를 가질 수 있는 undirected 그래프

directed graph : vertices와 directed edges의 모음

directed multigraph : multiple directed edges를 가질 수 있는 그래프

simple directed graph : loops나 multiple directed edges이 없는 directed 그래프

adjacent : 두 vertex 사이에 edge가 있을 때 둘이 adjacent 하다고 한다.

incident : 한 vertex가 어떤 edge의 끝점일 때 그 edge는 그 vertex와 incident하다고 한다. 

deg(v) : vertex v와 incident한 edge들의 갯수 (루프는 2번 카운트된다.), v와 연결된 edges의 갯수

deg-(v) :  v가 terminal vertex로서의 edges의 갯수. edges가 나가는 갯수

deg+(v) : v가 initial vertex로의 edges의 갯수. edges가 들어오는 갯수 

underlying undirected graph of a graph with directed edges : edges의 방향을 없앤 undirected graph

Kn (complete graph on n vertices) : 각각의 vertex 쌍이 edge로 연결되어 있는 undirected graph

bipartite graph : 한 그래프 V의 vertex set을 두개의 sub vertex set V1, V2로 나눌 수 있고 V1의 vertex는 V2의 vertex를 잇는 edge를 가진다. 이러한 그래프 V를 bipartite graph.

Km,n (complete bipartite graph) : m개의 vertex를 가진 첫번째 서브셋과 n개의 vertex를 가진 두번째 서브셋이 있을 때 첫번째 vertex와 두번째 서브셋의 vertex가 edge를 갖는 것.

Cn (cycle of size n), n >=3 : n개의 vertex들이 서로 edge로 이어져 마지막 vertex와 첫번째 vertex가 같은 graph

Wn (wheel of size n ), n>=3: 싸이클에 vertex 하나가 추가되서 그 vertex가 다른 vertex들을 연결 한 것 

Qn (n-cube), n>=1 : 길이가 n인 2^n개의 bit strings을 표현한 그래프. 두 vertex는 비트 차이가 하나일때 edge를 갖는다.

isolated vertex : 차수가 0인 vertex

pendant vertex : 차수가 1인 vertex

regular graph : vertex 차수가 모두 같은 그래프. 

subgraph  of a graph G = (V,E)

G1 U G2 (union of G1 and G2)

adjacency matrix : edge로 표현한 메트릭스

incidence matrix : edge와 vertex의 incidence로 표현한 메트릭스

isomorphic simple graphs : 두 그래프의 vertex가 V1에서 V2로 가는 일대일함수이면서 v1, v2와 f(v1), f(v2)의 edge도 일치할 때.

invariant : isomorphic graph가 가져야할 혹은 갖지 말아야할 속성. 예를 들면 노드수와 Edge수가 같아야 한다. 노드의 차수도 같아야 한다. 

simple path : 어느 한 edge를 한번 이상 지나지 않는 path

circuit : 시작과 끝이 같은 path

connected graph : 모든 vertex가 이어져 있는 undirected 그래프

strongly connected directed graph : 모든 두 노드가 path가 있는 directed 그래프

Euler circuit : 그래프의 모든 edge를  한번만 지나는 circuit.

Euler path :  모든 edge는 한번만 지나는 path

Hamilton circuit: 모든 vertex를 한번만 지나는 simple graph circuit.