그래프

이 개념 위에 세워진 것

이 개념을 언급하는 페이지

• 무작위 행보

  … 돌아오는 길의 수는 카탈랑 수 \frac{1}{n+1}\binom{2n}{n} 입니다. 직선 대신그래프위를 걸을 수도 있습니다. 점마다 거기서 나가는 선 가운데 하나를 무작위로 골라 옮겨 가는 것입니다. 어느 …

• 비둘기집 원리

  … 모임 안에서 아는 사람 수가 같은 두 사람이 반드시 있습니다. 사람을 점, 아는 사이를 선으로 그린그래프에서 한 점에 닿은 선의 개수(차수)가 곧 아는 사람 수입니다. n 명이면 그 수는 0부터 n-1 까지 n …

• 동치관계와 분할

  … 동치관계를 만듭니다. 각 동치류는 한 출력값으로 가는 입력 전체, 곧 그 값의 원상입니다. 방향 없는그래프에서 '길로 이어져 있다'는 관계도 동치관계이고(길이 0인 길, 곧 제자리도 길로 칩니다), 그 동치류가 …

• 교란 변수

  … 가짜 연관을 만드는 제3의 변수를 교란 변수 라고 합니다. 오른쪽처럼 원인 관계를 화살표로 적은 방향그래프에서 X \leftarrow Z \rightarrow Y 라는 '뒷문 경로'가 열려 있으면, X가 Y에 …

• 무작위 대조 시험

  … 정확히 참 효과가 됩니다. 사람마다 효과가 다르다면 참 효과는 그 평균입니다. 원인 관계를 화살표로 그린그래프로 말하면, 동전이 '건강 → 치료'라는 화살표를 끊어 버립니다. 물론 동전도 운이 나쁘면 한쪽에 건강한 …

• 쌍곡기하

  … 모양과 잘 맞습니다. 나무도 단계마다 가지 수가 곱절로 늘어 지수적으로 커지기 때문입니다. 그래서 거대한그래프(인터넷, 사회 연결망)를 쌍곡평면에 그려, 몇 단계만 거치면 누구에게나 닿는 좁은 세상의 구조를 …

• 측지선

  … 가장 짧은 총 길이)로 잇는 길, 곧 최단 경로는 측지선의 이산판입니다. 곡면 대신 점과 선으로 된그래프위에서 가장 짧은 길을 찾는 일이라, 실제로 '측지 거리'라고도 부릅니다. 빛은 두 점 사이를 걸리는 …

• 오일러 경로

  … 보였습니다. 오일러가 점과 선을 그리지는 않았지만, 오늘날 말로 하면 땅을 점으로, 다리를 변으로 바꾼그래프의 문제입니다. 열쇠는 차수의 홀짝입니다. 길이 어떤 땅을 지나갈 때마다 들어오는 다리 하나와 나가는 다리 …

• 4색 정리

  … 나라를 꼭짓점으로, 이웃 관계를 변으로 바꾸면 지도는 변이 서로 엇갈리지 않게 평면에 그릴 수 있는그래프가 되고, 문제는 이웃한 꼭짓점이 다른 색이 되게 칠하는 것이 됩니다. 나라를 눌러 색을 바꿔 보세요. …

• 최단 경로

  지도 앱이 길을 찾을 때, 도로망은 교차로(꼭짓점)와 도로(변)로 된그래프이고 각 도로를 지나는 데 걸리는 시간이 변의 가중치입니다. 찾는 것은 가중치의 합이 가장 작은 길입니다. …

• 좁은 세상

  … 답했습니다. 원 위의 n = 100개 점을 양옆으로 가까운 이웃과 이어(한 점당 이웃 k개) 고리 모양의그래프를 만들고, 각 변을 확률 p로 끊어 무작위로 고른 다른 점에 다시 잇습니다. 그리고 두 가지를 잽니다. …

• 페이지랭크

  … 링크를 따라갈 확률 d를 감쇠 계수라고 부릅니다. 다음 위치가 지금 위치에만 달려 있으니 이것은 링크그래프위의 무작위 행보, 곧 마르코프 연쇄입니다. 오래 걸은 뒤 산책자가 각 페이지에 있을 확률이 그 …

