Václav Chvátal

Václav Chvátal
Václav Chvátal
Václav Chvátal (2020)
태어난 (1946-07-20) 1946년 7월 20일 (77세)
프라하
국적.캐나다어, 체코어
모교워털루 대학교
찰스 대학교
유명한슈발 그래프
차바탈-상코프 상수
본디-슈바탈 정리
교차수 부등식
그래프인성
상비일-오처드-헤이스상(2000)
박사 호노리스 카우사, 메디테라네 대학 (2003)
프레더릭 W. 랭체스터상 (2007)
존 폰 노이만 이론상(2015)
과학경력
필드수학, 컴퓨터 과학, 운영 연구
기관콩코르디아 대학교
박사지도교수크리스핀 내쉬윌리엄스
박사과정생데이비드 에이비스(스탠포드 1977)
브루스 리드 (McGill 1986)

Václav (Vašek) Chvátal ( 체코어:[ ˈva ːtslaf ˈxva ːtal]]는 캐나다 퀘벡주 몬트리올에 있는 콩코르디아 대학의 컴퓨터 과학 및 소프트웨어 공학과 명예 교수이며 프라하에 있는 찰스 대학의 초빙 교수입니다. 그는 그래프 이론, 조합론 및 조합 최적화의 주제에 대해 광범위하게 발표했습니다.

전기

1946년 프라하에서 태어나 카를 대학교에서 수학을 공부하였으며, 츠덴 ě크 헤들린의 지도 아래 수학하였다. 그는 소련의 침공 3일 후인 1968년 체코슬로바키아를 탈출하여 [5]워털루 대학교에서 크리스핀 세인트 J. A.의 지도 아래 수학 박사 학위를 마쳤습니다. 내쉬-윌리엄스, 1970년 가을.[4][6] 그 후 맥길 대학교(1971년, 1978년 ~ 1986년), 스탠포드 대학교(1972년 ~ 1974년 ~ 1977년), 몽레알 대학교(1972년 ~ 1974년), 그리고 Rutgers University(1986-2004)는 몬트리올로 돌아와 Concordia의 캐나다 조합 최적화 연구 의장(2004-2011)과 캐나다 이산수학 연구 의장(2011-2014)으로 은퇴할 때까지 재직했습니다.

조사.

슈발 그래프

1964년 클로드 베르제가 필센 서점에서 책을 발견하면서 그래프 이론을 처음 알게 되었고, 그의 연구의 대부분은 그래프 이론과 관련이 있습니다.

  • 19세의 나이에 그의 첫 수학적 출판물은 어떤 사소한 그래프[9] 동형화에 의해서도 자기 자신에게 지도화될 수 없는 지시 그래프에 관한 것이었습니다.
  • 차발의 또 다른 그래프 이론적 결과는 1970년에 가능한 가장 작은 삼각형이 없는 그래프(현재 차발 그래프로 알려진 4색과 4정칙 그래프)를 구축한 것입니다.[4][10]
  • 1972년 해밀턴 사이클을 그래프의 연결성과 최대 독립 집합 크기와 관련시킨 논문에서 Chvátal의 Erd ő 수를 1로 얻었습니다. 구체적으로, 주어진 그래프가 s-정점으로 연결되어 있고 (s + 1)-정점 독립 집합이 없는 경우, 그래프는 해밀턴이어야 합니다. Avis et al. 는 Chvátal과 Erd ő가 긴 도로 여행 동안 이 결과를 도출하고 나중에 Louise Guy에게 "꾸준한 운전"에 감사하는 이야기를 들려줍니다.
  • 1973년 논문에서 [12]Chvátal은 해밀턴 사이클의 존재와 밀접하게 연결되는 그래프 연결성의 척도인 그래프 인성의 개념을 소개했습니다. 그래프는 1보다 큰 k개에 대해 tk개보다 작은 정점을 제거하면 나머지 부분 그래프에 연결된 k개보다 적은 성분이 남게 됩니다. 예를 들어, 해밀턴 사이클이 있는 그래프에서 비어 있지 않은 정점 집합을 제거하면 제거된 정점의 수만큼 사이클을 분할하므로 해밀턴 그래프는 1-터프입니다. Chvátal은 3/2-tough 그래프와 나중에 2-tough 그래프는 항상 해밀턴식이라고 추측했습니다. 이후 연구자들이 이러한 추측에 대한 반례를 찾았지만 그래프 인성에 대한 일정한 경계가 해밀턴성을 보장하기에 충분한지 여부는 여전히 열려 있습니다.[13]

