AI를 위한 필수 수학

401

Chapter 9 -

그래프 모델

원은 그래프의 간선 수

e

이며, 이 벡터 공간의 총 벡터 수는

2

e

이다. 여기서 그래프 이론이 스위칭 회로(켜짐

과 꺼지는 스위치), 디지털 시스템 및 신호에 어떻게 적용되는지 확인할 수 있다. 이 역시 모두 모듈로

2

의 필

드에서 작동하기 때문이다.

이처럼 간단한 대응관계와 선형 대수학 전체 분야에서의 지원을 바탕으로 절단점, 회로, 기본

회로, 스패닝 트리 및 기타 중요한 그래프 부분 구조들과 이들 사이의 관계를 벡터 부분 공간,

기저

basis

, 교차

intersection

, 직교성

orthogonality

및 이러한 부분 공간들의 차원의 맥락에서 이해하려는

것은 자연스러운 시도다.

9.14.5

실현 가능성

우리는 이미 그래프를 완전히 설명하는 행렬 표현으로 인접 행렬과 근접 행렬을 사용했다. 회

로 행렬

circuit

matrix

, 절단 집합 행렬

cut

set

matrix

, 경로 행렬

path

matrix

과 같은 행렬은 그래프의 또 다

른 중요한 특성들을 설명한다. 물론 관련 연구는 이 모든 것이 서로 어떻게 연관되고 상호 작용

하는지에 중점을 둔다.

또 다른 중요한 주제는 실현 가능성

realizability

이다. 주어진 행렬이 어떤 그래프의 회로 행렬이 되

기 위해 만족해야 하는 조건은 무엇일까?

9.14.6

컬러링과 매칭 ...