한붓그리기: 두 판 사이의 차이

입체적으로 역사 찾아보기

← 이전 편집 다음 편집 →

내용 삭제됨 내용 추가됨

시각위키텍스트

인라인

2017년 4월 16일 (일) 13:53 판

그래프 이론에서, 한붓그리기 또는 오일러 트레일(영어: Eulerian trail)은 그래프의 모든 변을 단 한 번씩만 통과하는 트레일이다.

정의

(단순) 그래프 $G$ 위의 한붓그리기 또는 오일러 트레일은 그래프의 모든 변을 포함하는 트레일이다. (정의에 따라, 트레일은 변을 중복해서 거칠 수 없다.) 닫힌 한붓그리기는 시작점과 끝점이 같은 한붓그리기다. 일부 저자들은 닫힌 트레일을 회로(영어: circuit)라고 부르며, 이 경우 닫힌 한붓그리기는 오일러 회로(영어: Eulerian circuit)가 된다.

(단순) 유한 그래프 $G$ 에 대하여, 다음 두 조건이 서로 동치이다.

$G$ 는 닫힌 한붓그리기를 가진다.
$G$ 는 연결 그래프이며, $G$ 의 모든 꼭짓점의 차수는 짝수이다.

닫힌 한붓그리기를 갖는 그래프를 오일러 그래프(영어: Eulerian graph)라고 한다.

(단순) 유한 그래프 $G$ 에 대하여, 다음 두 조건이 서로 동치이다.

$G$ 는 한붓그리기를 가진다.
$G$ 는 연결 그래프이며, $G$ 의 홀수 차수 꼭짓점의 수는 0 또는 2이다.

만약 홀수 차수 꼭짓점이 2개 존재하는 경우, $G$ 의 한붓그리기는 이들 점들을 시작점·끝점으로 한다.

역사와 어원

1736년에 레온하르트 오일러가 쾨니히스베르크의 다리 문제를 풀기 위하여 도입하였다. 이는 그래프 이론의 시초로 여겨진다.

"한붓그리기"라는 이름은 그래프를 붓으로 종이 위에 그리는 것에 빗댄 것이다. 그래프를 한붓그리기를 따라 그리게 되면 붓을 종이에서 떼지 않고, 이미 그린 변을 덧칠할 필요 없이 그릴 수 있다.

바깥 고리

위키미디어 공용에 관련된
미디어 분류가 있습니다.

한붓그리기

(영어) Discussion of early mentions of Fleury's algorithm

같이 보기

해밀턴 경로

@@ 4번째 줄: / 4번째 줄: @@
 == 정의 ==
-(단순) 그래프 <math>G</math> 위의 '''한붓그리기''' 또는 '''오일러 트레일'''은 그래프의 모든 변을 포함하는 [[그래프 이론 용어사전|트레일]]이다. (정의에 따라, 트레일은 변을 중복해서 거칠 수 없다.) '''닫힌 한붓그리기'''은 시작점과 끝점이 같은 한붓그리기다. 일부 저자들은 닫힌 트레일을 '''회로'''({{llang|en|circuit}})라고 부르며, 이 경우 닫힌 한붓그리기는 '''오일러 회로'''({{llang|en|Eulerian circuit}})가 된다.
+(단순) 그래프 <math>G</math> 위의 '''한붓그리기''' 또는 '''오일러 트레일'''은 그래프의 모든 변을 포함하는 [[그래프 이론 용어사전|트레일]]이다. (정의에 따라, 트레일은 변을 중복해서 거칠 수 없다.) '''닫힌 한붓그리기'''는 시작점과 끝점이 같은 한붓그리기다. 일부 저자들은 닫힌 트레일을 '''회로'''({{llang|en|circuit}})라고 부르며, 이 경우 닫힌 한붓그리기는 '''오일러 회로'''({{llang|en|Eulerian circuit}})가 된다.
 (단순) 유한 [[그래프]] <math>G</math>에 대하여, 다음 두 조건이 서로 [[동치]]이다.