한붓그리기: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
편집 요약 없음 |
잔글 로봇이 바꿈: eu:Eulertar grafo; 예쁘게 바꿈 |
||
4번째 줄: | 4번째 줄: | ||
그 중에서 같은 꼭짓점에서 시작해서 끝나는 오일러 경로를 '''오일러 회로'''(Euler circuit, Eulerian circuit)라고 한다. 오일러 회로를 지닌 무향그래프를 '''오일러 그래프'''라고 한다. 오일러는 그래프가 오일러 회로를 가질 필요충분조건은 |
그 중에서 같은 꼭짓점에서 시작해서 끝나는 오일러 경로를 '''오일러 회로'''(Euler circuit, Eulerian circuit)라고 한다. 오일러 회로를 지닌 무향그래프를 '''오일러 그래프'''라고 한다. 오일러는 그래프가 오일러 회로를 가질 필요충분조건은 |
||
*그 그래프가 연결된 그래프이고, |
* 그 그래프가 연결된 그래프이고, |
||
*모든 꼭짓점의 [[그래프 이론 용어사전|차수]]가 짝수이어야 한다 |
* 모든 꼭짓점의 [[그래프 이론 용어사전|차수]]가 짝수이어야 한다 |
||
는 것을 알아냈다. 오일러 회로가 아닌 오일러 경로(즉, 시작 꼭짓점과 끝 꼭짓점이 다른 경로)가 있을 필요충분조건은 |
는 것을 알아냈다. 오일러 회로가 아닌 오일러 경로(즉, 시작 꼭짓점과 끝 꼭짓점이 다른 경로)가 있을 필요충분조건은 |
||
*'정확히 두 개의 꼭지점만이 홀수의 차수를 가지고 |
* '정확히 두 개의 꼭지점만이 홀수의 차수를 가지고 |
||
*그 그래프가 연결되어 있다' |
* 그 그래프가 연결되어 있다' |
||
는 것이다. 이와 같은 조건은 [[그래프#정의|다중 그래프]]에서도 유효하다. |
는 것이다. 이와 같은 조건은 [[그래프#정의|다중 그래프]]에서도 유효하다. |
||
== 같이 보기 == |
== 같이 보기 == |
||
21번째 줄: | 21번째 줄: | ||
[[en:Eulerian path]] |
[[en:Eulerian path]] |
||
[[es:Ciclo euleriano]] |
[[es:Ciclo euleriano]] |
||
[[eu: |
[[eu:Eulertar grafo]] |
||
[[fa:دور اویلری]] |
[[fa:دور اویلری]] |
||
[[fi:Eulerin polku]] |
[[fi:Eulerin polku]] |
2010년 1월 27일 (수) 10:40 판
그래프 이론에서 오일러 경로(Euler path, Eulerian path)는 그래프의 모든 변을 단 한 번씩만 통과하는 경로를 뜻한다. 1736년 레온하르트 오일러가 쾨니히스베르크의 다리 문제를 푼 것에서 유래되었다. 흔히 한붓그리기 문제라고도 한다.
그 중에서 같은 꼭짓점에서 시작해서 끝나는 오일러 경로를 오일러 회로(Euler circuit, Eulerian circuit)라고 한다. 오일러 회로를 지닌 무향그래프를 오일러 그래프라고 한다. 오일러는 그래프가 오일러 회로를 가질 필요충분조건은
- 그 그래프가 연결된 그래프이고,
- 모든 꼭짓점의 차수가 짝수이어야 한다
는 것을 알아냈다. 오일러 회로가 아닌 오일러 경로(즉, 시작 꼭짓점과 끝 꼭짓점이 다른 경로)가 있을 필요충분조건은
- '정확히 두 개의 꼭지점만이 홀수의 차수를 가지고
- 그 그래프가 연결되어 있다'
는 것이다. 이와 같은 조건은 다중 그래프에서도 유효하다.
같이 보기
이 글은 수학에 관한 토막글입니다. 여러분의 지식으로 알차게 문서를 완성해 갑시다. |