[일반] 그래프 이론은 왜 다른 과목에 비해 귀납법을 증명에 많이 활용해요?

[Windfor..(k920048)]

제가 공부가 부족한 거일수도 있는데

다른 교과서에 비해 귀납법을 유독 많이 쓰는듯한 느낌을 받았어요.

왜 그럴까요?

[익명(223.62)]

Node가 countable해서?

[익명(125.138)]

꼭 조합론의 증명들이 algorithmic한 증명이 될 필요는 없지만, 그래프이론의 많은 정리들은 실제로 알고리즘에 원류를 두는 경우가 많아서 그렇습니다. 다른 분야의 수학은 infinite한 대상을 다루게 되는 경우가 많아서 수학적 귀납법만으로는 부족하고 선택공리 등이 개입될 여지가 있지만 조합론은 주로 유한한 대상을 다루니까 이러한 알고리즘에 원류를 두는건 자연스러운 부분이 있습니다.

[익명(125.138)]

이런 algorithmic한 증명법은 어떤 구조의 존재를 보일때 직접 구조를 만들어 보여주니 constructive하다는 장점이 있습니다.. 다른 분야에서 선택공리 등이 개입되는 경우에는 constructive하지 않으므로 이와는 크게 대비가 됩니다. 하지만 모든 조합적 증명법이 이처럼 constructive한건 아닙니다.. 예를 들어서 어떤 구조를 보일 때, 그 구조의 개수가 홀수개밖에 출현할수 없음을 보이거나, 아니면 개수가 0보다 커져야 한다는 증명을 한다면 구조의 존재를 증명할 수 있지만 직접적으로 구조를 만들어나가는 증명은 아니게 되죠.

[익명(125.138)]

그래프이론에서 constructive한 많은 증명들은 조합적 최적화에 기반을 두는 경우가 많고요. 실제로 많은 대상들이 duality 정리로 표현되곤 합니다. 예를 들어서 Menger의 정리는 Maxflow-Mincut의 관점에서 볼 수 있고, 최대유량 알고리즘과 관련이 깊죠. 이분그래프에서 Konig의 정리도 max matching과 min vertex cover의 크기가 같음을 보여주죠. Diestel 책에서 소개되는 Mader의 정리도 비슷한 맥락에서 볼 수 있고요.

[익명(125.138)]

결국 그래프에서 어떤 조합적 구조의 최댓값을 찾는 문제들은 특정 hypergraph의 packing/covering에 대한 duality문제로 변환되는 경우가 많은데, 이러한 linear programming 문제들은 fractional program에서 duality는 보장되어도 integer programming 관점에서 duality는 보장되지 않아서, 이는 Diestel 책과 같이 많은 그래프 이론 교재에서 다루는 것처럼 개별적인 주제로 다룰수밖에 없습니다. 요약하자면, 이런 'integer programming 문제의 효율적인 알고리즘을 찾으려는 시도'에서 출발한 경우가 많고, 결국 structural graph theory가 이러한 deterministic한 알고리즘과 관련이 깊은 이유가 됩니다.

[익명(125.138)]

하지만 counting/probabilistic/algebraic/topological한 논증에 기반한 non-constructive한 증명이 출현하는 경우도 생각보다 볼 수 있고요.. 관련 survey paper로는 좀 옛날거긴 한데 Alon의 survey가 있겠네요.
https://pdfs.semanticscholar.org/2662/3d9bf336beb6819d5cf72b968559daea571b.pdf

[Windforces(k920048)]

오우야....깊은 식견 감사드려요 - dc App

[dㅇ(110.70)]

댓글퀄보소