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.
'공부 > 이산수학' 카테고리의 다른 글
| 8장 Relations (0) | 2011.06.22 |
|---|
