어떤 그래프 \(G\) 의 degree sequence는 각 점의 degree로 이루어지는 non-decreasing sequence이다. 즉, 이 sequence의 길이는 그래프의 꼭짓점의 수 \(V(G)\)가 된다. 분명 임의의 그래프가 주어졌을 때 degree sequence를 결정할 수 있지만, degree sequence에서 대응되는 그래프가 하나, 즉 대응되는 그래프가 모두 isomorphic 한지는 조금 생각해볼 문제이다. 이후 증명에서 나오겠지만 대응되는 그래프는 일반적으로 많이 나타난다.그 전에, degree sequence에서 그래프가 대응되는가도 확실하지 않다. 예를 들어 (1,1,1,1,1)은 대응되는 그래프가 존재하지 않는다.\[ \sum _{v \in V} \deg (v) = 2..

1. 상한graph \(G\)의 radius \(k\), maximum degree \(d = \Delta (G) \)에 대해 다음이 성립한다.\[|G| \le 1 + d \sum _{i=0} ^{k-1} (d-1)^i \] 증명\(z\)를 \(G\)의 central vertex로 놓자.\[D_i := \{v|v\in V \wedge d(v,z) = i\}\]점 집합 \(D_i\)를 \(z\)로부터의 거리가 \(i\)인 점들의 집합으로 놓자. 그러면 다음이 성립한다.\[V(G) = \bigcup _{i=0} ^k D_i \]정의에 의해 \(D_i \cap D_j = \emptyset \)이므로 \(|G| = \sum _{i=0} ^k |D_i|\)이다.여기서 귀납적으로 접근하면\(|D_0| = 1\)(c..

\(G = (V , E) \)가 non-empty graph라고 할 때, 임의의 점 \(v \in V\)에 대해 이웃한 점(neighbours)의 집합을 \(N _G (v) \) 또는 간략하게 \(N(v)\)라고 나타낸다. 이걸 더 일반적으로 확장시켜서, 어떤 점 집합 \(U \subset V \)에 대해 \(N(U)\)는 \(U = \{ u_1 , u_2 , \cdots , u_n \} \)으로 놓았을 때 다음과 같이 정의한다.\[N(U) = \bigcup _{i=1} ^n N(u_i) \setminus U\] 예를 들면 위 그래프에서 \(d(A) = 3\), \(U = \{A,B,C,G\} \)일 때, \(d(U) = 5\)이다. 어떤 점 \(v\)에 대해 \(d(v) = 0\)이면 \(v\)는 '고..

그래프를 행렬로 바꾸는 것을 생각해보았는데 이미 있더라고요. 인접행렬 : 점의 개수가 유한한 어떤 그래프에 대해 각 점에 넘버링을 했을 때 인접하게 연결된 점에다가 1, 아닌 점은 0을 대입시켜서 만드는 행렬. 즉, 인접행렬의 i행 j열은 점 i와 j가 연결되어 있으면 1, i와 j가 연결되어 있지 않으면 0이다. 예를 들어, 삼각형의 경우에는\[ \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix} \]가 되는 거죠. 재미있는 것은 인접행렬을 제곱하는 것인데, 그 결과가 Graph와 밀접한 관련이 있어요.위에 예로 나온 행렬을 제곱하면\[ \begin{pmatrix} 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1& 1 & 2 \end{..