Chvátal의 연구 중 일부는 그의 박사 논문에서 이미 발생하고 있는 주제인 집합 또는 이에 상응하는 하이퍼그래프에 관한 것으로, 그는 또한 램지 이론을 연구했습니다.

  • 1972년 에르트 ő스가 "놀랍고" "아름답다"고 불렀다는 추측에서, 그는 (그 해에 대해 차바탈이 제시한 10달러의 상금과 함께) 부분집합을 취하는 연산에 의해 닫힌 어떤 집합군에서도, 가장 큰 쌍대 intersect 아과는 집합 중 하나의 원소를 선택하고 그 원소를 포함하는 모든 집합을 유지함으로써 항상 찾을 수 있습니다.
  • 1979년,[17] 그는 세트 커버 문제의 가중 버전을 연구했고, 욕심 많은 알고리즘이 최적 해법에 좋은 근사치를 제공한다는 것을 증명했고, 데이비드 S. 존슨(J. Comp)에 의해 이전의 가중되지 않은 결과를 일반화했습니다. Sys. Sci. 1974)와 László Lovász (Discrete Math. 1975).

차바탈은 워털루에 재학 중이던 시절 잭 에드먼즈의 영향을 받아 처음으로 선형 프로그래밍에 관심을 갖게 되었습니다.[4] 그는 최대 독립 집합 계산과 같은 조합 최적화 문제를 공격하기 위한 절단면의 중요성을 빠르게 인식하고 특히 절단면 증명의 개념을 도입했습니다.[18][19][20][21] 1970년대에 스탠포드 대학교에서 그는 1983년에 출판된 그의 인기 있는 교과서인 선형 프로그래밍을 쓰기 시작했습니다.[4]

절단면은 분기점의 중심에 놓여 있으며, 효율적인 해결사가 여행하는 세일즈맨 문제를 위해 사용하는 절단 방법입니다. 1988년에서 2005년 사이에 데이비드 L. 애플게이트, 로버트 E. 빅스비, 바젝 차바탈, 윌리엄 J. 쿡의 연구팀은 이러한 해결책인 콩코드를 개발했습니다.[22][23] 이 팀은 콩코드가 13,509개 도시의 사례를 해결하는 데 도움이 된 분기와 절단 방법의 개선점을 열거한 10페이지의 논문으로 2000년에 Beale-Orchard-Hays 전산수학 프로그래밍 부문 우수상을 수상했으며, 2007년에는 이 책으로 Frederick W. Lancester Prize를 수상했습니다. 출장 세일즈맨 문제: 컴퓨터를 이용한 연구.

Chvátal is also known for proving the art gallery theorem,[25][26][27][28] for researching a self-describing digital sequence,[29][30] for his work with David Sankoff on the Chvátal–Sankoff constants controlling the behavior of the longest common subsequence problem on random inputs,[31] and for his work with Endre Szemerédi on hard instances for resolution theorem proving.[32]

책들

  • Vašek Chvátal (1983). Linear Programming. W.H. Freeman. ISBN 978-0-7167-1587-0..게이가쿠 슈판 펴냄, Vašek Chvátal (1983). Linear Programming. W.H. Freeman. ISBN 978-0-7167-1587-0.도쿄, 1986.
  • C. Berge and V. Chvátal (eds.) (1984). Topics on Perfect Graphs. Elsevier. ISBN 978-0-444-86587-8. {{cite book}}: author= 일반 이름(도움말)이 있습니다.
  • David L. Applegate; Robert E. Bixby; Vašek Chvátal; William J. Cook (2007). The Traveling Salesman Problem: A Computational Study. Princeton University Press. ISBN 978-0-691-12993-8.[33]
  • Vašek Chvátal, ed. (2011). Combinatorial Optimization: Methods and Applications. IOS Press. ISBN 978-1-60750-717-8.
  • Vašek Chvátal (2021). Discrete Mathematical Charms of Paul Erdős. A Simple Introduction. Cambridge University Press. ISBN 978-1-108-92740-6.

참고 항목

