Day 02 · 방향이 있는 관계

A SMALL DETOUR

이번 회차, 내 속도로.

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

난이도·관심 주제 고르기

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

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

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

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

출발 · DAY 2방향·진입/진출 차수
1. 관심 주제오일러 경로·홀수 차수추가 01 · 새 추가 수업
복귀 · DAY 2원래 회차 이어가기

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

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

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

01 / UNDERSTAND

핵심 개념

방향 그래프(directed graph)의 엣지는 출발 노드와 도착 노드가 정해진 화살표입니다. ‘A가 B를 팔로우한다’는 A→B로 적고, B가 A를 팔로우하지 않으면 B→A는 없습니다. 송금, 논문 인용, 웹 링크, 업무 보고처럼 한쪽으로만 성립하는 관계가 여기에 속합니다. 방향이 없는 그래프는 무방향 그래프(undirected graph)라고 부릅니다.

방향이 생기면 노드의 연결 수도 둘로 나뉩니다. 노드로 들어오는 화살표 수가 진입 차수(in-degree), 나가는 화살표 수가 진출 차수(out-degree)입니다. 팔로워 수는 진입 차수, 팔로잉 수는 진출 차수에 해당합니다. 화살표 하나는 한 노드에서 나와 한 노드로 들어가므로, 모든 노드의 진입 차수 합과 진출 차수 합은 둘 다 화살표 수와 같습니다.

무방향 엣지 하나는 서로 반대 방향인 화살표 두 개로 바꿔 쓸 수 있습니다. 민수–지아 친구 관계는 민수→지아와 지아→민수입니다. 그래서 무방향 엣지 11개짜리 동아리 네트워크를 방향 그래프로 저장하면 화살표가 22개가 됩니다. 반대로 방향 그래프에서 화살표 머리를 지우면 누가 누구를 팔로우했는지, 서로 팔로우하는지 같은 정보가 사라집니다.

방향은 ‘어디까지 갈 수 있는가’도 바꿉니다. A→B와 B→C가 있으면 A에서 C로 갈 수 있지만 C에서 A로는 갈 수 없습니다. 길을 따라갈 때 화살표 방향을 지켜야 하기 때문입니다. 무방향 그래프에서는 성립하던 ‘내가 너에게 닿으면 너도 나에게 닿는다’가 방향 그래프에서는 성립하지 않을 수 있습니다.

방향 그래프에서는 들어오는 화살표(진입 차수)와 나가는 화살표(진출 차수)를 따로 세며, 각각의 합은 화살표 수와 같습니다.

02 / WORKED EXAMPLE∑

작은 예제로 따라가기

팔로우 화살표 5개 A→B, A→C, B→C, C→A, D→C에서 C로 들어오는 화살표는 A·B·D에서 오므로 C의 진입 차수는 3이고, 나가는 화살표는 C→A 하나라 진출 차수는 1입니다.

A는 진입 1·진출 2, B는 진입 1·진출 1, D는 진입 0·진출 1입니다. 진출 차수 합 2+1+1+1=5와 진입 차수 합 1+1+3+0=5는 모두 화살표 수 5와 같습니다.

A와 C는 서로 팔로우(A→C, C→A)하므로 방향을 지우면 A–C 엣지 하나가 됩니다. 화살표 5개를 방향 없이 묶으면 A–B, A–C, B–C, C–D 네 개의 엣지가 남습니다.

03 / EXPLORE

직접 실험해 보기

‘무방향’과 ‘방향(팔로우)’을 번갈아 고르며 같은 노드의 차수가 진입·진출로 나뉘는 모습을 확인하고, footer의 엣지 수가 어떻게 달라지는지 비교하세요.

LIVE EXPERIMENT · DIRECTION

같은 관계를 무방향과 방향으로 바꿔 보기

배지 = 차수 (연결된 선의 수)

사람을 눌러 차수를 확인하세요무방향에서는 화살표 없이 연결된 선의 수가 차수입니다.

사람	차수	이웃
민수	2	지아, 서준
지아	3	민수, 서준, 하린
서준	3	지아, 민수, 하린
하린	3	지아, 도윤, 서준
도윤	1	하린

04 / RECALL & PRACTICE

이번에는 직접 풀어 보세요

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

문제 1

세 사람의 송금 기록이 가→나, 가→다, 나→다, 다→가입니다. 각 사람의 진입·진출 차수를 적고, 방향을 지워 ‘거래한 적이 있는 사이’로만 그리면 엣지가 몇 개인지 구하세요.

힌트 보기

화살표 머리가 닿는 쪽이 진입입니다. 가→다와 다→가는 방향을 지우면 같은 쌍입니다.

풀이와 비교하기

가는 진입 1·진출 2, 나는 진입 1·진출 1, 다는 진입 2·진출 1이며 진입 합과 진출 합은 모두 4입니다. 방향을 지우면 가–나, 가–다, 나–다로 엣지 3개입니다.

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

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

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

방향이 있는 관계