4 
 g1=Graph[{UndirectedEdge[a,b]}];
 GraphQ[g1]
 (*
   OUT: True
 *)
   (*Needs["Combinatorica`"]*)
 PlanarQ[g1]
 (*
    OUT: PlanarQ[.-.]
 *)
 Combinatorica`PlanarQ[g1]
 (*
   OUT: Combinatorica`PlanarQ[.-.]
 *)

为什么 PlanarQ 不返回 "True" 或 "False" ？

4

4 回答 4

4

您的图表不是Combinatorica图表，而是System图表。您需要明确指定上下文。

Needs["GraphUtilities`"];
g1 = System`Graph[{UndirectedEdge[a, b]}];
Combinatorica`PlanarQ[
  GraphUtilities`ToCombinatoricaGraph[g1]]

这会返回True，但总的来说，这个过程很痛苦，而且相当麻烦。我相信这Combinatorica正在消失，我建议尝试不这样做。

于 2011-06-02T12:37:06.477 回答
2

你可能需要：

Needs["GraphUtilities`"]
Needs["Combinatorica`"]

cg1 = ToCombinatoricaGraph[g1];

PlanarQ[cg1]

但是，我没有要检查的 v8。

于 2011-06-02T12:20:04.323 回答
2

请注意，Combinatorica 即将推出。然而，三个月前，Graph 项目的一位负责人告诉我，没有计划重新实现像BrelazColoringSystem Graph 这样的算法特定接口。所以，有些事情可能需要Combinatorica一段时间，解决这个问题的一种方法是尝试对所有内容使用 System'Graph，远离Combinatorica包路径，并通过将 Graph 对象显式转换为 Combinatorica'Graph 对象来使用 Combinatorica 函数，调用 Combinatorica 函数，然后转换回系统图。这是一些详细的讨论

对于后代，这是relabelGraph我用来解决 TomD 报告的排序问题的函数，

relabelGraph[g_Graph,labeling_]:=Module[{vcoords,gstyle,labelMap,adjMat,newOrder,newCoords,verts},
    verts=VertexList@g;
    vcoords=VertexCoordinates/.AbsoluteOptions[g,VertexCoordinates];
    gstyle=GraphStyle/.AbsoluteOptions[g,GraphStyle];
    labelMap=Thread[Range[Length[verts]]->labeling];

    adjMat=Normal@AdjacencyMatrix[g];
    newOrder=Ordering[VertexList[g]/.labelMap];

    newCoords=Thread[(VertexList[g]/.labelMap)->vcoords];

    AdjacencyGraph[adjMat[[newOrder,newOrder]],VertexCoordinates->newCoords,GraphStyle->gstyle]
];

下面是一种使用方法。这会产生类似于 的结果IndexGraph，但已排序VertexList

g=relabelGraph[g,Range@Length@VertexList@g];

我的其他一些“烦恼修复”功能在此处graphUsage.nb的包中进行了描述

于 2011-06-03T16:25:54.767 回答
1

这也只是一个注释。

我想特别提请注意可能存在的错误ToCombinatoricaGraph和可能的解决方法。它可能与原始问题无关。

另外，我使用的是 Mma 7，所以可能会在 v8 中修复。

如果我定义一个图表如下

Needs["Combinatorica`"]

Needs["GraphUtilities`"]

gr1 = {2 -> 4, 4 -> 3, 3 -> 1}

gr1的GraphPlot

在此处输入图像描述

比较以下内容：

EdgeList@gr1
EdgeList@ToCombinatoricaGraph@gr1
Edges@ToCombinatoricaGraph@gr1

输出

{{2, 4}, {4, 3}, {3, 1}}
{{1, 2}, {2, 3}, {3, 4}}
{{1, 2}, {2, 3}, {3, 4}}

我使用的解决方法是尽可能忽略，ToCombinatoricaGraph而是使用.FromOrderedPairs

例如

Edges@FromOrderedPairs@EdgeList@gr1
EdgeList@FromOrderedPairs@EdgeList@gr1

输出

{{2, 4}, {4, 3}, {3, 1}}
{{2, 4}, {3, 1}, {4, 3}}

另一个例子，Degrees

比较

Degrees@MakeSimple@ToCombinatoricaGraph[gr1]
VertexList@MakeSimple@ToCombinatoricaGraph[gr1]

输出

{1, 2, 2, 1}
{1, 2, 3, 4}

和

Degrees@MakeSimple@FromOrderedPairs@EdgeList@gr1
VertexList@MakeSimple@FromOrderedPairs@EdgeList@gr1

{1, 1, 2, 2}
{1, 2, 3, 4}

我还将包含一个带有Prufer 代码的示例，因为在这里我被严重“抓住了”（当时我不知道 SO）

LabeledTreeToCode@MakeSimple@ToCombinatoricaGraph@gr1
LabeledTreeToCode@MakeSimple@FromOrderedPairs@EdgeList@gr1

输出

{2, 3}
{3, 4}

（只有第二个答案是正确的）

我已将此情况报告给 Wolfram。看起来，它与创建图形时的顶点重新排序有关ToCombinatoricaGraph。这是回复的一部分（2009 年）

Edges 和 EdgeList 在 ToCombinatoricaGraph 对象上不起作用的原因是 Combinatorica 包是在这些功能之前开发的，并且结构尚未适应这些功能的操作。

Our development team is currently working to update the Combinatorica
package so that these functions will be compatible.  If you happen to

遇到任何其他问题，或有任何问题，请告诉我。

在我看来，ToCombinatoricaGraph需要小心使用（并尽可能避免）。但是，可能有很多情况（包括原始问题的其他答案中给出的用途）没有区别。

就我个人而言，我不希望看到Combinatorica包消失。它包含许多有用的功能（如果文档非常糟糕）。

于 2011-06-03T17:31:18.060 回答