流程圖的可證明的平面性

我有一個問題：是否有任何參考文獻（例如紙張）具有流體佈局平面性的證明？任何人都可以提出生成流程圖（平面）佈局的算法嗎？流程圖的可證明的平面性

我知道那裏有一些代碼到流程圖的工具，但我不知道它們的內部。

來源

2010-03-15 Nikolaos Kavvadias

這取決於你所說的「流程圖」。如果流程圖是簡單的類型，即。一個沒有節點指向上的有向圖（到以前可能已經訪問過的節點），那麼你所描述的是一個tree，它的嵌入在平面上是微不足道的。

但是如果您的流程圖有循環（循環），那麼構造一個反例很簡單，一個圖不是而是可嵌入平面中。對於一個人爲的例子（因爲沒有規定限制）考慮完整的圖K5，其中每個節點彼此連接。該圖不是平面的。

至於繪製圖形，我想推薦優秀的工具GraphViz，其中繪製（其中包括）美麗的流程圖與自動佈局。您可以選擇一個渲染引擎來嘗試在圖形中保留一些順序，並且存在明確的層次結構圖選項。

來源

2010-03-15 06:04:04 Hooked

嗨帶鉤我流程圖將不得不爲c建模lassic命令式循環（例如repeat-until或while-do）。我看到了一些生成平面佈局的方法。但是，如果這隻能通過添加節點（不確定），那麼你當然是對的。我記得圖中的檢測完成（子）圖K3,3和K5證明了非平面性。我知道Graphviz並使用它很長一段時間了。從我使用的版本2.22開始，它沒有專門針對流程圖的佈局引擎。親切的問候 -kavi – 2010-03-15 06:45:11

你是正確的，檢測完整的子圖K3,3和K5可以證明/反駁平面性（庫拉託斯基定理），但該方法是一個NP完全問題。在平面性方面也有一些O（N^3）方法。至於GraphViz，我指的是'點'佈局，它在我需要流程圖時隨時繪製一個'足夠好'的佈局。如果你不喜歡你所看到的東西，你可以隨時用手搓一個元素。祝你好運！ – Hooked 2010-03-15 07:36:26

平面性測試可以在線性時間內完成：高效的平面性測試（Hopcroft，Tarjan，1974）（http://portal.acm.org/citation.cfm?id=321852） – 2010-04-07 13:54:58

我不同意Hooked。流程圖，有一些限制（使用循環是不是其中之一），是平面的。一些例子：

單一原始指令轉換爲一個平面圖形（單個節點）
語句序列：如果語句可以被翻譯爲平面圖，該序列可以本身被轉換爲平面圖（簡單地通過連接這些子圖）
甲功能：與上述相同
A（repeat-until，while-do等）循環是形成循環語句序列。週期也很好，，只要他們正確嵌套（並且這樣的結構被設計爲正確嵌套）。
（其可以跳goto，或break/continue/return語句）轉到陳述不確定。如果你有一個嵌套循環，並且從內部跳出外部循環，那麼這樣一個邊將清楚地與包含它的循環（循環，函數）相交。如果代碼被轉換爲一次退出一個循環，這些也沒關係。（這種翻譯與簡單地引入節點來模擬交叉點沒有太大差別）。

必須有一個更系統的方式正式證明流程圖從一組特定結構的成分推導是平面的，我希望我能在5分鐘內想起來了，但沒有運氣:)

更新：順便說一下，goto S能平凡創建K3,3或K5，例如這是K5（在老式QBasic的！）：

00 GOTO (INT(RND * 5) * 10) 
10 GOTO (INT(RND * 5) * 10) 
20 GOTO (INT(RND * 5) * 10) 
30 GOTO (INT(RND * 5) * 10) 
40 GOTO (INT(RND * 5) * 10)

來源

2010-04-07 14:13:18

事後看來，我發現使用循環是一個不好的選擇 - 我的意思是循環的圖形理論意義上，即。對於非平面圖，底層圖中的循環是必需的（但不足）。你上面提到的這個詞的意圖是什麼，「goto」式的說法。感謝您評論中的Planarity O（N）測試鏈接！ – Hooked 2010-04-08 21:51:26

流程圖的可證明的平面性

回答

相關問題