๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
๐Ÿš— Major Study (Bachelor)/๐ŸŸข Discrete Mathematics

์˜ค์ผ๋Ÿฌ ํšŒ๋กœ (Euler's Path), ์˜ค์ผ๋Ÿฌ ์„œํ‚ท(Euler's Circuit)

by UKHYUN22 2021. 12. 7.
728x90

 

Introduction

"๋น„๋ฐ€์ด ๋ญ๋ƒ๋ฉด... ๋Œ€ํ•™์ƒํ™œ์ด ๋๋‚˜๋ฉด ๋ฐฉํ•™์ด ์—†์–ด์ ธ์š”...
๋ฌด์–ธ๊ฐ€๋ฅผ ํ•  ์ˆ˜ ์žˆ๋Š” ๋‚ด ์‹œ๊ฐ„์ด ์—†์–ด์ง„๋‹ค...
๋Œ€ํ•™์‹œ์ ˆ์˜ ๋ฐฉํ•™์€ '๊ธˆ'๊ณผ ๊ฐ™์€ ๊ฒƒ
ํ•˜์ง€๋งŒ ์‚ฌ๋žŒ์€ ๊ทธ๋ ‡๊ฒŒ ์•ˆํ•œ๋‹ค. ๋ถˆ์•ˆํ•˜๋‹ค. ๋ฌธ์ œ์—†์ง€๋งŒ ๋ถˆ์•ˆํ•˜๋‹ค.
๊ธธ๊ฒŒ ์‰ฐ๋‹ค๋Š” ๊ฒŒ ํž˜๋“ค๊ณ , ๋ถˆ๊ฐ€ํ”ผํ•˜๊ฒŒ ์‰ฌ๋Š” ๊ฒƒ์€ ํŽธํ•˜์ง€ ์•Š๋‹ค...
* ๋…ธ๋Š” ๊ฒƒ ๋ถ€ํ„ฐ ์ฑ„์›Œ๋ผ * 
11์ฃผ ์ •๋„์˜ ๋ฐฉํ•™๊ธฐ๊ฐ„. ๋ฐ˜์„ ๋†€์•„๋ผ ๋ถ€๋””
์ž๋ฐœ์ ์œผ๋กœ ํ•  ์ˆ˜ ์žˆ๋Š” ๊ฒƒ์„ ํ•˜๋ฉด์„œ ๋†€์•„๋ผ.
์ฆ‰, ๋†€์ง€ ๋ง๋ผ. ๋…ธ๋Š” ๋“ฏํ•˜์ง€๋งŒ ๋†€์ง€ ๋งˆ๋ผ"

 

 

HW4
ํญ๊ณผ ๋†’์ด๋ฅผ ๋จผ์ € ๊ตฌํ•ด์•ผ ๋œ๋‹ค.

Visual ํ•˜๊ธฐ ์ „์— Hasse Diagram์„ Excel ๋กœ ๊ทธ๋ ค๋ด๋ผ -> Coordination์— ๋Œ€ํ•œ ๊ฐ๊ฐ

Grid๋ฅผ ํ™•์žฅํ•˜๊ณ  Node๋ฅผ ๋ถ™์—ฌ๋„ฃ๋Š” ๋ฐฉ์‹

 

Graph

 

Isomorphism of Graph

iso == Equivalent, morphic == appearance

one to one correspondence and onto function.

์ผ๋Œ€์ผ ๋Œ€์‘ํ•˜๋Š” ํ•จ์ˆ˜๋ฅผ ์ผ์ปซ๋Š”๋‹ค. NOT Overlapped.

ํ˜„์‹ค ์„ธ๊ณ„์˜ ์นœ๊ตฌ๊ด€๊ณ„์™€ ์ธ์Šคํƒ€ ๊ณ„์ • ์ƒ์˜ ํŒ”๋กœ์šฐ ๊ด€๊ณ„์˜ ์ผ๋Œ€์‘ ๋Œ€์‘ํ•จ์„ ๋น„์œ ๋กœ..

 

2D์—์„œ ํ‘œํ˜„ํ•˜๋‹ค๋ณด๋ฉด Overlapped ๋˜๋Š” ๊ฒƒ ์ฒ˜๋Ÿผ ๋ณด์ด์ง€๋งŒ Rearrange ํ•˜๋ฉด Iso ํ•จ์ด ๋ณด์ผ ์ˆ˜ ์žˆ๋‹ค.

 

