직관 — 거리 대신 연결만 남긴 지도
다섯 전시실 사이에 문이 나 있다고 하자. 방의 넓이와 복도의 실제 길이를 지우고, 서로 바로 오갈 수 있는 방만 선으로 이으면 길 찾기에 필요한 관계가 남는다. 점의 자리를 옮겨도 어느 방끼리 연결되는지가 같으면 같은 연결 모형이다.
전시실을 꼭짓점, 두 방 사이의 직접 연결을 변으로 나타낸다. 이 그래프는 함수의 입력과 출력을 좌표평면에 찍는 함수의 그래프와 다른 개념이다. 관계를 나타내는 점과 선에는 좌표축이 없어도 된다. 지하철 노선도, 친구 관계, 시험 시간표의 충돌처럼 ‘무엇과 무엇이 이어져 있나’만 중요한 문제가 모두 이 모형으로 옮겨진다.
그래프는 꼭짓점의 집합과 변의 집합으로 정한다
그래프는 꼭짓점들의 집합과 꼭짓점 사이 연결들의 집합을 묶은 것이다. 여기서는 꼭짓점이 하나 이상이고 유한하며, 방향이 없고, 자기 자신으로 돌아오는 변과 같은 두 꼭짓점을 잇는 중복 변이 없는 단순 무방향그래프만 다룬다.
| 기호 | 이름 | 원어 | 뜻 |
|---|---|---|---|
| 그래프 | graph | 꼭짓점과 변을 함께 정한 대상 | |
| 꼭짓점 집합 | vertex set | 대상들을 모은 집합 | |
| 변 집합 | edge set | 서로 다른 두 꼭짓점의 연결을 모은 집합 | |
| 변 | edge | 와 의 순서 없는 쌍 | |
| 꼭짓점 수, 변 수 | order, size | 각각 의 원소 수 |
우리교과서는 꼭짓점 집합과 변 집합을 로도 쓴다. 여기서 꼭짓점 이름 와 변 집합 는 문맥으로 구별한다. 변 와 는 같은 연결이므로 두 번 세지 않는다. 식 (1)은 꼭짓점 수 , 변 수 인 가상 전시실 모형이다.
식 (1)은 그림 1의 평면도에서 문이 있는 방끼리만 이어 얻었다. 아래 그래프에는 방의 넓이도, 문의 위치도 남아 있지 않다.
figures/floor_plan_graph.py와 처럼 변 하나로 직접 연결된 두 꼭짓점을 인접한다고 한다. 와 는 인접하지 않지만, 를 거쳐 갈 수 있다. 직접 연결과 여러 변을 통한 도달은 다르다.
이산수학의 그래프와 함수의 그래프는 같은 것인가요?
아니다. 함수의 그래프는 순서쌍 를 좌표평면에 찍은 점의 모임이고, 이산수학의 그래프는 꼭짓점 집합과 변 집합의 쌍이다. 식 (1)의 그래프는 다섯 점을 어디에 찍어도 같은 그래프이며 좌표축이 필요 없다.
실생활 상황은 어떻게 그래프로 나타낼까?
대상을 꼭짓점으로, 두 대상 사이에 성립하는지 묻는 관계를 변으로 정한다. 그 관계가 두 대상의 순서와 무관하고, 자기 자신과는 맺지 않으며, ‘있다·없다’로만 기록되면 단순 무방향그래프가 된다.
그림 1의 전시실은 다음 세 단계로 옮겼다.
- 대상 정하기 — 전시실 다섯 개가 꼭짓점이다.
- 관계 정하기 — ‘문 하나를 지나 바로 오갈 수 있다’를 변으로 한다. 에서 로 갈 수 있으면 에서 로도 갈 수 있어 순서가 없다.
- 버릴 정보 정하기 — 방의 넓이, 문까지의 거리, 문의 개수는 적지 않는다.
그래서 문은 여섯 개인데 변은 다섯 개다. 와 사이의 두 문은 ‘바로 오갈 수 있다’는 같은 사실이므로 변 하나로 적는다. 와 는 벽이 맞닿아 있지만 문이 없어 인접하지 않는다.
지하철 노선은 역을 꼭짓점, 한 정거장 구간을 변으로 놓는다. 친구 관계는 사람을 꼭짓점, 서로 친구인 두 사람을 변으로 잇는다. 무엇을 꼭짓점으로 정하느냐에 따라 같은 상황에서 다른 그래프가 나올 수 있으므로, 모형을 만들 때는 대상과 관계를 문장으로 먼저 적는다.
모든 관계가 그대로 단순 그래프가 되지는 않는다. ‘가 를 팔로우한다’는 한쪽만 성립할 수 있어 방향이 필요하다. 두 도시 사이의 하루 항공편 수처럼 횟수를 세면 같은 두 점 사이에 변이 여럿 생긴다. 이 과목은 단순 그래프만 다루므로 이런 상황은 ‘서로 팔로우한다’, ‘직항이 있다’처럼 있다·없다로 바꿔 기록한다.
같은 그래프인지는 그림이 아니라 변 목록으로 판단한다
두 그래프는 꼭짓점 집합과 변 집합이 각각 같으면 같은 그래프다. 점을 놓은 자리, 선의 길이와 모양, 선이 교차해 보이는지는 판단에 쓰지 않는다.
그림 2의 위아래 두 그림은 점의 배치가 다르다. 그러나 두 그림에서 변을 읽으면 모두 이고 꼭짓점도 같으므로, 식 (2)에 따라 같은 그래프다.
figures/same_connections.py그림에서 변 집합을 읽을 때는 선마다 양 끝의 이름을 한 번씩 적는다. 한 선을 와 로 두 번 적으면 변 수가 부풀려진다. 반대로 두 집합이 주어지면 꼭짓점을 아무 자리에나 찍고 변 목록의 두 점을 잇는다. 변에 나오지 않는 꼭짓점도 점으로 남겨 둔다.
식 (2)는 꼭짓점 이름까지 같을 것을 요구한다. 모양은 같아도 꼭짓점 이름이 과 로 다르면 이 정의로는 같은 그래프가 아니다.
그래프에서 선이 교차하면 꼭짓점이 하나 늘어나나요?
아니다. 그림에서 두 변이 겹쳐 보여도 그 교차점은 꼭짓점이 아니며, 꼭짓점 수는 변 목록이 정한 그대로다. 고가도로처럼 갈아탈 수 없는 교차는 세지 않고, 갈아탈 수 있는 교차로라면 처음부터 그 지점을 꼭짓점으로 정해 모형을 만든다.
같은 점으로 돌아오면 모두 같은 종류의 길일까?
아니다. 변의 반복과 꼭짓점의 반복을 따로 확인해야 한다. 먼저 가장 넓은 이동부터 정한다.
식 (3)처럼 차례로 이웃한 두 꼭짓점이 모두 변으로 이어진 나열을 보행이라 한다. 지나간 변의 개수 가 그 이동의 길이다. 나머지 용어는 보행에 반복 금지 조건을 하나씩 붙인 것이다.
| 용어 | 허용하는 이동 | 예 |
|---|---|---|
| 보행(walk) | 꼭짓점과 변을 반복해도 됨 | |
| 경로(trail) | 같은 변을 두 번 쓰지 않음 | |
| 단순경로(path) | 꼭짓점을 반복하지 않음 | |
| 회로(circuit) | 길이가 양수인 경로가 출발점으로 돌아옴 | (변 추가) |
| 단순회로(cycle) | 시작·끝을 제외한 꼭짓점도 반복하지 않는 회로 |
이 글은 우리교과서의 ‘경로=trail, 회로=circuit’ 관례를 따른다. 영어 자료의 path를 여기서는 단순경로라고 구별한다. 오일러 문제에서는 변 반복을, 해밀턴 문제에서는 꼭짓점 반복을 주로 살핀다.
figures/walk_types.py그림 3의 둘째 줄 는 변 를 한 번씩 쓰므로 길이 4인 경로다. 그러나 를 다시 만나므로 단순경로는 아니다. 첫째 줄 는 같은 무방향 변 를 왕복하므로 보행일 뿐, 경로가 아니다.
식 (1)에서는 회로가 삼각형 하나뿐이어서 회로와 단순회로의 예가 같아진다. 변 를 더해 두 삼각형이 를 공유하게 하면, 그림 3의 넷째 줄 는 여섯 변을 한 번씩 쓰고 돌아오는 회로다. 중간에 를 다시 만나므로 단순회로는 아니다. 이 나비 모양 그래프는 해밀턴그래프에서 다시 쓴다.
단순 그래프의 단순회로는 적어도 서로 다른 꼭짓점 3개와 변 3개를 써야 한다. 길이 1은 자기 연결을, 길이 2는 같은 변의 반복을 요구하기 때문이다.
연결과 부분그래프는 무엇을 보존할까?
서로 다른 어떤 두 꼭짓점 사이에도 단순경로가 있으면 연결그래프다. 원래 그래프의 꼭짓점과 변 가운데 일부를 골라 만든 그래프는 부분그래프다.
서로 다른 두 점 사이에 보행이 하나라도 있으면, 같은 꼭짓점 사이를 돌아 나온 구간을 잘라 내 단순경로를 얻는다. 그래서 ‘경로가 있다’로 연결을 정의해도 뜻이 같다. 꼭짓점 하나만 있는 그래프도 연결된 것으로 약속한다.
식 (4)가 우리교과서의 부분그래프 조건이다. 단, 도 그래프여야 하므로 에 고른 변의 양 끝점은 에 들어 있어야 한다.
figures/subgraph_connectivity.py그림 4의 위쪽 는 원래 변 를 고르지 않았지만, 식 (4)를 만족하므로 부분그래프다. 가운데처럼 원래 없던 를 넣으면 가 깨진다. 식 (1)은 연결되어 있지만, 아래처럼 변 를 지우면 와 사이를 오갈 수 없어 연결이 끊어진다.
이 연결 관계를 꼭짓점마다 수로 세면 다음 글의 차수가 되고, 표로 저장하면 인접행렬이 된다.
그래프는 꼭짓점 집합과 변 집합으로 정해지며, 그림의 배치와 선의 길이는 정보가 아니다. 단순 무방향그래프에서 경로는 변을, 단순경로는 꼭짓점을 반복하지 않는다.
연결그래프에서는 모든 꼭짓점끼리 인접하나요?
아니다. 연결그래프는 두 점 사이에 단순경로가 있기만 하면 되고, 모든 쌍이 직접 이어질 필요는 없다. 식 (1)의 는 변이 없지만 길이 2인 로 이어진다. 다섯 점의 모든 쌍을 직접 잇는다면 변이 10개 필요한데 식 (1)은 5개뿐이다.
변이 없는 그래프도 가능한가요?
가능하다. 꼭짓점 하나와 변 0개인 그래프는 이 단원의 범위에 든다. 꼭짓점이 둘 이상이고 변이 전혀 없으면 서로 오갈 수 없어 연결그래프가 아니다.
그래프의 흔한 오해
- 가까이 그린 두 점이나 맞닿은 두 대상은 인접한다. — 인접 여부는 변 목록으로만 판단한다. 그림 1의 와 는 벽이 맞닿아 있어도 문이 없어 변이 아니다.
- 같은 점을 다시 만나면 경로가 아니다. — 여기서 경로는 변의 중복을 금지한다. 는 경로지만 단순경로는 아니다.
- 부분그래프는 고른 꼭짓점 사이의 변을 모두 남겨야 한다. — 식 (4)는 변 집합이 포함되기만 하면 된다. 그림 4의 는 변 를 빼도 부분그래프다.
직접 해보기
새 그래프의 꼭짓점은 이고 변은 이다.
- 꼭짓점 수와 변 수를 구하고, 와 가 인접하는지 판단하시오.
- 의 길이를 구하고 보행·경로·회로·단순회로 여부를 판단하시오.
- 가 경로인지 판단하시오.
- 변 만 지운 그래프가 원래 그래프의 부분그래프인지, 여전히 연결되어 있는지 설명하시오.
- 다음 관계 가운데 그대로 단순 무방향그래프의 변으로 쓸 수 있는 것을 고르고, 나머지는 어떻게 바꿔 기록하면 되는지 쓰시오. (가) 두 역이 한 정거장 떨어져 있다. (나) 가 에게 문자를 보냈다. (다) 두 도시 사이의 하루 직항 편수.
답과 풀이
- 꼭짓점은 4개, 변은 5개다. 변 목록에 가 없으므로 두 점은 인접하지 않는다.
- 의 3개 변을 쓴다. 모두 다르고 출발점 로 돌아오며 중간 꼭짓점도 겹치지 않으므로 네 용어 모두에 해당한다. 길이는 3이다.
- 와 는 같은 변이다. 이를 두 번 써서 경로가 아니며, 길이 3인 보행이다.
- 원래 변만 골랐으므로 식 (4)에 따라 부분그래프다. 남은 변 로 를 따라 네 점을 차례로 지날 수 있으므로 연결은 유지된다.
- (가)만 그대로 쓸 수 있다. 두 역의 순서와 관계없고 자기 자신과는 맺지 않는다. (나)는 방향이 있으므로 ‘서로 문자를 주고받았다’로, (다)는 횟수이므로 ‘직항이 있다’로 바꾸면 단순 그래프의 변이 된다.
더 읽기
- 교육부 2022 개정 교육과정 고시 — 별책20 이산 수학 [12이수04-01]과 단순 그래프 범위의 근거. ‘실생활 상황은 어떻게 그래프로 나타낼까’ 절이 이 성취기준을 따른다.
- 우리교과서 이산 수학 공개본 — 인쇄127쪽의 , 인쇄129쪽의 같은 그래프·부분그래프와 인쇄143쪽의 경로·회로 정의를 대조했다. 본문의 전시실과 연습은 별도로 구성했다.
- Levin, Graph Theory Introduction — 꼭짓점·변 집합으로 그래프를 정의하고 그림의 배치와 연결을 구별한다.
영상 노트
- 00:00 그림 1의 평면도에서 넓이와 거리를 지우고 문만 남겨 식 (1) 만들기
- 00:50 문 두 개는 변 하나, 벽만 닿은 B와 D는 변 없음 — 모형화 세 단계
- 01:40 그림 2의 두 배치에서 변 목록을 읽어 식 (2)로 같은 그래프 판정하기
- 02:30 식 (3)의 보행에서 출발해 그림 3의 다섯 줄로 변 반복과 꼭짓점 반복 표시하기
- 03:40 그림 4로 식 (4)의 부분그래프 판정과 변 CD를 지운 뒤 연결이 끊기는 모습 보기
지도에서의 위치
- 2026-11-16 · 에이전트 초안
- 2026-11-17 · 전수 검수 반영 — 실생활 상황을 그래프로 옮기는 절차와 단순 그래프 조건, 같은 그래프·부분그래프의 식, 회로와 단순회로를 가르는 예와 표 순서대로 펼친 이동 그림, 함수의 그래프와의 차이 질문, 해보기 5문항 추가, 흔한 오해를 그림의 사례로 반박 (에이전트 수정, 그림 1→4)
- 2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림