오일러 지표 (Euler Characteristic)

정의

오일러 지표 (Euler Characteristic) χ 는 다면체(polyhedron) 또는 CW 복합체의 위상적 불변량으로, χ = V - E + F 로 정의. V는 꼭짓점(vertex), E는 변(edge), F는 면(face)의 개수. 볼록 다면체에서는 항상 χ = 2 (오일러의 다면체 정리).

문제 상황과 동기

임의의 다면체가 주어졌을 때 V - E + F 를 계산하면 그 다면체가 어떤 위상적 성질을 가지는지 알 수 있음.

• Naive 접근: 단순히 V, E, F 를 세어 빼기.
• 핵심 통찰: χ 는 위상 불변량. 구면 위의 그래프는 χ=2, 원환면(torus)은 χ=0. 위상수학에서 genus g 와 χ = 2 - 2g.
• PS 위치: 평면 그래프 판별 (χ=2), 3D 기하 문제에서 다면체 종류 분류.

시각화

핵심 아이디어

볼록 다면체 (convex polyhedron):  V - E + F = 2
   정육면체: V=8, E=12, F=6 -> 8-12+6 = 2
   정사면체: V=4, E=6, F=4 -> 4-6+4 = 2

평면 그래프 (planar graph):     V - E + F = 1 + C (C = connected components)

원환면 (torus):                 V - E + F = 0

일반화:                         χ = V - E + F = 2 - 2g  (g = genus)

Invariant: 모든 convex polyhedron 은 구면과 위상 동형, 따라서 χ=2. 위상 변화 없이 edge 를 추가/제거해도 χ 불변.

알고리즘

euler_characteristic(vertices, edges, faces):
    return V - E + F

genus_from_chi(chi):
    return (2 - chi) / 2  # if chi is even

평면 그래프의 경우 outer face 를 포함한 F 사용.

구현

// Euler characteristic from V, E, F
#include <bits/stdc++.h>
using namespace std;
int main() {
  int V, E, F;
  cin >> V >> E >> F;
  int chi = V - E + F;
  cout << "chi = " << chi << "\n";
  if (chi == 2) cout << "Sphere / convex polyhedron\n";
  else if (chi == 0) cout << "Torus (genus 1)\n";
  else if (chi == -2) cout << "Double torus (genus 2)\n";
  else cout << "Genus g = " << (2 - chi) / 2 << "\n";
}

# Euler characteristic from planar graph input
# Input: N edges, each with two vertex IDs
# Output: V, E, F, chi
n = int(input())  # number of edges
vertex_set = set()
edges = []
for _ in range(n):
  u, v = map(int, input().split())
  vertex_set.add(u); vertex_set.add(v)
  edges.append((u, v))
V = len(vertex_set)
E = n
# For a connected planar graph: F = E - V + 2
# F includes the outer face
F = E - V + 2
chi = V - E + F
print(f"V={V}, E={E}, F={F}")
print(f"chi = {chi}")
if chi == 2: print("Planar graph (sphere)")
elif chi == 0: print("Torus")

import java.util.*;
import java.io.*;
public class Main {
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int E = Integer.parseInt(br.readLine());
      Set<Integer> vs = new HashSet<>();
      for (int i = 0; i < E; i++) {
          StringTokenizer st = new StringTokenizer(br.readLine());
          vs.add(Integer.parseInt(st.nextToken()));
          vs.add(Integer.parseInt(st.nextToken()));
      }
      int V = vs.size();
      int F = E - V + 2; // connected planar graph
      int chi = V - E + F;
      System.out.println("V=" + V + ", E=" + E + ", F=" + F);
      System.out.println("chi = " + chi);
      if (chi == 2) System.out.println("Planar (sphere)");
      else if (chi == 0) System.out.println("Torus");
  }
}

12
0 1
1 2
2 3
3 0
4 5
5 6
6 7
7 4
0 4
1 5
2 6
3 7

V=8, E=12, F=6
chi = 2
Sphere / convex polyhedron

