Day 01 · 점과 선으로 관계 적기

A SMALL DETOUR

이번 회차, 내 속도로.

기초를 더 짚거나 궁금한 주제로 잠깐 넓혀 보세요. 최대 3단계를 거쳐 DAY 1로 돌아옵니다.

난이도·관심 주제 고르기

이번 회차는 어느 속도로 볼까요?기초부터새 보충 수업부터 짚어요현재 수준으로관심 주제부터 살펴봐요한 걸음 더새 심화 수업까지 넓혀요

더 살펴볼 주제 1~2개 선택오일러 경로·홀수 차수추가 01 · 새 수업 · 1회차에서 노드·엣지·이웃을 배운 뒤, 그래프 이론의 첫 문제를 차수로 직접 풀어 봅니다.동형·불변량추가 02 · 새 수업 · 1회차의 ‘노드의 위치와 선의 길이는 정보가 아니다’를 정확한 정의로 확인하는 심화 수업입니다.방향·진입/진출 차수DAY 2 · 팔로우·인용처럼 한쪽으로만 성립하는 관계에서 진입·진출 차수를 따로 세는 법을 다시 익힙니다.가중치·경로 비용DAY 3 · 홉 수와 가중치 합을 구분해야 경로 비용과 최단 경로를 올바르게 비교할 수 있습니다.이분·다중·하이퍼그래프DAY 4 · 이분·다중·하이퍼그래프를 구분하면 실제 데이터를 어떤 그래프로 옮길지 판단할 수 있습니다.관계 타입·관계 속성DAY 27 · 엣지에 숫자 하나 대신 타입과 속성을 붙이는 속성 그래프의 관계로 확장해, 방향·가중치가 데이터베이스에서 어떻게 쓰이는지 봅니다.

1/2개 선택 · 새 보충·심화 수업과 본과정 다시 읽기를 선택할 수 있어요.

이렇게 다녀와요 1단계 · 약 12분

출발 · DAY 1노드·엣지·이웃
1. 관심 주제오일러 경로·홀수 차수추가 01 · 새 추가 수업
복귀 · DAY 1원래 회차 이어가기

오일러 경로·홀수 차수 · 1회차에서 노드·엣지·이웃을 배운 뒤, 그래프 이론의 첫 문제를 차수로 직접 풀어 봅니다.

선택과 경로 기록은 이 브라우저에 저장됩니다. 본과정의 회차 완료와는 별도입니다.

복귀: DAY 1 → 본과정 다음 회차: DAY 2

01 / UNDERSTAND

핵심 개념

그래프(graph)는 대상과 관계만 남긴 그림입니다. 대상 하나를 노드(node, 꼭짓점)로, 두 대상 사이의 관계 하나를 엣지(edge, 간선)로 적습니다. 사람·역·논문·상품처럼 하나씩 셀 수 있는 것은 노드가 되고, 친구·이웃 역·인용·함께 구매처럼 둘을 잇는 사실은 엣지가 됩니다. 노드를 어디에 그리는지, 선이 얼마나 긴지는 정보가 아닙니다. 누가 누구와 이어졌는지가 같으면 같은 그래프입니다.

엣지로 직접 이어진 노드를 서로의 이웃(neighbor)이라고 합니다. 이 과정의 실험에서 계속 쓰는 동아리 네트워크는 민수·지아·서준·하린·도윤·유나·태오·보라 8명과 친구 관계 11개로 이루어져 있습니다. 노드 수는 보통 N, 엣지 수는 E 또는 m으로 적으며, 이 그래프에서는 N=8, E=11입니다. 두 무리 {민수, 지아, 서준, 하린}과 {도윤, 유나, 태오, 보라}를 하린–도윤 엣지 하나가 잇고 있습니다.

