庫拉托夫斯基定理

庫拉托夫斯基定理，即證明一個圖是平面圖的必要充分條件是 它不包含任何同胚於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年起任教於華沙大學。

作者貢獻

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