Vatslav Chvatal - Václav Chvátal

Vatslav Chvatal
Chvatal-kyoto2007-kostyum-head.png
Vatslav Chvatal (2007)
Tug'ilgan (1946-07-20) 1946 yil 20-iyul (74 yosh)
Praga
MillatiKanadalik, Chex
Olma materVaterloo universiteti
Charlz universiteti
MukofotlarBeale-Orchard-Hays mukofoti (2000) [1]
Docteur Honoris Causa, Université de la Mediterranné (2003)
Frederik V.Lancher mukofoti (2007) [2]
Jon fon Neyman nazariyasi mukofoti (2015) [3]
Ilmiy martaba
MaydonlarMatematika, Kompyuter fanlari, Operatsion tadqiqotlar
InstitutlarConcordia universiteti
Doktor doktoriKrispin Nesh-Uilyams
DoktorantlarDevid Avis (Stenford 1977)
Bryus Rid (McGill 1986)

Vatslav (Vashek) Chvatal (Chexiya: [ˈVaːtslaf ˈxvaːtal] Kompyuter fanlari va dasturiy ta'minot muhandisligi kafedrasi professori Concordia universiteti yilda Monreal, Kvebek, Kanada. Mavzular bo'yicha ko'p nashr etdi grafik nazariyasi, kombinatorika va kombinatorial optimallashtirish.

Biografiya

Chvatal tug'ilgan Praga 1946 yilda va matematikada tahsil olgan Charlz universiteti Pragada u Zdenek Hedrlinning nazorati ostida o'qigan.[4] U qochib ketdi Chexoslovakiya 1968 yilda, uch kundan keyin Sovet bosqini,[5] va doktorlik dissertatsiyasini tugatdi. matematikada Vaterloo universiteti, nazorati ostida Crispin St. J. A. Nash-Williams, 1970 yilning kuzida.[4][6] Keyinchalik, u pozitsiyalarni egalladi McGill universiteti (1971 va 1978-1986), Stenford universiteti (1972 va 1974-1977), Montreal universiteti (1972-1974 va 1977-1978), va Rutgers universiteti (1986-2004) uchun Monrealga qaytishdan oldin Kanada tadqiqotlari kafedrasi Kombinatorial optimallashtirishda [7][5]da Konkordiya (2004-2011) va Kanada tadqiqotlari kafedrasi Diskret matematikada (2011-2014) nafaqaga chiqqaniga qadar.

Tadqiqot

The Chvatal grafigi

Chvatal birinchi marta grafika nazariyasini 1964 yilda, kitob topib o'rgangan Klod Berge a Pilsen kitob do'koni [8] va uning ko'plab tadqiqotlari grafik nazariyasini o'z ichiga oladi:

  • Uning 19 yoshida birinchi matematik nashri haqida yo'naltirilgan grafikalar o'zlariga biron bir noan'anaviy narsalar bilan taqqoslana olmaydi gomomorfizm [9]
  • Chvatalning yana bir grafik-nazariy natijasi - bu 1970 yilda imkon qadar eng kichigi qurilishi uchburchaksiz grafik ikkalasi ham 4-xromatik va 4-muntazam, endi Chvatal grafigi.[4][10]
  • 1972 yilgi qog'oz [11] Hamilton davrlarini ulanish va maksimal mustaqil to'plam Chvatalga tegishli bo'lgan grafikaning kattaligi Erdo'ning raqami of 1. Xususan, agar mavjud bo'lsa s berilgan grafik shunday bo'ladi s-tepaga ulangan va yo'q (s + 1) -vertex mustaqil to'plami, grafil Gamiltonian bo'lishi kerak. Avis va boshq.[4] Chvatal va Erdős uzoq muddatli sayohat davomida ushbu natijani ishlab chiqdi va keyinchalik Luiza Gayga "barqaror haydashi uchun" minnatdorchilik bildirdi.
  • 1973 yilgi maqolada,[12] Chvatal tushunchasini taqdim etdi grafikning mustahkamligi, o'lchovi grafik aloqasi mavjudligi bilan chambarchas bog'liq Gamilton davrlari. Grafik t- agar har bir kishi uchun k 1dan katta, kamroqni olib tashlash tk tepaliklar kamroq qoldiradi k qolgan subgrafadagi ulangan komponentlar. Masalan, Gamilton tsikli bilan chizilgan grafikada, har qanday bo'sh bo'lmagan tepaliklar to'plamining olib tashlanishi, tsiklni olib tashlangan tepalar soniga qadar ko'p bo'laklarga ajratadi, shuning uchun hamilton grafikalari 1-qattiq. Chvatal 3/2 qattiq grafikalar, keyinroq esa 2 qattiq grafikalar har doim hamiltonlik deb taxmin qildi; keyingi tadqiqotchilar ushbu taxminlarga qarshi misollarni topgan bo'lishiga qaramay, grafilning qat'iyligiga bog'liq bo'lgan biron bir doimiylik Hamiltoniklikni kafolatlash uchun etarli bo'ladimi-yo'qmi hali ham ochiq.[13]

Chvatalning ba'zi asarlari to'plamlar oilasiga tegishli yoki ularga tenglashtirilgan gipergrafalar, allaqachon doktorlik dissertatsiyasida uchraydigan mavzu. u ham o'qigan tezis Ramsey nazariyasi.

  • 1972 yilda Erduss "ajablantiradigan" va "chiroyli" deb atagan gumonida,[14] va bu ochiq qoladi (Chvatal tomonidan echimi uchun taqdim etgan 10 dollarlik mukofot bilan) [15][16] u har qanday oilada to'plam operatsiyasi ostida yopilishini taklif qildi pastki to'plamlar, har ikkala to'plamning elementini tanlash va shu elementni o'z ichiga olgan barcha to'plamlarni saqlash orqali har doim juftlik bilan kesishadigan eng katta kichik oilani topish mumkin.
  • 1979 yilda,[17] u ning vaznli versiyasini o'rganib chiqdi qopqoq muammosi va isbotladi a ochko'zlik algoritmi yaxshilikni ta'minlaydi taxminlar tomonidan oldingi tortilmagan natijalarni umumlashtirib, optimal echimga Devid S. Jonson (J. Comp. Sys. Sci. 1974) va Laslo Lovásh (Diskret matematika. 1975).

Chvatal avvaliga qiziqib qoldi chiziqli dasturlash ning ta'siri orqali Jek Edmonds Chvatal Vaterlooda talaba bo'lganida.[4] U muhimligini tezda anglab etdi samolyotlarni kesish hisoblash kabi kombinatorial optimallashtirish muammolariga hujum qilish uchun maksimal mustaqil to'plamlar va, xususan, tekislikni isbotlash tushunchasini kiritdi.[18][19][20][21] 1970-yillarda Stenfordda u o'zining mashhur darsligini yozishni boshladi Lineer dasturlash1983 yilda nashr etilgan.[4]

Kesish samolyotlari markazida yotadi filial va kesilgan uchun samarali hal qiluvchilar tomonidan ishlatiladigan usul sotuvchi muammosi. 1988 yildan 2005 yilgacha Devid L. Applegeyt, Robert E. Biksi, Vashek Chvatal va Uilyam J. Kuk shunday hal qiluvchini ishlab chiqdi, Konkord.[22][23] Jamoa 2000 yilda o'zining o'n betlik maqolasi uchun hisoblash matematik dasturlashning mukammalligi uchun Beale-Orchard-Hays mukofotiga sazovor bo'ldi. [24] Konkordening 13509 shahar misolini hal qilishga olib kelgan filial va kesish usulidagi ba'zi bir aniqliklarini sanab o'tib, 2007 yilda o'z kitoblari uchun Frederik V. Lanchester mukofotiga sazovor bo'ldi, Sayohatchining sayohatchisi muammosi: hisoblash tadqiqotlari.

Chvatal shuningdek, buni isbotlash bilan mashhur badiiy galereya teoremasi,[25][26][27][28] o'zini ta'riflaydigan raqamli ketma-ketlikni o'rganish uchun,[29][30] bilan ishlash uchun Devid Sankoff ustida Chvatal - Sankoff konstantalari ning xatti-harakatlarini boshqarish eng uzoq tarqalgan keyingi muammo tasodifiy kirishlarda,[31] va uning ishi uchun Endre Szemeredi uchun qiyin holatlarda rezolyutsiya teoremasi.[32]

Kitoblar

  • Vashek Chvatal (1983). Lineer dasturlash. W.H. Freeman. ISBN  978-0-7167-1587-0.. Yaponiya tarjimasi Keigaku Shuppan tomonidan nashr etilgan, Tokio, 1986 y.
  • C. Berge va V. Chvatal (tahr.) (1984). Mukammal grafikalar bo'yicha mavzular. Elsevier. ISBN  978-0-444-86587-8.CS1 maint: qo'shimcha matn: mualliflar ro'yxati (havola)
  • Devid L. Applegate; Robert E. Biksi; Vashek Chvatal; Uilyam J. Kuk (2007). Sayohatchining sayohatchisi muammosi: hisoblash tadqiqotlari. Prinston universiteti matbuoti. ISBN  978-0-691-12993-8.
  • Vashek Chvatal (tahr.) (2011). Kombinatorial optimallashtirish: usullari va ilovalari. IOS Press. ISBN  978-1-60750-717-8.CS1 maint: qo'shimcha matn: mualliflar ro'yxati (havola)

Adabiyotlar

  1. ^ Beale-Orchard-Hays mukofotining o'tgan g'oliblari.
  2. ^ Frederik V. Lanchester mukofoti 2007 yil, olingan 2017-03-19.
  3. ^ Jon fon Neyman nazariyasi mukofoti 2015 yil, olingan 2017-03-19.
  4. ^ a b v d e f Avis, D.; Bondy, A .; Kuk, V.; Reed, B. (2007). "Vasek Chvatal: Qisqa kirish" (PDF). Grafika va kombinatorika. 23: 41–66. CiteSeerX  10.1.1.127.5910. doi:10.1007 / s00373-007-0721-4.
  5. ^ a b Vasek Chvatal - "sayohat qilayotgan professor", Concordia ning payshanba kuni hisoboti, 2005 yil 10 fevral.
  6. ^ Matematikaning nasabnomasi loyihasi - Vatslav Chvatal
  7. ^ Vasek Chvatal Kanada tadqiqotlari kafedrasini taqdirladi, Concordia ning payshanba kuni hisoboti, 2003 yil 23 oktyabr.
  8. ^ Chvatal, Vashek (1997), "Klod Berjeni maqtash uchun", Diskret matematika, 165-166: 3–9, doi:10.1016 / s0012-365x (96) 00156-2,
  9. ^ Chvatal, Vatslav (1965), "Cheklangan va hisoblanadigan qat'iy grafikalar va musobaqalar to'g'risida", Mathematicae Universitatis Carolinae sharhlari, 6: 429–438.
  10. ^ Vayshteyn, Erik V. "Chvatal Grafika". MathWorld.
  11. ^ V. Chvatal; P. Erdos (1972), "Gamilton davrlari to'g'risida eslatma" (PDF), Diskret matematika, 2 (2): 111–113, doi:10.1016 / 0012-365x (72) 90079-9,
  12. ^ Chvatal, V. (1973), "Qattiq grafikalar va gamilton sxemalari", Diskret matematika, 5 (3): 215–228, doi:10.1016 / 0012-365x (73) 90138-6,
  13. ^ Lesniak, Linda, Chvatalning t0- qattiq gumon (PDF)
  14. ^ Matematik sharhlar MR0369170
  15. ^ V. Chvatal; Devid A. Klarner; D.E. Knuth (1972), "Tanlangan kombinatoriya tadqiqot muammolari" (PDF), Stenford universiteti kompyuter fanlari bo'limi, Stan-CS-TR-72-292: Muammo 25
  16. ^ Chvatal, Vashek, Ekstremal kombinatorikadagi taxmin
  17. ^ "To'plamni qoplash muammosi uchun ochko'z evristik", Amaliyot tadqiqotlari matematikasi, 1979 y
  18. ^ Chvatal, Vatslav (1973), "Edmonds politoplari va zaif hamilton grafikalari", Matematik dasturlash, 5: 29–40, doi:10.1007 / BF01580109,
  19. ^ Chvatal, Vatslav (1973), "Edmonds politoplari va kombinatoriya muammolari iyerarxiyasi", Diskret matematika, 4 (4): 305–337, doi:10.1016 / 0012-365x (73) 90167-2,
  20. ^ Chvatal, Vatslav (1975), "Kombinatorikaning ba'zi chiziqli dasturlash jihatlari" (PDF), Kongress Numerantium, 13: 2–30,
  21. ^ Chvatal, V. (1975), "Grafikalar bilan bog'liq ba'zi bir politoplar to'g'risida", Kombinatoriya nazariyasi jurnali, B seriyasi, 18 (2): 138–154, doi:10.1016/0095-8956(75)90041-6.
  22. ^ Matematik muammo, uzoq hayajonlanish, sekin hosil. Nyu-York Tayms, 1991 yil 12 mart.
  23. ^ Badiiy marshrutlar, Science News Online, 2005 yil 1-yanvar.
  24. ^ Applegate, Devid; Biksi, Robert; Chvatal, Vashek; Kuk, Uilyam (1998), "Sayohat qiluvchi sotuvchi muammolarini hal qilish to'g'risida", Matematika hujjatlari, Qo'shimcha jild ICM III
  25. ^ Vayshteyn, Erik V. "Badiiy galereya teoremasi". MathWorld-dan - Wolfram veb-resursi. http://mathworld.wolfram.com/ArtGalleryTheorem.html
  26. ^ Diagonallar: I qism 4. Badiiy galereya muammolari, Jozef Malkevich tomonidan AMS Feature Column
  27. ^ Chvatalning badiiy galereya teoremasi yilda Aleksandr Bogomolniy Tugunni kesing
  28. ^ Ta'qib qilish, Numb3rs, 3-qism, 2-fasl
  29. ^ Chvatal, Vashek (1993), "Kolakoski ketma-ketligi to'g'risida eslatmalar", DIMACS texnik hisobotlari, TR: 93-84
  30. ^ Xavfli muammolar, Science News Online, 2002 yil 13-iyul.
  31. ^ Chvatal, Vatslav; Sankoff, Devid (1975), "Ikki tasodifiy ketma-ketlikning eng uzun umumiy ketma-ketliklari", Amaliy ehtimollar jurnali, 12 (2): 306–315, doi:10.2307/3212444, JSTOR  3212444.
  32. ^ Chvatal, Vashek; Szemeredi, Endre (1988), "Qaror uchun ko'plab qiyin misollar", ACM jurnali, 35 (4): 759–768, doi:10.1145/48014.48016.

Tashqi havolalar