참고문헌

  1. ^ 비일-오르카르트-헤이스상의 과거 수상자들.
  2. ^ 프레더릭 W. 랜체스터 상 2007, 2017-03-19 회수.
  3. ^ 존 폰 노이만 이론상 2015, 회수 2017-03-19.
  4. ^ a b c d e f Avis, D.; Bondy, A.; Cook, W.; Reed, B. (2007). "Vasek Chvatal: A Short Introduction" (PDF). Graphs and Combinatorics. 23: 41–66. CiteSeerX 10.1.1.127.5910. doi:10.1007/s00373-007-0721-4. S2CID 11121944.
  5. ^ a b 바섹 차바탈은 2005년 2월 10일자 콩코르디아의 목요일 보고서인 '여행하는 교수'입니다.
  6. ^ 수학 계보 프로젝트 – 바클라브 차바탈
  7. ^ 바섹 차바탈은 2003년 10월 23일, Concordia의 목요일 보고서인 캐나다 연구 위원장을 수상했습니다.
  8. ^ Chvátal, Vašek (1997), "In praise of Claude Berge", Discrete Mathematics, 165–166: 3–9, doi:10.1016/s0012-365x(96)00156-2,
  9. ^ Chvátal, Václav (1965), "On finite and countable rigid graphs and tournaments", Commentationes Mathematicae Universitatis Carolinae, 6: 429–438.
  10. ^ Weisstein, Eric W. "Chvátal Graph". MathWorld.
  11. ^ V. Chvátal; P. Erdős (1972), "A note on Hamiltonian circuits" (PDF), Discrete Mathematics, 2 (2): 111–113, doi:10.1016/0012-365x(72)90079-9,
  12. ^ Chvátal, V. (1973), "Tough graphs and hamiltonian circuits", Discrete Mathematics, 5 (3): 215–228, doi:10.1016/0012-365x(73)90138-6,
  13. ^ Lesniak, Linda, Chvátal's t0-tough conjecture (PDF)
  14. ^ 수학평 MR0369170
  15. ^ V. Chvátal; David A. Klarner; D.E. Knuth (1972), "Selected combinatorial research problems" (PDF), Computer Science Department, Stanford University, Stan-CS-TR-72-292V. Chvátal; David A. Klarner; D.E. Knuth (1972), "Selected combinatorial research problems" (PDF), Computer Science Department, Stanford University, Stan-CS-TR-72-292문제 25
  16. ^ Chvátal, Vašek, A conjecture in extremal combinatorics
  17. ^ "집합 커버링 문제에 대한 탐욕스러운 휴리스틱", 운영 수학 연구, 1979
  18. ^ Chvátal, Václav (1973), "Edmonds polytopes and weakly hamiltonian graphs", Mathematical Programming, 5: 29–40, doi:10.1007/BF01580109, S2CID 8140217,
  19. ^ Chvátal, Václav (1973), "Edmonds polytopes and a hierarchy of combinatorial problems", Discrete Mathematics, 4 (4): 305–337, doi:10.1016/0012-365x(73)90167-2,
  20. ^ Chvátal, Václav (1975), "Some linear programming aspects of combinatorics" (PDF), Congressus Numerantium, 13: 2–30,
  21. ^ Chvátal, V. (1975), "On certain polytopes associated with graphs", Journal of Combinatorial Theory, Series B, 18 (2): 138–154, doi:10.1016/0095-8956(75)90041-6.
  22. ^ 수학 문제, 긴 당황, 천천히 산출합니다. 뉴욕 타임즈, 1991년 3월 12일자
  23. ^ Artful Routes, Science News Online, 2005년 1월 1일
  24. ^ Applegate, David; Bixby, Robert; Chvátal, Vašek; Cook, William (1998), "On the Solution of Traveling Salesman Problems", Documenta Mathematica, Extra Volume ICM III
  25. ^ 바이스타인, 에릭 W "미술관 정리" From MathWorld--Wolfram Web Resource. http://mathworld.wolfram.com/ArtGalleryTheorem.html
  26. ^ 대각선: 파트 I 4. 미술관 문제, 조지프 말케비치의 AMS 특징 칼럼
  27. ^ Alexander Bogomolny의 Cut the Knot에 나타난 Chvatal의 미술관 정리
  28. ^ 집착, Number3rs, 에피소드3, 시즌2
  29. ^ Chvátal, Vašek (1993), "Notes on the Kolakoski Sequence", DIMACS Technical Reports, TR: 93-84
  30. ^ 위험한 문제들, 과학 뉴스 온라인, 2002년 7월 13일
  31. ^ Chvátal, Václav; Sankoff, David (1975), "Longest common subsequences of two random sequences", Journal of Applied Probability, 12 (2): 306–315, doi:10.2307/3212444, JSTOR 3212444, S2CID 250345191.
  32. ^ Chvátal, Vašek; Szemerédi, Endre (1988), "Many hard examples for resolution", Journal of the ACM, 35 (4): 759–768, doi:10.1145/48014.48016, S2CID 2526816.
  33. ^ Borchers, Brian (March 25, 2007). "Review of The Traveling Salesman Problem: A Computational Study". MAA Reviews, Mathematical Association of America.

외부 링크