เดเนช เคอนิก: ผู้เขียนตำราทฤษฎีกราฟเล่มแรกของโลก

หากถามว่าทฤษฎีกราฟกลายเป็นสาขาคณิตศาสตร์ของตนเองเมื่อใด คำตอบที่นักประวัติศาสตร์มักให้คือปี ค.ศ. 1936 เมื่อมีหนังสือเล่มหนึ่งรวบรวมความรู้ที่กระจัดกระจายเข้าด้วยกันเป็นครั้งแรก ผู้เขียนคือ เดเนช เคอนิก (Dénes Kőnig) นักคณิตศาสตร์ชาวฮังการี ผู้เสียชีวิตเมื่อวันที่ 19 ตุลาคม ค.ศ. 1944 ที่กรุงบูดาเปสต์ ด้วยวัย 60 ปี ในเดือนที่ฮังการีถูกพรรคแอร์โรว์ครอสเข้ายึดอำนาจและการกวาดล้างชาวยิวทวีความรุนแรง

ชีวิตช่วงต้นในครอบครัวนักคณิตศาสตร์

เคอนิกเกิดเมื่อวันที่ 21 กันยายน ค.ศ. 1884 ที่บูดาเปสต์ เป็นบุตรของยูลา เคอนิก (Gyula Kőnig) นักคณิตศาสตร์ชื่อดังที่มีชื่อเสียงจากผลงานด้านทฤษฎีเซต เขาได้รับการศึกษาที่ดีที่โรงเรียนมัธยมชั้นนำของเมือง ศึกษาต่อที่บูดาเปสต์และที่เกิททิงเงินในช่วงปี ค.ศ. 1902-1904 และรับปริญญาเอกในปี ค.ศ. 1907 โดยมียอเชฟ เคือร์ชัค (József Kürschák) และแฮร์มันน์ มินคอฟสกี (Hermann Minkowski) เป็นอาจารย์ที่ปรึกษา

ตั้งแต่ปี ค.ศ. 1908 เขาทำงานที่มหาวิทยาลัยเทคนิคแห่งบูดาเปสต์ ไต่ระดับจากผู้ช่วยสอน เป็นผู้ช่วยอาวุโสในปี ค.ศ. 1910 และเป็นอาจารย์พิเศษ (Privatdozent) ในปี ค.ศ. 1911 โดยสอนวิชานอโมกราฟี ทอพอโลยี ทฤษฎีเซต ฟังก์ชันของจำนวนจริง และทฤษฎีกราฟ เขาได้เป็นศาสตราจารย์เต็มตัวในปี ค.ศ. 1935 และอยู่ที่นี่ตลอดชีวิต ในช่วงต้นอาชีพ เขายังเขียนหนังสือในปี ค.ศ. 1918 และ 1920 ซึ่งนักคณิตศาสตร์ฮังการีหลายคนเรียนรู้ทอพอโลยีของพื้นผิวมาจากหนังสือเล่มนั้น

ก้าวแรกของทฤษฎีกราฟ

เคอนิกมองเห็นพลังของแนวคิดกราฟมาก่อนใคร เขาเห็นว่าการแปลงปัญหาให้เป็นภาพของจุดและเส้นเชื่อมช่วยให้มองเห็นโครงสร้างและแก้ปัญหาได้ง่ายขึ้น และบ่อยครั้งเขาก็แปลผลลัพธ์ทางทฤษฎีเซตของเขาเป็นภาษากราฟ เขายังสนใจปริศนาคณิตศาสตร์เชิงสันทนาการ ซึ่งมีบทบาทในการปูทางสู่ทฤษฎีกราฟด้วยเช่นกัน

ในปี ค.ศ. 1936 เขาตีพิมพ์ “Theorie der endlichen und unendlichen Graphen” (ทฤษฎีของกราฟจำกัดและอนันต์) ที่เมืองไลพ์ซิก ซึ่งได้รับการยกย่องว่าเป็น ตำราทฤษฎีกราฟเล่มแรกของโลก และเป็นเครื่องหมายแห่งการเริ่มต้นของทฤษฎีกราฟในฐานะสาขาคณิตศาสตร์ที่เป็นอิสระ (ก่อนหน้านั้น ชื่อ “ทฤษฎีกราฟ” ยังไม่ปรากฏในแคตตาล็อกวิชาของมหาวิทยาลัยด้วยซ้ำ จนกระทั่งปี ค.ศ. 1927) หนังสือเล่มนี้ถูกพิมพ์ซ้ำโดยสำนักพิมพ์เชลซีในปี ค.ศ. 1950 และยังเป็นหนังสือที่ถูกอ้างถึงบ่อยแม้จะมีตำราใหม่ออกมามากมาย ภายหลังฉบับแปลภาษาอังกฤษก็ตีพิมพ์ในปี ค.ศ. 1990