• 최적 수송

  … 만든 분포는 표본이 늘수록 참 분포에 바서슈타인 거리로도 다가갑니다(큰 수의 법칙). 도시들을 잇는그래프위라면 칸 사이의 거리 대신 최단 경로의 길이가 비용이 되고, 문자열을 바꾸는 최소 비용인 ⟦편집 …

• 거리 함수

  … 해밍 거리, 단어의 편집 거리, 모든 점이 이어지고 모든 선이 양방향이며 선의 길이가 양수인그래프에서 최단 경로의 길이, 구면 위의 대원 거리(구면기하, 하버사인 공식), 푸앵카레 원판의 …

• 맨해튼 거리

  … 한 걸음이 둘 중 하나이므로). 그래서 수들이 비스듬히 누운 파스칼의 삼각형을 이룹니다. 도로망을그래프로 보면 맨해튼 거리는 그 그래프 위의 최단 경로 길이입니다. 한 점에서 택시 거리가 r = 인 점들을 …

• 체비쇼프 거리

  … 최단 경로의 수도 이때는 이항계수가 되어 파스칼의 삼각형이 판 위에 나타납니다. 판을 칸이 꼭짓점인그래프로 보면 두 거리 모두 최단 경로의 길이입니다. 평면에서 두 거리는 사실 같은 것을 45° 돌려 본 …

• 보로노이 다이어그램

  … 줄이려면 무게중심 대신 좌표별 중앙값으로 옮겨야 합니다. 이어지는 곳. 곧은 거리 대신 도로를 따라 재면그래프의 최단 경로 거리로 나눈 보로노이가 됩니다. 불이 났을 때 어느 소방서가 가장 빨리 닿는지 정하는 …

• 해밍 거리

  … 문자열끼리 모서리로 이어집니다. 해밍 거리는 모서리를 따라가는 최단 경로의 길이입니다. 이 정육면체는그래프이고, n비트라면 n차원 정육면체(초입방체)가 됩니다. 한 점에서 거리가 k인 문자열은 n자리 가운데 …

• 편집 거리

  … 치환, 분홍(−)은 삭제, 보라(+)는 삽입이고, 아래 두 줄은 그 순서대로 맞춘 정렬입니다. 표를그래프로 보면 더 분명합니다. 칸이 꼭짓점이고, 오른쪽 화살표는 삽입, 아래 화살표는 삭제, 대각선 화살표는 …

• P 대 NP 문제

  … 완전임을 보인 뒤로 수천 개가 더해졌습니다. 부분집합 합, 모든 꼭짓점을 한 번씩 지나는 해밀턴 경로,그래프를 세 가지 색으로 칠하기(평면 그래프로 좁혀도 NP 완전이라, 네 가지 색이면 언제나 된다는 ⟦4색 …

• 유한 오토마톤

  … 쓰고 오가는 튜링 기계보다 훨씬 약합니다. 그림으로는 상태가 꼭짓점이고 전이가 기호를 단 화살표인 방향그래프입니다. 자판기, 지하철 개찰구, 신호등 제어, 문서에서 낱말 찾기가 모두 이런 기계입니다. 노랗게 칠한 …

• 촘스키 위계

  … 옮기는 컴파일러는 이 위계를 그대로 씁니다. 소스 코드를 낱말로 자르는 단계는 정규 표현식, 낱말을그래프인 구문 트리로 묶는 단계는 문맥 자유 문법입니다. 층마다 '알아볼 수 있는가'뿐 아니라 '얼마나 빨리 …

• 문맥 자유 문법

  … 하나인 표준 모양으로 바꿔 둡니다). 편집 거리의 표와 같은 생각입니다. 구문 트리는 순환 없이 이어진그래프, 곧 그래프 이론에서 말하는 트리입니다. 한 기호에 규칙이 여럿일 수 있으니 문법은 기호를 기호열 …

• 정규 표현식

  … 상태를 하나씩 없애며 화살표에 식을 적어 나가면 됩니다. 오토마톤 그림은 꼭짓점이 상태, 변이 글자인 방향그래프이고, 받아들여지는 문자열은 시작에서 이중 원까지 가는 길입니다. 식을 기계로 바꾸면 처음에는 한 글자에 …

