[이산수학] 그래프

📌 들어가며

이번 글에서는 그래프(Graph)를 정리한다. 그래프는 인공지능의 뉴럴넷·계산 그래프와 직결되는 중요한 구조다.

그래프: 정점(vertex)의 집합 V와, 서로 다른 정점쌍을 연결하는 모서리(edge)의 집합 E로 구성된 구조. G = (V, E)

---

1. 그래프 용어

용어	정의
인접(adjacent)	두 정점이 모서리로 연결됨
근접(incident)	모서리가 두 정점을 연결함
N(v)	정점 v의 이웃 정점 집합
차수(degree) d(v)	정점 v에 근접하는 모서리 개수

💡 루프(자기 자신으로의 모서리)는 차수를 2로 계산한다. 한쪽으로 나가서 다른 쪽으로 들어오기 때문이다.

---

2. 그래프의 형태

형태	특징
단순 그래프	두 정점 사이에 모서리 하나만
다중 그래프	두 정점 사이에 둘 이상의 모서리
의사 그래프	루프를 허용
가중치 그래프	모서리에 가중치 부여 (AI에서 자주 등장)

---

3. 그래프의 표현 — 인접 행렬

그래프는 행렬(인접 행렬)로 표현할 수 있다. 각 정점을 행·열 인덱스로 두고, 이어진 점은 1, 아니면 0을 넣는다.

     A B C          A─B, B─C 연결이면
A [ 0 1 0 ]
B [ 1 0 1 ]   →   (i,j)가 연결되면 1, 아니면 0
C [ 0 1 0 ]

---

4. 뉴럴넷과 계산 그래프

💡 인공지능의 뉴럴넷은 노드(정점)와 가중치가 부여된 연결(모서리)로 이루어진 가중치 그래프로 볼 수 있다. 계산 그래프는 연산의 흐름을 그래프로 표현한 것으로, 순전파·역전파의 기반이 된다.

---

📝 정리

그래프
├─ 정의    G = (V정점, E모서리)
├─ 용어    인접·근접·차수(루프는 2)
├─ 형태    단순/다중/의사/가중치 그래프
├─ 표현    인접 행렬 (연결=1, 아니면 0)
└─ AI      뉴럴넷·계산 그래프 = 가중치 그래프

개념	한 줄 정의
정점/모서리	노드 / 연결
차수	정점에 붙은 모서리 수 (루프=2)
인접 행렬	그래프를 0/1 행렬로 표현
가중치 그래프	모서리에 값이 부여된 그래프

그래프는 관계를 표현하는 강력한 구조다. 특히 가중치 그래프와 인접 행렬 표현은 뉴럴넷과 계산 그래프의 기초가 되니, AI를 향한 발판으로 잘 잡아두자. 다음엔 순전파·역전파를 다룬다.