ทฤษฎีบทและเลมมาของเคอนิก

ชื่อของเคอนิกปรากฏในผลลัพธ์พื้นฐานหลายอย่าง

ทฤษฎีบทของเคอนิกในทฤษฎีกราฟ (Kőnig’s theorem) กล่าวว่าในกราฟสองส่วน (bipartite graph) จำนวนเส้นเชื่อมมากที่สุดที่ไม่ใช้จุดยอดร่วมกัน (การจับคู่สูงสุด) เท่ากับจำนวนจุดยอดน้อยที่สุดที่ต้องเลือกเพื่อ “ครอบคลุม” เส้นเชื่อมทั้งหมด ผลลัพธ์นี้เป็นรากฐานของปัญหาการจับคู่และการจัดสรรงาน และเชื่อมโยงกับขั้นตอนวิธีที่เรียกว่าอัลกอริทึมฮังกาเรียน (Hungarian algorithm) ที่ใช้แก้ปัญหาการมอบหมายงานในปัจจุบัน

เลมมาของเคอนิก (Kőnig’s lemma) กล่าวว่า ต้นไม้ที่มีจำนวนจุดยอดไม่จำกัดแต่แต่ละจุดแตกกิ่งได้เพียงจำนวนจำกัด จะต้องมีเส้นทางที่ยาวไม่สิ้นสุดอย่างน้อยหนึ่งเส้น เลมมานี้เป็นเครื่องมือที่ใช้ซ้ำแล้วซ้ำอีกในตรรกศาสตร์ ทฤษฎีการคำนวณ และการพิสูจน์ทฤษฎีบทความกระชับ

ควรสังเกตว่า “ทฤษฎีบทของเคอนิก” ในทฤษฎีเซตที่เกี่ยวกับการเปรียบเทียบจำนวนคาร์ดินัลเป็นผลงานของบิดาของเขา ยูลา เคอนิก ไม่ใช่เดเนช

ครูผู้จุดประกายนักคณิตศาสตร์ฮังการี

บรรยายและตำราของเคอนิกมีบทบาทสำคัญในการก่อให้เกิดงานด้านทฤษฎีกราฟของนักคณิตศาสตร์ฮังการีรุ่นถัดมา ซึ่งรวมถึงลัสโล เอเยด (László Egyed), พอล แอร์ดิช (Pál Erdős), ติบอร์ กัลไล (Tibor Gallai), เยอร์ดี ฮายอส (György Hajós), โยเชฟ คราอุส (József Kraus), ติบอร์ เซเล (Tibor Szele), ปาล ทูราน (Pál Turán) และเอนเดร วาโซนยี (Endre Vázsonyi) ซึ่งกัลไลเป็นนักศึกษาปริญญาเอกของเขาโดยตรง

ช่วงเวลามืดมนในปี ค.ศ. 1944

เคอนิกมีเชื้อสายยิวแต่ถูกเลี้ยงดูเป็นคริสต์ ซึ่งทำให้เขาไม่ตกอยู่ในอันตรายจากการประหัตประหารชาวยิวในฮังการีอยู่ช่วงหนึ่ง แต่สถานการณ์เปลี่ยนไปในวันที่ 15 ตุลาคม ค.ศ. 1944 เมื่อพรรคแอร์โรว์ครอสเข้ายึดอำนาจในประเทศ เพียงไม่กี่วันต่อมา ในวันที่ 19 ตุลาคม ค.ศ. 1944 เขาเลือกจบชีวิตตนเองเพื่อหนีการประหัตประหารของนาซี

มรดก

เดเนช เคอนิกเสียชีวิตก่อนจะได้เห็นทฤษฎีกราฟเบ่งบานเป็นสาขาที่ขาดไม่ได้ของวิทยาการคอมพิวเตอร์ การวิเคราะห์เครือข่าย และการวิจัยดำเนินงาน แต่ตำราของเขาเป็นรากฐานที่นักคณิตศาสตร์รุ่นหลังต่อยอด ปัจจุบัน SIAM (สมาคมคณิตศาสตร์อุตสาหกรรมและประยุกต์) มอบรางวัลเดเนช เคอนิก ให้แก่นักวิจัยรุ่นใหม่ด้านคณิตศาสตร์ไม่ต่อเนื่อง และมหาวิทยาลัยเทคนิคแห่งบูดาเปสต์จัดการแข่งขันคณิตศาสตร์ไม่ต่อเนื่องที่ใช้ชื่อเขา เพื่อระลึกถึงอาจารย์ผู้เขียนตำราทฤษฎีกราฟเล่มแรก