한붓그리기 할 수 있는 조건은 무엇일까? (Eulerian circuit/path) / Graph Theory #3

graph theory

어린 시절 한붓그리기를 해본 경험이 있을 것이다. (없어도 상관 없다.) 하나의 “점”에서 “길”을 통해서 다른 “점”으로 이동한다. 전체적인 이동 경로를 살피었을 때 다음 두 가지 조건을 만족한다면 “한붓그리기가 성공했다.” 고 한다.

그래프 G가 bipartite면 G는 홀수 cycle을 가지지 않는다. (bipartite) / Graph Theory #2

graph theory

A graph is bipartite iff it has no odd cycle.

위의 정리를 이해하려면 bipartite graph가 무엇인지 알아야 한다. 정의는 다음과 같다.

A graph G is bipartite if V(G) is the union of two disjoint (possibly empty) independent sets.

정의가 한 번에 이해가 되지는 않는다. 자세히 풀어보면, 그래프 G의 vertices가 두 개의 disjoint independent sets의 합집합이라고 한다.

모든 닫힌 홀수 walk는 홀수 cycle을 포함한다. (walk, trail, path, cycle) / Graph Theory #1

graph theory

Every closed odd walk contains an odd cycle. (모든 닫힌 홀수 walk는 홀수 cycle을 포함한다.)

위의 정리를 이해하려면 walk와 path에 대해서 알아야 한다. Graph는 vertex와 edge로 이루어져 있다. 하나의 vertex에서 다른 vertex로 edge를 통해서 이동하는 상상을 쉽게 해볼 수 있을 것이다. 이처럼 edge를 통해서 vertex를 이동하는 ‘길’을 walk라고 한다.

Probability density function(PDF; 확률 밀도 함수)의 정의와 예시 / Random Process #4

random process

확률 질량 함수(probability mass function)은 이산 확률 변수를 기반으로 정의되었습니다. 확률 밀도 함수(probability density function; PDF)는 확률 질량 함수와 매우 유사하나, 연속 확률 변수(continuous random variable)를 기반으로 정의된다는 차이가 있습니다. 확률 질량 함수는 샘플에 접근하지 않고 실수에서 바로 확률을 구할 수 있도록 해준다는 것을 다뤘습니다. 확률 밀도 함수도 같은 역할을 합니다.

Probability mass function(PMF; 확률 질량 함수)의 정의와 예시 / Random Process #3

random process

확률 변수(random variable)는 값의 가능성에 따라서 이산 확률 변수와 연속 확률 변수로 나뉩니다. 어떤 사건이 발생할 확률을 구할 때 이산 확률 변수를 이용하여 쉽게 확률을 구하고 싶습니다. 확률을 빠르게 구하도록 도와주는 확률 질량 함수(probability mass function; PMF)에 대해서 알아봅시다.