Items tagged with graphtheory


Suppose,  there are

  • 50 vertices

  • list of coordinates of these 50 vertices


Now I want to create a graph with minimum distance.

The starting point of the graph should be vertice 1. From there,  the closest point has to be added to a list X. and from this point, it should calculate again the closest point and add this value to the same list X.


So actually I want to start in point 1 and I want to see the sequence of how the graph (I think minimum spanning tree?) is created


How can I code this in Maple?


Thanks in advance!


I could keep on using the commands 




but then this is not helpful because I do not get non-isomorphic graph each time and there are repetitions. So any other suggestions would be very helpful. 


This question concerns the package GraphTheory
( Maple 2015 on a Windows 7 PC )

Let G1 be some graph and V a list of vertices in G1
The default colors DrawGraph uses for the vertices is yellow

I define the graph G2 this way :
    G2 := copy(G1):
    HighlightVertex(G2, V, red);
Obviously the result is a graph where vertices in V are red while the remaining ones are still yellow

Question 1 :  Why does the command DrawGraph(G1) returns exactly the same picture ?
I have thought that defining G2 as a copy of G1 would have preserved the default colouring of the vertices.
Note that the same undesired (at least for me) thing occurs with the  HighlightEdges command.

Question 2 : Is it possible to retrieve the original colouring of G1 without using HighlightVertex(G1, V, yellow)  ?

Thank you in advance

Hi everybody, 

Only weights of type "numeric" can be used in a weighted graph (package GraphTheory) .
Is it possible to bypass this limitation and affect an infinite weight to an edge ?
If not possible, does it exist some "highest numeric value" in Maple I could use instead ?
(the trick of a very high value doesn't suit me)

Subsidiary question : is it possible to change the printing format for those weights ?
For instance   GraphTheory:-SetEdgeWeight(MyGraph, MyEdge, 123.4) plots the value 123 on edfe MyEdge

Thanks in advance

how to define VertexWeight in Graph Theory package

Could someone please explain to me why the procedure GraphTheory:-CycleBasis requires that the vertices of a graph be integers for it to work correctly ?
(while the definition of a graph supports other types of vertex names)


#------------------------------------------------------- test 1

g1 := Graph({{"a", 1}, {1, 3}, {"a", 3}});

Error, (in GraphTheory:-CycleBasis) cannot determine if this expression is true or false: "a" < 1

#------------------------------------------------------- test 2

g2 := Graph({{a, 1}, {1, 3}, {a, 3}});

Error, (in GraphTheory:-CycleBasis) cannot determine if this expression is true or false: a < 1


#------------------------------------------------------- test 3

g3 := Graph({{4, 1}, {1, 3}, {4, 3}});

[[1, 3, 4]]

Knowing this limitation I usually rename to integers the vertices of the graphs, next do some operations, and next go back to the original names.

Thanks for any explanation.

This week I am participating in 19th Ising lectures (see The Serguei Nechaev's talk inspired me to ask the question:
"How to simulate a random walk on an undirected and unweighted (and, of course, connected) graph
(All the paths from a vertex of degree k have the same probability 1/k.)?"
A Maple procedure to this end is welcome.

I am looking for a quick implementation in Maple to approximate a solution to the travelling salesman problem in a graph of several thousand vertices randomly placed in the unit square. I've tried TravelingSaleman in the GraphTheory package; it bogs down with just a handful (say, twelve) of vertices. I also tried Bruno Buerrier's implementation of the two-opt algorithm; on my machine that took more than a day for 2048 vertices. 

Is anyone aware of a quicker implementation in Maple?

Hello I'm having trouble create Konigsberg Graph on Maple. Here's the picture. Sorry if it's not clear enough. Thanks!

I do not know! I am a novice in maple as well as in graph theory. I attach a doc in which i attempted to learn what is network. It seems alright with maple as it gives as what it understands as horizontal and vertical network. I do not expect a horizontal line as horizontal network and vertical line as vertical network, in which case a horizontal line with nodes 1 and 2 will be vertical network if  draw it vertically. The maple, in my opinion ( i am not a maple man) gives the answer in a vertical pattern, rightly so for clarity and space constraint.

I am sorry if i am confusing.  The document in my attempt to know more may give you also more insight. Thanks.



N := GraphTheory:-RandomGraphs:-RandomNetwork(4, 0):


DrawNetwork(N, vertical)




O1 := GraphTheory:-RandomGraphs:-RandomNetwork(4, 1):


GraphTheory:-DrawNetwork(O1, vertical)





P := GraphTheory:-RandomGraphs:-RandomNetwork(4, 0):


GraphTheory:-DrawNetwork(P, horizontal)




Q := GraphTheory:-RandomGraphs:-RandomNetwork(4, 1):


GraphTheory:-DrawNetwork(Q, horizontal)





In Maple 2015, the DrawNetwork command option "horizontal" does not seem to work. Is this a bug? It doesn't even display horizontally on the online Maple Help webpage. Any help would be appreciated.

In the below file, I have tried to create tree using Graphtheory and export it to file. But exporting works only if I read the procedure twice and that too after running the procedure.


I found some codes for drawing my Graph in Maple:

[>  with(GraphTheory);

     W := Graph(undirected, {{0, 1}, {0, 2}, {0, 3}}):

     HighlightEdges(W, W, black):

     HighlightVertex(W, [1, 2, 3, 0], gray):

     DrawGraph( W);

 The way that the graph was plotted was not what I wanted to have. In fact, I expected to have something like this one:

I mean the vertexes are shaped by circles not by boxs. Moreover, one may want to see labels below (or above) the circled nodes. My question is 

" Is there any certain codes we can use to have this graph like the picture above? Can we manage the labels to be appeared near the nodes in Maple?

Thanks for your time!

How to find all nonisomorphic undirected graphs with 5 vertexes? Of course, with Maple.

do graph have invariant for invariant of cayley graph

1 2 Page 1 of 2