viewimage.php?id=20bcc42e&no=24b0d769e1d32ca73cec85fa11d028318672c324147e3f6f5673e300cbe709253b7a9a518d075ba3f2f7da89a0fa2ea36a04fb4c960b1fbd5a1f39f4c79c8ed2

음... 사실 이제 학부 수학 같은건 기억도 안 나는 사람이 무슨 글을 쓸 수 있을까.


디씨에 쓰기 좋은 수학글은 좀 인스턴트식으로 보고 바로 오~ 할 수 있는 내용이 좋다고 생각을 하는데..

왜냐고? 여기서 아무리 글을 쓰고 소개를 잘 해봐야 얼마나 많은 사람이 교과서, 논문, 참고 문헌 찾아보겠어.

(혹시 나만 안 찾아보나? 다들 수학이 너무 궁금해서 그런거 다 뒤져봐?)


그리고 기초 지식이 너무 많이 필요해도 어렵지. 과목을 들었다고 거기에 있는 내용을 다 이해하는 것도 아니구...

그래서 선대에서 고유값을 구할 수 있는 정도의 친구들이 이해할 정도의 내용과 이해했다면 풀 수 있는 문제 정도를 낼 예정.

간단한 증명은 있을 수 있으나, 아무래도 인스턴트식 수학이 제 맛이지!


내가 배울 때 그래프는 보통 G = (V, E)로 쓰더라. V는 vertex(꼭지점), E는 edge(변).

내가 앞으로 다룰 그래프는 다음 성질을 만족하는 그래프들이야. 한글로 쓰려니 어색하다.

1. (finite) 꼭지점 수는 유한
2. (undirected) 변에는 방향이 없음
3. (simple) 아래와 같은 녀석들을 가지지 않는다.



viewimage.php?id=20bcc42e&no=24b0d769e1d32ca73cec85fa11d028318672c324147e3f6f5673e300cbe709253b7a9a518d075ba3f2f7da89a0fa2ea36a04fb4cc05616ef021b3ff5c79c8ed2


꼭지점과 변을 규정해주면 그래프에 대해서 알 수 있겠지?


예) Hamming Graph H(n, q)의 경우

V : {0, 1, 2. ,,, . q-1}^n

E : 두 점의 n개의 좌표 중 정확하게 하나가 차이나는 경우 그 두 점을 변으로 잇는다.


예를 들어서 H(3, 2)는 이렇게 되겠지.



viewimage.php?id=20bcc42e&no=24b0d769e1d32ca73cec85fa11d028318672c324147e3f6f5673e300cbe709253b7a9a518d075ba3f2f7da89a0fa2ea36a04fb4c915f1ab0511e6ff8c79c8ed2



이런 그래프들에 대해서 인접행렬을 정의하고 고유치를 구하고, 그 의미를 찾아보는게 대수적 그래프론의 기초야.

예를 들어서 저 H(3, 2)의 경우 꼭지점의 수가 8개니까 8*8인 인접행렬을 가지고, 고유치는 3, 1, 1, 1, -1, -1, -1, -3이 나오게 되지.

인접행렬은... 정의만 보면 |V|x|V| 행렬이고 (i, j) 성분이 i와 j가 변이 이어져있으면 1, 아니면 0인 행렬이야.

예시 안 쓰고 텍스트로 설명하긴 좀 그러니까 다음 시간에 예를 들어서 성질과 함께 제대로 소개할게.


이 코너는 이렇게 진행할 예정인데... 의미는.. 뭐 딱히 있겠어? 선형대수로 고유값을 이렇게 구할 수 있다 정도?


1. (필요하다면) 새로운 정의를 소개한다.

2. (필요하다면) 고유치를 구하는 테크닉을 소개한다.

3. 새로운 정의나 테크닉을 적용하는 예시를 소개한다.

4. 글에 있는 내용을 대충 훑어보고 풀 수 있는 문제를 소개한다.


오늘 새벽이나 내일 하나 써보도록 할게. 첫 글에서는 아래와 같은 기본적인 그래프들의 인접행렬의 고유값을 구해볼거야.

1. 꼭지점의 갯수가 n개인 완전그래프 K_n

2. 꼭지점의 갯수가 n개인 사이클 C_n

3. 꼭지점의 갯수가 n개인 경로 P_n

4. 꼭지점의 갯수가 n+m개인 완전이분그래프 K_(n,m)


엄청 재밌을거라곤 생각하지 않지만, 내가 학부 2~3학년 때 수업으로 들을 때는 선형대수로 이런걸 할 수 있다는게 좀 신기했었어.

그냥 특수한 행렬의 고유값을 구하는 문제라고 생각하고 가볍게 봐도 무방해.