그래프 이론의 출발점으로는 흔히 오일러(Euler)의 쾨니히스베르크 다리 문제를 꼽습니다. 1735년에 발표되어 학술원 논문집 1736년 권에 실린 풀이에서, 오일러는 땅덩어리 4곳을 점으로, 다리 7개를 선으로 줄인 뒤 ‘모든 다리를 한 번씩만 건너는 산책’이 불가능하다는 것을 보였습니다. 지도의 모양을 지우고 연결만 남기자 문제가 풀린 것입니다.

그래프로 옮길 때는 무엇을 버렸는지도 기억해야 합니다. 친구 관계를 엣지 하나로만 적으면 얼마나 친한지, 언제부터 알았는지, 누가 먼저 연락했는지는 사라집니다. 이런 정보가 필요하면 다음 회차부터 배우는 방향·가중치·여러 종류의 엣지를 더합니다.

대상은 노드, 대상 사이의 관계는 엣지로 적고, 엣지로 직접 이어진 노드가 이웃입니다.

02 / WORKED EXAMPLE∑

작은 예제로 따라가기

민수에게 붙은 엣지는 민수–지아, 민수–서준 두 개이므로 민수의 이웃은 지아와 서준, 2명입니다.

하린에게 붙은 엣지는 지아–하린, 서준–하린, 하린–도윤이므로 하린의 이웃은 지아·서준·도윤, 3명입니다.

민수와 도윤은 직접 이어지지 않았으므로 이웃이 아닙니다. 둘 사이에는 지아(또는 서준)와 하린을 거쳐 가는 길이 있을 뿐입니다.

03 / EXPLORE

직접 실험해 보기

노드를 하나씩 눌러 강조되는 이웃과 엣지를 확인하고, footer의 이웃 수를 보며 이웃이 가장 적은 두 사람을 찾으세요.

LIVE EXPERIMENT · NODES & EDGES

노드를 눌러 이웃과 엣지 세기

먼저 예측: 이웃이 가장 많은 사람은 누구일까요? 노드를 눌러 확인해 보세요.

노드를 눌러 보세요노드는 대상(사람), 엣지는 관계(서로 아는 사이)입니다.

엣지 목록 11개

민수–지아민수–서준지아–서준지아–하린서준–하린하린–도윤도윤–유나도윤–태오유나–태오유나–보라태오–보라

04 / RECALL & PRACTICE

이번에는 직접 풀어 보세요

정답을 보기 전에 계산과 이유를 적어 보세요. 해설과 비교하고 확인 표시를 남기면 완료할 수 있습니다.

문제 1

도서관 대출 기록을 그래프로 그리려 합니다. 회원 3명(가, 나, 다)과 책 2권(X, Y)이 있고, 가는 X를, 나는 X와 Y를, 다는 Y를 빌렸습니다. 노드 수, 엣지 수, X의 이웃을 적으세요.

힌트 보기

회원과 책을 모두 노드로 두고, ‘빌렸다’는 사실 하나를 엣지 하나로 셉니다.

풀이와 비교하기

노드는 회원 3명과 책 2권으로 5개, 엣지는 가–X, 나–X, 나–Y, 다–Y로 4개입니다. X의 이웃은 X를 빌린 가와 나입니다.

내 풀이를 해설과 비교하고 다른 점을 확인했어요.

풀이와 확인 표시는 이 브라우저에 저장됩니다.

더 깊이 읽기

예제와 실험 데이터는 이 과정을 위해 만든 것입니다. 원문은 선택 자료이며, 강의와 직접 풀기만으로도 다음 회차를 이어갈 수 있습니다.

Seven Bridges of KönigsbergWikipedia Solutio problematis ad geometriam situs pertinentis (E53)Euler (1736) · Euler Archive Network Science, Chapter 2: Graph TheoryBarabási (2016)

이 자료는 개념 학습용입니다. 실제 데이터베이스·라이브러리·플랫폼의 동작과 설정은 제품과 버전마다 다를 수 있습니다.

점과 선으로 관계 적기