[Graph Theory] Basic Concepts

Definition.

Graph G: a pair (V, E)

V(G): a set of vertices

E(G): a multiset of edges

$|G| = |V(G)|$: the order of G: order 은 vertex 갯수

$e(G) = |E(G)|$: the size of G: size 는 edge 갯수

Loop: an edge of size 1

graph 가 simple 하다: loop 나 multiple edge가 없다

 

u 와 v 가 adjacent: $uv \in E(G)$. 둘 사이 edge가 있다

v 와 e가 incident: $v \in e$, edge 중 하나에 포함된다

e 와 e'가 incident: $e \cap e' \neq \emptyset$ e랑 e' 는 공통의 vertex를 가진다. 연결되어있다.

u 는 v의 neighbor: $uv \in E(G)$, 두 vertex가 연결되어있다

$N_G(v)$: set of neighbors of v. v랑 연결된 애들

$d_G(v)$: the degree of $v$, v에 붙은 edge 갯수

 

Subgraph: $V(H) \subseteq V(G)$ and $E(H) \subseteq E(G)$.

Spanning Subgraph: $V(H) = V(G)$ : Vertex 는 싹 갖고오고 edge만 드문드문

$G[U]$: $U \subseteq V(G)$, and edge set $\{e \in E(G) : e \subseteq U  \}$ : subgraph of G induced by $U$. Vertex 는 subset이고, edge 는 U에 포함된 애들만 가져옴

induced subgraph: $H = G[U]$ 일 때. vertex는 선택, edge는 싹 가져옴

 

Clique: complete subgraph of G: Vertex 몇 개 골랐는데 걔들끼리 complete graph

$\omega(G)$: maximum size of a clique G: Vertex 몇개 골랐는데 걔들끼리 complete graph 가 되는 최대한.

Independent set (stable set): an empty induced subgraph of G: vertex 몇개 골랐는데 걔들끼리 non adjacent. 하나도 접점이 없음

$\alpha(G)$: maximum size of an independent set of G. 골랐는데 하나도 접점 없게 고를 수 있는 최대한.

 

r-partite: G의 vertex 가 union of r independent sets. : 골랐는데 걔들끼리 접점 없는 세트 r개로 딱 나눠떨어짐.

 

regular: 모든 vertices 가 같은 degree

k-regular: 모든 vertices 가 edge 가 k개

$\Delta(G) = max_v\{d_G(v)\}$, G 에서 가장 edge 많은 애가 가진 edge 갯수

$\delta(G) = min_v\{d_G(v)\}$, G에서 가장 edge 적은 애가 가진 edge 갯수

 

Lemma (Handshake Lemma)

Every graph contains even number of vertices with odd degree.

degree 합은 무조건 짝수다.

$\textit{Proof}$

$\sum d_G(v) = 2e(G)$

edge 가 두개씩 세지니까.

 

Directed graph (digraph) an ordered pair (V, E) where $E \subseteq V \times V$. e에 순서가 있다.

oriented graph: $\overrightarrow{uv} \in E(D)$, then $\overrightarrow{vu} \notin E(D)$. uv로는 한 방향만 있다.