Isomorphism์„ ์ฐพ๊ธฐ ์œ„ํ•œ ๋ฐฉ๋ฒ•

One to one correspodence ํ•จ์„ ๋ณด์—ฌ์„œ Isomophism ํ•จ์„ ๋ณด์—ฌ์•ผ ํ•œ๋‹ค.

Graph์˜ ๋ชจ๋“  Node์˜ Degree๊ฐ€ ๋™์ผํ•˜๋‹ค๋ฉด Iso ํ•  ๊ฐ€๋Šฅ์„ฑ์ด ๋†’๊ณ , Graph Invariant๊ฐ€ ๊ทธ๊ฒƒ์„ ์ผ์ปซ๋Š”๋‹ค.

์ฆ‰ Graph์˜ ํŠน์ง•๋“ค์„ ๋งํ•œ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, degree of vertices, number of edges, degree sequence...

 

Invariant๊ฐ€ ์œ ์‚ฌํ•œ Graph๋ฅผ ์ฐพ๋Š” ๊ฒƒ ์ž์ฒด๋กœ ๊ต‰์žฅํฌ ์˜๋ฏธ์žˆ๋Š” ์ž‘์—…์ด๋‹ค. 

 

Same Invariant ์ธ ๊ฒฝ์šฐ

Number of edge์™€ Degree number of n ๋“ฑ๋“ฑ์ด ๊ฐ™์€ Invariant์˜ Graph๊ฐ€ ์žˆ๋‹ค๋ฉด ์–ด๋–ป๊ฒŒ ํ•ด์•ผ ํ•œ๋Š”๊ฐ€?

One to One correspondence function doman -> codomain ์— ๋Œ€ํ•œ ์ ์šฉ์„ ์ง„ํ–‰ํ•ด์•ผ ํ•œ๋‹ค.

degree number 2์™€ ์—ฐ๊ฒฐ๋˜๋Š” degree number 2๊ฐ€ ์—†๋‹ค.

ํ•˜์ง€๋งŒ H์˜ ๊ฒฝ์šฐ degree number 2 ์™€ ์—ฐ๊ฒฐ๋˜๋Š” degree number 2๊ฐ€ ์กด์žฌํ•œ๋‹ค.

์ฆ‰. ์ผ๋Œ€์ผ ๋Œ€์‘ํ•˜์ง€ ๋ชปํ•˜๋Š” ์„ฑ์งˆ์ด ์กด์žฌํ•œ๋‹ค. 

์ฆ‰, Invariant ๊ฐ„์˜ ๊ด€๊ณ„์„ฑ์— ๋Œ€ํ•œ ํŠน์ง•์„ Enumerationํ•˜๊ณ  Correspondence ํ•œ์ง€๋ฅผ ์‚ดํŽด๋ณด๋ฉด ๋œ๋‹ค.

 

 

Euler Path

Path ๋ž€?

The sequence of edges(vertices)๋ฅผ ๋งํ•œ๋‹ค.

Length of the Path ๋ž€?

The number of edge์ด๋‹ค. 

 

Attributes

๋™์ผํ•œ edge๋ฅผ ๋‘ ๋ฒˆ ์ด์ƒ ๊ฐ€์ง€๊ณ  ์žˆ์ง€ ์•Š์œผ๋ฉด graph is simple ์ด๋ผ๊ณ  ํ•œ๋‹ค.

๋ชจ๋“  Graph๋Š” Euler Circute ์ด ์žˆ๋Š” ๊ฒƒ์€ ์•„๋‹ˆ๋‹ค. Euler Path๋Š” ํ•œ๋ถ“๊ทธ๋ฆฌ๊ธฐ๊ฐ€ ๊ฐ€๋Šฅํ•œ ๊ฒƒ์ด๊ณ 

Euler Circuti์€ ํ•œ๋ถ“๊ทธ๋ฆฌ๊ธฐ๋กœ ์‹œ์ž‘ํ–ˆ๋˜ Node๋กœ ๋Œ์•„์™€์•ผ ํ•œ๋‹ค.

 

Euler Circuit

๊ฐ๊ฐ์˜ Vertice๊ฐ€ even degree๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ์–ด์•ผ ํ•œ๋‹ค๋Š” ๊ฒƒ์ด ํ•„์ˆ˜ ์กฐ๊ฑด์ด๋‹ค. 

Euler Circuit์ด์—ˆ๋˜ Graph์˜ ํ•œ edge๋ฅผ ์—†์•  ๋ฒ„๋ฆฌ๋ฉด ๊ทธ ๋‘ ๊ฐœ๋งŒ odd degreeํ•˜๊ฒŒ ๋œ๋‹ค.

