오일러 지표 (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).

함정

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 기하
• 기하 기본
• 평면 그래프