기본사항

그래프란?

쾨히스베르크 다리건너기 문제

🔗나무위키: 쾨니히스베르크 다리 건너기 문제

한 붓 그리기, 오일러 경로

https://namu.wiki/w/쾨니히스베르크 다리 건너기 문제

쾨니히스베르크시의 한 가운데는 프레겔 강[1]이 흐르고 있고 여기에는 가운데 섬들과 연결되어있는 일곱 개의 다리가 있다. 그 다리들을 한 번씩만 차례로 모두 건널 수 있겠는가?

주요 용어

https://gamedevlog.tistory.com/15

𝑮 = (𝑽, 𝑬)

𝑽 = {𝒗|𝒗는 꼭지점(vertex)}

𝑬 = {𝒆|𝒆는 변(edge})

• 변은 두 꼭지점을 연결함**. (변에 의해 발생(incident)되었다.)**
• 연결된 두 꼭지점은 서로 인접**(adjacent)**한다고 함
• 병렬 변**(parallel edge) :** 두 꼭지점을 연결하는 변이 복수개 있을 때
• 루프**(loop) :** 동일한 꼭지점을 연결하는 변
• 고립된 꼭지점**(isolated vertex) :** 어떠한 변도 연결되지 않은 꼭지점

병렬변과 루프

동형(isomorphic)