์ฆ‰, Euler Path์ด๋ ค๋ฉด ๋‘ ๊ฐœ๋งŒ odd degree์—ฌ์•ผ ํ•œ๋‹ค.

 

๋ชจ๋“  vertex์˜ degree๊ฐ€ ์ง์ˆ˜์—ฌ์•ผ  Euler Ciruit์„ ๊ฐ€์งˆ ์ˆ˜ ์žˆ๋‹ค.

ํ•˜๋‚˜์˜ vertex์—์„œ ๋‚˜๊ฐ€๋Š” ๊ธธ ํ•˜๋‚˜์™€ ๋Œ๊ณ  ๋Œ์•„ ๋“ค์–ด์˜ค๋Š”(Income) edge ์ด๋ ‡๊ฒŒ ๋‘ ๊ฐœ๋Š” ํ•ญ์ƒ ์žˆ์–ด์•ผ ์ง์ด ๋œ๋‹ค. ๋‘ ๊ฐœ๊ฐ€ ์žˆ๋‹ค๋ฉด ํ•ด๋‹น vertex๋กœ ๋“ค์–ด์˜จ๋‹ค๋ฉด ํ•ญ์ƒ ๋‚˜๊ฐ€๋Š” ๊ธธ์€ ๋‹ค๋ฅธ ๋‚˜๋จธ์ง€ ํ•˜๋‚˜์˜ ๊ธธ๋กœ ๋‚˜๊ฐ€๊ฒŒ ๋œ๋‹ค๋Š” ๊ฒƒ์ด๋‹ค. 

Intermediate vertex๋„ ๋งˆ์ฐฌ๊ฐ€์ง€๋กœ ๋‘ ๊ฐœ๊ฐ€ ์กด์žฌํ•˜๊ณ  ๋™์ผํ•œ ์›์น™์œผ๋กœ ์ž‘๋™ํ•˜๊ฒŒ ๋œ๋‹ค.

 

Degree๊ฐ€ 2์ด์ƒ์ธ Vertice๊ฐ€ ์žˆ๋Š” Digraph์˜ ๊ฒฝ์šฐ

Path๊ฐ€ ๋ชจ์ž๋ผ๋Š” Graph๊ฐ€ ์กด์žฌํ•˜๋ฉด ํ•ด๋‹น Circuit์„ ๋–ผ์–ด๋‚ด๋ฉด Euler Circuit ํ•œ ๊ทธ๋ž˜ํ”„๋ฅผ ๋งŒ์กฑํ•  ์ˆ˜ ์žˆ๋‹ค.

๋–ผ์–ด๋‚ด๋Š” ๊ฒฝ์šฐ ์—ญ์‹œ ๋™์ผํ•˜๊ฒŒ Input ๊ณผ ouput ๋˜๋Š” edge๊ฐ€ ์—†์–ด์ง€๋Š” ๊ฒƒ์ด๊ธฐ ๋•Œ๋ฌธ์— ๋™์ผํ•˜๊ฒŒ ์œ ์ง€๋œ๋‹ค.

 

Ciruit์ž„์„ ๊ฐ๊ฐ ๋‚˜๋ˆ„์–ด์„œ ๋ฐํžˆ๊ณ  ๊ทธ๊ฒƒ์ด Connection ๋˜์–ด์žˆ๋‹ค๋ฉด ์ „์ฒด Graph๊ฐ€ Euler's Circuit์ด๋‹ค.

 

 

 

Hamilton Paths and Circuits

๋ชจ๋“  vertex๊ฐ€ ์ •ํ™•ํžˆ ํ•œ ๋ฒˆ ํ†ต๊ณผํ•ด์„œ ๋ชจ๋“  ๊ฒฝ๋กœ๊ฐ€ ๊ทธ๋ ค์ง€๋Š” ๊ฒƒ.

์ด๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ด ์—†๋‹ค. 

'๐Ÿš— Major Study (Bachelor) > ๐ŸŸข Discrete Mathematics' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

HW3 (Implementation with Recursive)  (0) 2022.01.02
Dijkstra's Algorithm  (0) 2021.12.10
Hall's Marriage Theorem, Isomorphism of Graph  (0) 2021.12.03
Discrete Mathematics  (0) 2021.11.02
Discrete Mathematics(HW2)  (0) 2021.10.24