6
0 1
1 2
2 0
0 3
1 3
2 3

V=4, E=6, F=4
chi = 2
Sphere / convex polyhedron

복잡도

변형 / 활용

• 평면 그래프 판별: V - E + F = 1 + C (연결 성분 C). planar embedding 존재 여부 체크.
• 3D 모델링: manifold mesh 의 위상 검증. χ=2 면 구면 위상.
• GIS: 지도에서 지역/경계/꼭짓점 관계 분석.
• Poincare 공식: 고차원 일반화 (alternating sum of Betti numbers).

표면 위상 분류

오일러 지표는 위상 불변량이므로 어떤 표면인지 바로 알 수 있다:

flowchart TD
    Chi["χ 계산"] --> C2{χ = 2}
    C2 -->|"Yes"| SP["구면 위상<br/>볼록 다면체, 평면 그래프"]
    C2 -->|"No"| C0{χ = 0}
    C0 -->|"Yes"| TR["원환면 위상\ngenus 1"]
    C0 -->|"No"| CN{χ < 0}
    CN -->|"Yes"| HG["고차 genus 곡면\ng = (2 - χ) / 2"]
    CN -->|"No"| ERR["연결 성분 분리\n또는 비다양체"]

오일러 공식 증명 스케치

볼록 다면체에서 V - E + F = 2 임을 귀납법으로:

1. 기저 사례: 사면체. V=4, E=6, F=4. 4 - 6 + 4 = 2.
2. 귀납: 다면체에서 임의의 edge 를 제거하면
   • 두 face 가 합쳐짐: F 가 1 감소, E 가 1 감소 → χ 불변.
   • 꼭짓점을 제거하면서 edge 도 같이 제거: 각 꼭짓점 제거 시 V, E 동시 감소 → χ 불변.
3. 최종적으로 사면체 (기저 사례) 로 환원. χ = 2.

이 증명의 핵심: edge/face 를 추가하거나 제거해도 χ 가 불변 임을 이용한다.

귀납 과정 예:
  정육면체 (V=8, E=12, F=6) → edge 1개 제거 (face 합침)
  → V=8, E=11, F=5 → χ = 8-11+5 = 2 (불변)

알고리즘 설계 응용

PS (Problem Solving) 에서 오일러 지표가 직접 쓰이는 상황:

1. 평면 그래프 판별: 주어진 그래프가 planar 인지 판단할 때, 조건 E ≤ 3V - 6 (F ≤ 2V - 4) 과 조합.
2. 그래프 genus 계산: 비평면 그래프의 embedding 에 필요한 최소 genus 추정.
3. 다면체 분류 문제: V, E, F 를 세어 χ 를 구한 뒤 표면 유형 판별.
4. Lattice / Grid 문제: 격자 위의 path/region 분석.

def planar_check(V, E):
    """단순 그래프에서 평면성 필요 조건 (충분 조건 아님)"""
    if V < 3:
        return True
    return E <= 3 * V - 6

def classify_surface(V, E, F):
    chi = V - E + F
    g = (2 - chi) // 2
    if chi == 2:
        return f"구면 (genus 0)"
    elif chi == 0:
        return f"원환면 (genus 1)"
    elif chi < 0 and (2 - chi) % 2 == 0:
        return f"genus {g} 곡면"
    else:
        return f"χ={chi}, 비방향성 또는 비다양체"

함정

1. F 에 outer face 포함

평면 그래프에서 F 는 outer (unbounded) face 를 포함한 모든 face 개수. 빼먹으면 χ 가 1 작아짐.

2. 연결성

공식 V - E + F = 2 는 connected graph 기준. disconnected 면 V - E + F = 1 + C.

3. Non-planar graph

K_5, K_3,3 같은 non-planar 그래프는 평면에 embedding 불가능해 Euler 공식이 성립하지 않음.

BOJ 연습 문제

참고

• 3D 기하
• 기하 기본
• 평면 그래프