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 |