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

입체적으로 역사 찾아보기

← 이전 편집 다음 편집 →

내용 삭제됨 내용 추가됨

시각위키텍스트

인라인

2014년 12월 12일 (금) 08:27 판

그래프 이론에서, 오일러 트레일(영어: 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

같이 보기

해밀턴 경로

@@ 1번째 줄: / 1번째 줄: @@
 [[파일:Königsberg_graph.svg|thumb|165px|쾨니히스베르크의 다리 그래프. 이 그래프는 오일러 트레일을 갖지 않는다.]]
-[[그래프 이론]]에서, '''오일러 경로'''({{llang|en|Eulerian path}}) 또는 '''한붓그리기'''는 [[그래프 이론]]에서 [[그래프]]의 모든 [[그래프 이론 용어사전#용어|변]]을 단 한 번씩만 통과하는 [[그래프 이론 용어사전|트레일]]이다.
+[[그래프 이론]]에서, '''오일러 트레일'''({{llang|en|Eulerian trail}}) 또는 '''한붓그리기'''는 [[그래프 이론]]에서 [[그래프]]의 모든 [[그래프 이론 용어사전#용어|변]]을 단 한 번씩만 통과하는 [[그래프 이론 용어사전|트레일]]이다.
 == 정의 ==
@@ 24번째 줄: / 24번째 줄: @@
 {{Commons category|Eulerian paths}}
 * {{언어고리|en}} [http://mathforum.org/kb/message.jspa?messageID=3648262&tstart=135 Discussion of early mentions of Fleury's algorithm]
+== 같이 보기 ==
+* [[해밀턴 경로]]
 [[분류:그래프 이론]]