[일반] 교수님이 perfect graph 예시들 2~3시수동안 설명해 주셨는데

[Windfor..(k920048)]

정작 Diestel 책 보니까 그런 내용이 전혀 없네요.

Comparability Graph, Interval Graph, Chordal Graph, etc, ...

이런 것들은 어디서 볼 수 있나요?

레퍼런스 봐도 없어서 여쭈어봅니다.

[익명(175.203)]

저게 perfect graph라는 증명은 정의로부터 자명한데

[Windforces(k920048)]

그것 말고도 몇가지 성질들을 더 알려주셨는데, 제가 중간에 강의 흐름을 놓쳐서 그렇습니다요 ㅠㅠ

[익명(175.203)]

일단 Weak/Strong perfect graph theorem이 있잖음? 근데 학교에서 perfect graph 관련 내용도 수업에서 커버하고 신기하네

[익명(175.203)]

Lovasz의 replacement theorem도 있고.. 이 세 정리 모두 Diestel에서 볼수 있는데.

[익명(175.203)]

예를 들어서 interval graph는 co-comparability graph의 subclass에 속하고 weak perfect graph theorem으로부터 comparability graph와 cocomparability graph의 perfectness는 동치니까 결국 저 리스트 중에서 comparability/chordal graph만 따지면됨

[익명(175.203)]

Chordal graph는 clique을 트리구조로 붙여나가는것이고 induced subgraph도 chordal이니까 leaf에 clique 붙여나가는 방식으로 induction 쓰면 chromatic number = clique number는 쉽게 보일수 있고,

[익명(175.203)]

Comparability graph는 poset에서 antichain으로 poset을 decompose하는 최소의 수 = poset 내 chain의 최대 길이니까 perfect이라는게 자명하지

[익명(175.203)]

실제로 co-comparability graph의 perfectness는 Dilworth theorem과 동치이고 Dilworth 정리는 윗 댓글의 정리보다 증명이 더 까다로운데, 윗 댓글에 weak perfect graph theorem을 적용하면 따름정리로 바로 딸려나오니 굉장히 유용하지.

[익명(175.203)]

정리 이름이 생각이 안났는데 윗윗 댓글의 정리는 Mirsky theorem. 근데 증명이 워낙 쉬워서 (한두줄) 그냥 이름 거론 안하는 경우가 많다..

[익명(175.203)]

그리고 perfect graph도 polyhedra의 조합적 최적화의 관점에서 생각해볼수 있는데, Schrijver의 combinatorial optimization 교재의 마지막권 뒷부분 챕터 (아마 chapter 70 후반대부터 hypergraph에 대한 이야기 나오는 부분부터) 에 아주 상세하게 나와있으니, 관심이 있으면 이 부분을 참고하도록 하고..

[익명(175.203)]

Perfect graph의 여러 example은 위키피디아나 인터넷 검색해도 꽤 나올거야. 그리고 Strong perfect graph theorem만으로 웬만한 characterization이 모두 가능함. 단점이라면 정리가 너무 강하고 직접 증명하기가 불가능하다는게 문제. (실제 증명이 100쪽 넘어가니까)

[익명(223.39)]

아니면 Matt Devos의 lecture note를 보는것도 괜찮음. 분량도 적고 정말 필요한 에센스만 담은 노트라서, 아마 self-contained 되어있을것임.
http://www.sfu.ca/~mdevos/notes/pack-cover/

[익명(223.39)]

그리고 임의의 길이 5 이상의 odd cycle이 2개 이상의 chord를 가지는 Meyniel graph도 perfect graph에 속함. 얘는 꽤 많은 다른 subclass들을 포함해서 (예를 들어서 본문의 chordal graph나 distance hereditary graph) 꽤 유용하고, 증명은 schrijver 교재에 있던걸로 기억함.

[익명(223.39)]

수업에서 perfect graph의 algorithmic한 관점에서 다룬다면 분명히 Lovasz theta function을 다룰텐데.. complement의 theta function이 clique number와 chromatic number 사이에 끼어있는데, perfect graph의 경우 세개가 모두 equal이 되고

[익명(223.39)]

다항시간 안에 theta function을 계산할수 있어서, 일반적인 그래프에서는 NP-hard로 알려진 chromatic number나 clique number를 구하는게 perfect graph에서는 polytime에 가능하게 되지.

[익명(223.39)]

관련된 classical한 교재로는 Golumbic의 algorithmic graph theory and perfect graphs라는 유명한 책이 있음. 최근에는 사람들이 perfect graph가 strong perfect graph theorem으로 완전히 characterize가 되었으니까,

[익명(223.39)]

Induced graph에 operation에 의해서 닫혀있는 어떤 그래프 class가 perfectness보다 완화된 조건 (e.g. chromatic number가 clique number에 대한 어떤 함수로 bounded되는가?) 을 만족하는지, 이런게 이 분야의 연구 줄기 중 하나가 되는것 같음.

[Windforces(k920048)]

헠 항상 좋은 답 주셔서 너무너무 감사드려요...복받으실 거에요 - dc App

[ㅅㄲㅁㅇ(as1392)]

175같은 인간이 고닉파고와야 파딱 넘기고 튀는데 ㅡㅡ 왜 유동이세요 흑흑