庫拉托夫斯基定理

庫拉托夫斯基定理

庫拉托夫斯基定理,即證明一個圖是平面圖的必要充分條件是 它不包含任何同胚於K5或K3,3的子圖。

基本介紹

  • 中文名:庫拉托夫斯基定理
  • 外文名:the Theorm of Kuratowski
  • 提出者:Kuratowski
  • 提出時間:1930年
  • 套用學科:數學
  • 適用領域範圍:幾何學
定理背景,判定方法,定理內容,作者,作者貢獻,

定理背景

最常見的就是布線問題。一個複雜的網路能否布在平面上而又不自相交叉?做印製電路時自然會碰到這個問題。有的圖把一條對角線移到方形外面就可以布在平面上。但有的圖卻無論怎樣移動都不能布在平面上。1930年K·庫拉托夫斯基證明,一個網路是否能嵌入平面,就看其中是否不含有k5或k3,3兩個圖之一。

判定方法

判斷一個圖是否為平面圖是一件困難的事。通常我們可以採用直觀的方法,即:在圖中找出一個長度儘可能大的且邊不相交的圈;然後將圖中那些相交於非結點的邊,適當放置在已選定的圈內側或外側,若能避免除結點之外邊的相交,則該圖為平面圖,否則便是非平面圖。
例如,K5不是平面圖,因為無論如何畫都不能使其所有邊不相交。

定理內容

波蘭數學家庫拉托夫斯基(Kuratowski)在1930年給出了判定一個圖是平面圖的這個充要條件。這個定理證明太複雜,一般教材僅介紹不證明。一個圖是平面圖的必要充分條件是, 它不包含任何同胚於K5或K3,3的子圖。
Kuratowski定理的實際套用較困難。

作者

庫拉托夫斯基(Kazimierz Kuratowski,1896年2月2日-1980年6月18日),波蘭數學家。他主要研究點集拓撲學和集合論。
庫拉托夫斯基的父親是華沙的著名律師。當時華沙受俄羅斯統治,進入當地大學必須經過俄語的考試。庫氏沒有就讀俄語中學,決定到蘇格蘭學習工程。1913年10月,他進入了格拉斯哥大學,那年他得了班內的數學獎。1914年,他回到波蘭度假,不料第一次世界大戰暴發,他便沒有回格拉斯哥。1915年11月,俄軍撤出華沙,華沙大學改用波蘭語,庫氏選擇修讀數學。
在大學內有幾個教授對庫氏影響很深:博士論文導師Janiszewski和Mazurkiewicz、瓦茨瓦夫·謝爾賓斯基、Lukasiewicz。前三位都研究當時很新鮮的領域拓撲學。最後者研究數理邏輯,他的研討會啟發了庫氏的第一篇論文(1917年)。1927年被聘為利沃夫工業大學(Politechnika Lwowska)教授,1934年起任教於華沙大學。

作者貢獻

  • 庫拉托夫斯基閉包公理
  • 塔斯基–庫拉托夫斯基算法
  • 平面圖的庫拉托夫斯基定理
  • 庫拉托夫斯基十四集問題
  • 佐恩引理的證明

相關詞條

熱門詞條

聯絡我們