• 은닉 마르코프 모델

  … 확률에 −로그를 씌우면 곱이 합으로, 최대가 최소로 바뀌어, 이 계산은 날짜별 상태를 점으로 둔 격자그래프위의 최단 경로 찾기가 됩니다. 한 걸음씩 나아가는 계산은 거리표끼리 곱셈 대신 덧셈을, 덧셈 대신 …

• 비교 언어학

  … 가는 가지(노랑)이므로, 그 아래의 언어들은 모두 같은 대응을 물려받습니다. 이런 계통도는 순환이 없는그래프인 나무이고, 오늘날에는 기본 낱말 목록에서 동족어를 공유하는 비율(일종의 자카드 지수)이나 낱말 …

• 역전파

  … 방법이 역전파입니다. 아래는 입력 x 하나, 숨은 단위 둘, 출력 하나인 작은 신경망을 계산 순서대로 그린그래프(계산 그래프)입니다. 각 칸의 값은 왼쪽 칸들의 값만으로 정해집니다. z_j = w_j x + …

• 램지 이론

  … 사람 사이를 선으로 긋고, 아는 사이면 빨강, 모르는 사이면 파랑으로 칠해 봅시다. 여섯 점을 모두 이은그래프(완전 그래프 K_6 )의 변 15개를 어떻게 칠하든 세 변이 모두 같은 색인 삼각형이 생깁니다. . …

• 확률적 방법

  … 반드시 둘 다 (0보다 큰 확률로) 있습니다. 모두가 평균보다 클 수는 없으니까요. 점 개를 모두 이은그래프의 변마다 따로따로 동전을 던져 빨강이나 파랑으로 칠하면, 세 점이 이루는 삼각형 \binom n3 개 …

• 트리

  트리는 이어져 있으면서 순환(제자리로 돌아오는 고리)이 없는그래프입니다. 겉보기에 다른 여러 조건이 모두 같은 뜻이라는 점이 트리를 특별하게 만듭니다. 꼭짓점이 n개인 …

• 홀의 정리

  … 사람과 일을 두 줄의 꼭짓점으로, '받아들일 수 있다'를 변으로 그리면 변이 두 무리 사이에만 있는 이분그래프가 됩니다. 서로 겹치지 않는 변들의 모음이 매칭 이고, 모든 사람이 일을 얻는 매칭은 사람에서 일로 가는 …

• 최대 흐름 최소 절단 정리

  물탱크 s에서 마을 t로 관을 통해 물을 보냅니다. 이음매를 꼭짓점으로, 관을 방향 있는 변으로 그리면그래프가 되고, 관마다 1초에 흘릴 수 있는 양(용량)이 정해져 있습니다. 흐름은 두 규칙을 지켜야 합니다. …

• 위상수학

  … 전혀 쓰지 않았습니다. 어느 땅이 어느 땅과 몇 개의 다리로 이어져 있는지만 필요했습니다(오일러 경로,그래프). 오일러는 이것이 라이프니츠가 바랐던 '위치의 기하학'에 속하는 문제라고 적었습니다. 길이도 각도도 …

• 라틴 방진

  … 됩니다. 그래프로 보면 n × n 라틴 방진은 가로줄 n개와 세로줄 n개를 꼭짓점으로 하는 완전 이분그래프의 변을 n가지 색으로 칠하되, 한 꼭짓점에서 만나는 변끼리는 색이 겹치지 않게 칠한 것과 같습니다(r행 …

• 자동 미분

  … 각 연산의 미분만 알면 연쇄법칙으로 이어 붙여 도함수의 값을 냅니다. 쪼갠 모양이 아래의 계산그래프입니다. v_1 = \ln x_1,\quad v_2 = x_1x_2,\quad v_3 = \sin …

• 라플라시안과 그래프 라플라시안

  … 어떻게 돌려 잡아도 \Delta u 의 값은 같습니다. 방향에 치우침이 없는 연산입니다. 그래프의 경우.그래프에서는 변으로 이어진 꼭짓점이 이웃입니다. 이웃 수가 꼭짓점마다 달라서 보통 평균 대신 합을 쓰고 부호를 …

이 페이지가 가리키는 개념