수학

그래프 이론 스케치

정점·간선, 차수, 경로, 오일러, 인접행렬.

기초

그래프

정점(꼭짓점)과 이를 잇는 간선으로 관계를 그립니다. 무방향이면 길이 양방향, 유방향이면 화살표입니다. 고리·다중간선을 허용하는지로 단순/다중 그래프를 나눕니다. 가중치는 거리·비용입니다. 지도·네트워크·분자가 같은 언어를 씁니다. 그림은 모델이지 현실 전부는 아닙니다.

차수와 핸드셰이킹

정점의 차수는 맞닿은 간선 수입니다. 모든 차수를 합하면 간선 수의 두 배입니다(핸드셰이킹 보조정리). 그래서 홀수 차수 정점은 짝수 개입니다. 정규 그래프는 모든 차수가 같습니다. 유방향에서는 진입·진출 차수를 따로 셉니다. 이 한 줄이 많은 존재 증명의 출발입니다.

경로와 오일러

경로는 정점을 따라가는 간선 열입니다. 연결 그래프에서 모든 간선을 정확히 한 번씩 지나는 회로가 오일러 회로이고, 홀수 차수가 0개일 때 가능합니다. 한붓그리기 문제의 해답입니다. 해밀턴 경로는 모든 정점을 한 번씩 — 조건이 훨씬 까다롭습니다. 최단경로는 가중치와 알고리즘(데이크스트라 등) 이야기입니다.

인접행렬

행·열이 정점이고, 간선이 있으면 1(또는 가중치)입니다. A²의 항은 길이 2 경로 수를 셉니다. 라플라시안 L = D − A 는 스펙트럼 그래프 이론으로 이어집니다. 희소 그래프는 리스트가 메모리에 유리합니다. 컴퓨터가 그림을 숫자로 읽는 방법입니다.

공식

핸드셰이킹

Σ deg(v) = 2 |E|

홀수 차수 정점은 짝수 개.

기호

|E| 간선 수
deg(v) 정점 v의 차수

오일러 회로 조건

연결 + 홀수 차수 0개

무방향. 오일러 경로(비회로)는 홀수 차수 0 또는 2.

인접행렬 제곱

(A²)_{ij} = (i→j 길이 2 보행 수)

단순 무가중 무방향 기준.

기호

A 인접행렬

핵심 표

나무	연결 + 사이클 없음. \|E\| = \|V\| − 1
이분 그래프	정점을 두 편으로 나눠 간선은 편 사이에만
완전 그래프 K_n	모든 쌍이 간선. 간선 수 n(n−1)/2