AI를 위한 필수 수학

402

AI

를 위한 필수 수학

분야가 있다. 이는 결국 최대 유량 최소 절단

max

-

flow

min

-

cut

문제가 된다. 우리는 랜덤 워크 기반

의 알고리즘을 사용해 대규모 이분 그래프에서 완벽한 매칭을 찾을 수 있다.

9.14.7

열거

1857

년 클레이는 포화 탄화수소

C

n

H

2n

+

2

의 이성질체 수를 세는 데 관심이 있었고, 이를 통해

n

개의 노드를 가진 다양한 트리의 수를 세어 그래프 이론에 기여했다. 열거할 수 있는 그래프

의 종류는 매우 다양하며 그 많은 그래프가 연구 논문의 주제가 되기도 했다. 예를 들어 모든

루트 트리

rooted

tree

, 단순 그래프

simple

graph

, 단순 다이그래프

simple

digraph

, 특정 속성을 가진 기타

그래프를 열거하는 것 등이 있다. 열거는 그래프 이론에서 매우 중요하고 방대한 분야다. 다양

한 열거 기법 중 가장 중요한 하나는 포여의 계수 정리

Pólya

’

s

counting

theorem

로, 적절한 순열 그룹을

찾은 다음 그 순환 지표

cycle

index

를 구해야 하는데 이는 그리 간단하지 않다.

9.15

그래프 알고리즘과 연산 측면

그래프 모델링을 다루는 모든 사람에게 알고리즘과 컴퓨터 구현은 엄청난 가치가 있다. 전통적

으로 다음과 같이 그래프 과제를 위한 알고리즘들이 있다.

●

그래프가 분리 가능

separable

한지 알아본다.

●

그래프가 연결되어 있는지 확인한다.

●

그래프의 구성 요소를 찾는다.

●

그래프의 스패닝 트리

spanning

tree

를 구한다.

●

기본 회로 집합을 구한다. ...