AI를 위한 필수 수학

400

AI

를 위한 필수 수학

9.14.3

평면성

그래프의 기하학적 표현이 평면적인가 입체적인가? 즉, 그래프의 꼭짓점을 그리고 그 엣지가

서로 교차하지 않고 하나의 평면에 모두 연결할 수 있는가의 문제다. 이는 복잡한 시스템의 자

동 배선, 인쇄 회로, 대규모 집적 회로와 같은 애플리케이션에서 고려되는 주제다. 비평면 그래

프

nonplanar

graph

의 경우 그래프 두께와 엣지 사이의 교차 횟수와 같은 속성에 관심이 있다. 평면

그래프에 대한 동등한 조건은 이중 그래프의 존재인데, 그래프의 벡터 공간 측면에서 그래프와

이중 그래프 사이의 관계가 명확해지는 것이다. 여기서 선형 대수와 그래프가 결합하여 대수적

표현과 조합적 표현이 기하학적 도형에 관한 질문에 답하고 그 반대의 경우도 마찬가지다. 평

면성 문제에서 우리는 꼭짓점 (노드 )이 세 개 이상의 차수를 가진 단순하고 분리되지 않은 그래

프만 고려해야 한다. 또한 엣지의 수가 꼭짓점의 수를 세 배해서

6

을 뺀 것보다 큰 그래프는 비

평면 그래프다. 이 분야에서는 아직 해결되지 않은 문제가 많이 있다.

9.14.4

벡터 공간으로서의 그래프

그래프를 기하학적 객체이자 대수적 객체로 이해하고 두 표현 사이의 대응관계로 파악하는 것

이 중요하다. 그래프의 경우 특히 더 중요하다. 모든 그래프는 그래프의 엣지의 ...