1. Home
2. Questions
3. Tags
5. Users
6. Unanswered
Teams

Ask questions, find answers and collaborate at work with Stack Overflow for Teams.
Try Teams for free Explore Teams
Teams
Ask questions, find answers and collaborate at work with Stack Overflow for Teams. Explore Teams

Return to Answer

added 186 characters in body

Source Link

edited Mar 9, 2021 at 9:45

400.5k
18
488
929

am = {{0, 1, 0, 0, 0, 1}, {1, 0, 1, 0, 0, 0}, {0, 1, 0, 1, 1, 0}, {0, 
    0, 1, 1, 0, 1}, {0, 0, 1, 1, 0, 1}, {1, 0, 0, 1, 1, 1}};

g0 = UndirectedGraph[SimpleGraph@AdjacencyGraph[am]UndirectedGraph[SimpleGraph @ AdjacencyGraph @ am, 
  VertexCoordinates -> Reverse@CirclePoints[Reverse @ CirclePoints[{1, Pi}, 6], 
  VertexLabels -> "Name"]

trees = Select[TreeGraphQ[Graph@#] &] @ Select[VertexCount @ # == 6 &]@ 
  Subsets[EdgeList[g0], {5}];

Length @ trees

This matches what we should expect from Kirchhoff's Theorem:

Det[KirchhoffMatrix[g0][[2 ;;, 2 ;;]]]

We can also get the resultsame number using IGSpanningTreeCount from IGraphM package:

<< IGraphM`
IGSpanningTreeCount[g0]

These 32 trees fall into three isomorphic groups:

Length /@ Gather[Graph /@ trees, IsomorphicGraphQ]

{10, 16, 6}

Graph[#, VertexLabels -> Placed["Name", Center], VertexStyle -> White,
    GraphLayout -> "LayeredEmbedding", 
    VertexShapeFunction -> (Disk[#, Offset[7]] &), 
    AspectRatio -> 1] & /@ trees // Multicolumn[#, 6] &

HighlightGraph[g0, #, GraphHighlightStyle -> "Thick"] & /@ trees // 
 Multicolumn[#, 6, Appearance -> "Horizontal"] &

am = {{0, 1, 0, 0, 0, 1}, {1, 0, 1, 0, 0, 0}, {0, 1, 0, 1, 1, 0}, {0, 
    0, 1, 1, 0, 1}, {0, 0, 1, 1, 0, 1}, {1, 0, 0, 1, 1, 1}};

g0 = UndirectedGraph[SimpleGraph@AdjacencyGraph[am], 
  VertexCoordinates -> Reverse@CirclePoints[{1, Pi}, 6], 
  VertexLabels -> "Name"]

trees = Select[TreeGraphQ[Graph@#] &] @ Select[VertexCount @ # == 6 &]@ 
  Subsets[EdgeList[g0], {5}];

Length @ trees

This matches the result using IGSpanningTreeCount from IGraphM package:

<< IGraphM`
IGSpanningTreeCount[g0]

These 32 trees fall into three isomorphic groups:

Length /@ Gather[Graph /@ trees, IsomorphicGraphQ]

{10, 16, 6}

Graph[#, VertexLabels -> Placed["Name", Center], VertexStyle -> White,
    GraphLayout -> "LayeredEmbedding", 
    VertexShapeFunction -> (Disk[#, Offset[7]] &), 
    AspectRatio -> 1] & /@ trees // Multicolumn[#, 6] &

HighlightGraph[g0, #, GraphHighlightStyle -> "Thick"] & /@ trees // 
 Multicolumn[#, 6, Appearance -> "Horizontal"] &

am = {{0, 1, 0, 0, 0, 1}, {1, 0, 1, 0, 0, 0}, {0, 1, 0, 1, 1, 0}, {0, 
    0, 1, 1, 0, 1}, {0, 0, 1, 1, 0, 1}, {1, 0, 0, 1, 1, 1}};

g0 = UndirectedGraph[SimpleGraph @ AdjacencyGraph @ am, 
  VertexCoordinates -> Reverse @ CirclePoints[{1, Pi}, 6], 
  VertexLabels -> "Name"]

trees = Select[TreeGraphQ[Graph@#] &] @ Select[VertexCount @ # == 6 &]@ 
  Subsets[EdgeList[g0], {5}];

Length @ trees

This matches what we should expect from Kirchhoff's Theorem:

Det[KirchhoffMatrix[g0][[2 ;;, 2 ;;]]]

We can also get the same number using IGSpanningTreeCount from IGraphM package:

<< IGraphM`
IGSpanningTreeCount[g0]

These 32 trees fall into three isomorphic groups:

Length /@ Gather[Graph /@ trees, IsomorphicGraphQ]

{10, 16, 6}

Graph[#, VertexLabels -> Placed["Name", Center], VertexStyle -> White,
    GraphLayout -> "LayeredEmbedding", 
    VertexShapeFunction -> (Disk[#, Offset[7]] &), 
    AspectRatio -> 1] & /@ trees // Multicolumn[#, 6] &

HighlightGraph[g0, #, GraphHighlightStyle -> "Thick"] & /@ trees // 
 Multicolumn[#, 6, Appearance -> "Horizontal"] &

deleted 2 characters in body

Source Link

edited Mar 9, 2021 at 9:27

400.5k
18
488
929

am = {{0, 1, 0, 0, 0, 1}, {1, 0, 1, 0, 0, 0}, {0, 1, 0, 1, 1, 0}, {0, 
    0, 1, 1, 0, 1}, {0, 0, 1, 1, 0, 1}, {1, 0, 0, 1, 1, 1}};

g0 = UndirectedGraph[SimpleGraph@AdjacencyGraph[am], 
  VertexCoordinates -> Reverse@CirclePoints[{1, Pi}, 6], 
  VertexLabels -> "Name"]

trees = Select[TreeGraphQ[Graph@#] &] @ Select[VertexCount @ # == 6 &]@ 
  Subsets[EdgeList[g0], {5}];

Length @ trees

This matches the result using IGSpanningTreeCount from IGraphM package:

<< IGraphM`
IGSpanningTreeCount[g0]

These 32 trees fall into three isomorphic groups:

Length /@ Gather[Graph /@ trees, IsomorphicGraphQ]

{10, 16, 6}

Graph[#, VertexLabels -> Placed["Name", Center], VertexStyle -> White,
    GraphLayout -> "LayeredEmbedding", 
    VertexShapeFunction -> (Disk[#, Offset[7]] &), 
    AspectRatio -> 1] & /@ trees // Multicolumn[#, 6] &

HighlightGraph[g0, #, GraphHighlightStyle -> "Thick"] & /@ trees // 
 Multicolumn[#, 6, Appearance -> "Horizontal"] &

am = {{0, 1, 0, 0, 0, 1}, {1, 0, 1, 0, 0, 0}, {0, 1, 0, 1, 1, 0}, {0, 
    0, 1, 1, 0, 1}, {0, 0, 1, 1, 0, 1}, {1, 0, 0, 1, 1, 1}};

g0 = UndirectedGraph[SimpleGraph@AdjacencyGraph[am], 
  VertexCoordinates -> Reverse@CirclePoints[{1, Pi}, 6], 
  VertexLabels -> "Name"]

trees = Select[TreeGraphQ[Graph@#] &] @ Select[VertexCount @ # == 6 &]@ 
  Subsets[EdgeList[g0], {5}];

Length @ trees

This matches the result using IGSpanningTreeCount from IGraphM package:

<< IGraphM`
IGSpanningTreeCount[g0]

Graph[#, VertexLabels -> Placed["Name", Center], VertexStyle -> White,
    GraphLayout -> "LayeredEmbedding", 
    VertexShapeFunction -> (Disk[#, Offset[7]] &), 
    AspectRatio -> 1] & /@ trees // Multicolumn[#, 6] &

HighlightGraph[g0, #, GraphHighlightStyle -> "Thick"] & /@ trees // 
 Multicolumn[#, 6, Appearance -> "Horizontal"] &

am = {{0, 1, 0, 0, 0, 1}, {1, 0, 1, 0, 0, 0}, {0, 1, 0, 1, 1, 0}, {0, 
    0, 1, 1, 0, 1}, {0, 0, 1, 1, 0, 1}, {1, 0, 0, 1, 1, 1}};

g0 = UndirectedGraph[SimpleGraph@AdjacencyGraph[am], 
  VertexCoordinates -> Reverse@CirclePoints[{1, Pi}, 6], 
  VertexLabels -> "Name"]

trees = Select[TreeGraphQ[Graph@#] &] @ Select[VertexCount @ # == 6 &]@ 
  Subsets[EdgeList[g0], {5}];

Length @ trees

This matches the result using IGSpanningTreeCount from IGraphM package:

<< IGraphM`
IGSpanningTreeCount[g0]

These 32 trees fall into three isomorphic groups:

Length /@ Gather[Graph /@ trees, IsomorphicGraphQ]

{10, 16, 6}

Graph[#, VertexLabels -> Placed["Name", Center], VertexStyle -> White,
    GraphLayout -> "LayeredEmbedding", 
    VertexShapeFunction -> (Disk[#, Offset[7]] &), 
    AspectRatio -> 1] & /@ trees // Multicolumn[#, 6] &

HighlightGraph[g0, #, GraphHighlightStyle -> "Thick"] & /@ trees // 
 Multicolumn[#, 6, Appearance -> "Horizontal"] &

deleted 2 characters in body

Source Link

edited Mar 9, 2021 at 9:19

400.5k
18
488
929

am = {{0, 1, 0, 0, 0, 1}, {1, 0, 1, 0, 0, 0}, {0, 1, 0, 1, 1, 0}, {0, 
    0, 1, 1, 0, 1}, {0, 0, 1, 1, 0, 1}, {1, 0, 0, 1, 1, 1}};

g0 = UndirectedGraph[SimpleGraph@AdjacencyGraph[am], 
  VertexCoordinates -> Reverse@CirclePoints[{1, Pi}, 6], 
  VertexLabels -> "Name"]

trees = Select[TreeGraphQ[Graph@#] &] @ Select[VertexCount @ # == 6 &]@ 
  Subsets[EdgeList[g0], {5}];

Length @ trees

This matches the result using IGSpanningTreeCount from IGraphM package:

<< IGraphM`
IGSpanningTreeCount[g0]

Graph[#, VertexLabels -> Placed["Name", Center], VertexStyle -> White,
    GraphLayout -> "LayeredEmbedding", 
    VertexShapeFunction -> (Disk[#, Offset[7]] &), 
    AspectRatio -> 1] & /@ trees // Multicolumn[#, 6] &

HighlightGraph[g0, #, GraphHighlightStyle -> "Thick"] & /@ trees // 
 Multicolumn[#, 6, Appearance -> "Horizontal"] &

am = {{0, 1, 0, 0, 0, 1}, {1, 0, 1, 0, 0, 0}, {0, 1, 0, 1, 1, 0}, {0, 
    0, 1, 1, 0, 1}, {0, 0, 1, 1, 0, 1}, {1, 0, 0, 1, 1, 1}};

g0 = UndirectedGraph[SimpleGraph@AdjacencyGraph[am], 
  VertexCoordinates -> Reverse@CirclePoints[{1, Pi}, 6], 
  VertexLabels -> "Name"]

trees = Select[TreeGraphQ[Graph@#] &] @ Select[VertexCount @ # == 6 &]@ 
  Subsets[EdgeList[g0], {5}];

Length @ trees

This matches the result using IGSpanningTreeCount from IGraphM package:

<< IGraphM`
IGSpanningTreeCount[g0]

Graph[#, VertexLabels -> Placed["Name", Center], VertexStyle -> White,
    GraphLayout -> "LayeredEmbedding", 
    VertexShapeFunction -> (Disk[#, Offset[7]] &), 
    AspectRatio -> 1] & /@ trees // Multicolumn[#, 6] &

HighlightGraph[g0, #, GraphHighlightStyle -> "Thick"] & /@ trees // 
 Multicolumn[#, 6, Appearance -> "Horizontal"] &

am = {{0, 1, 0, 0, 0, 1}, {1, 0, 1, 0, 0, 0}, {0, 1, 0, 1, 1, 0}, {0, 
    0, 1, 1, 0, 1}, {0, 0, 1, 1, 0, 1}, {1, 0, 0, 1, 1, 1}};

g0 = UndirectedGraph[SimpleGraph@AdjacencyGraph[am], 
  VertexCoordinates -> Reverse@CirclePoints[{1, Pi}, 6], 
  VertexLabels -> "Name"]

trees = Select[TreeGraphQ[Graph@#] &] @ Select[VertexCount @ # == 6 &]@ 
  Subsets[EdgeList[g0], {5}];

Length @ trees

This matches the result using IGSpanningTreeCount from IGraphM package:

<< IGraphM`
IGSpanningTreeCount[g0]

Graph[#, VertexLabels -> Placed["Name", Center], VertexStyle -> White,
    GraphLayout -> "LayeredEmbedding", 
    VertexShapeFunction -> (Disk[#, Offset[7]] &), 
    AspectRatio -> 1] & /@ trees // Multicolumn[#, 6] &

HighlightGraph[g0, #, GraphHighlightStyle -> "Thick"] & /@ trees // 
 Multicolumn[#, 6, Appearance -> "Horizontal"] &

added 330 characters in body

Source Link

edited Mar 9, 2021 at 9:13

400.5k
18
488
929

Loading

Source Link

created Mar 9, 2021 at 8:58

400.5k
18
488
929

Loading