ASKSAGE: Sage Q&A Forum - Latest question feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Fri, 10 Jul 2020 15:04:04 -0500Edge isoperimetric numberhttps://ask.sagemath.org/question/52410/edge-isoperimetric-number/This is probably a very silly question. How does one get the edge isoperimetric number of a graph?
As seen under [here](https://trac.sagemath.org/ticket/21942) there should be an algorithm for it, but when I define a graph (say H), then
<code>
edge_isoperimetric_number(H)
</code>
returns "name 'edge_isoperimetric_number' is not defined"
and
<code>
H.edge_isoperimetric_number()
</code>
returns "'Graph' object has no attribute 'edge_isoperimetric_number'"
(while
<code>
edge_isoperimetric_number?
</code>
returns "Object `edge_isoperimetric_number` not found."
So how do I load said algorithm for use?ARGFri, 10 Jul 2020 15:04:04 -0500https://ask.sagemath.org/question/52410/fractional chromatic index of edge-weighted graphshttps://ask.sagemath.org/question/46900/fractional-chromatic-index-of-edge-weighted-graphs/How would you compute the fractional chromatic index of an edge-weighted graph using SAGE?
The built-in function fractional_chromatic_index seems to compute the fractional chromatic index for only unweighted graphs. For instance, if $G$ is the 5-cycle graph, its fractional chromatic index is $2.5$. But if one of the edges can be ignored, say by giving it a zero weight, then the fractional chromatic index becomes $2$.
The code and output below shows that SAGE ignores the edge-weights (notice that the edge-weights need not be integral - in the graph below, the correct value of the fractional chromatic index is 2.1, which is the maximum sum $1.1+1.0$ of weights of edges incident to a vertex):
sage: G = graphs.EmptyGraph()
sage: G.add_edges([(1,2,1.1),(2,3,1),(3,4,1),(4,5,1),(5,1,0)])
sage: G.fractional_chromatic_index()
5/2
sage:
Is there some way to get the built-in function to take edge weights into account? Or can this value be computed using some other method?Ashwin GanesanTue, 11 Jun 2019 03:52:15 -0500https://ask.sagemath.org/question/46900/Way to solve max_split enumerationhttps://ask.sagemath.org/question/38283/way-to-solve-max_split-enumeration/Hello everyone,
I try to solve a problem on graphs. The graphs contain two types of nodes, a first type linked together containing max_cliques that I seek to determine. A second one connected only to the first.
For the moment I enumerate the biggest cliques of the first type, then determines for each the number of nodes of the second type related to this one. Finally I list the one with the largest number of nodes of the second type.
So I'm looking to find the biggest split graph.
Do you have an idea to improve my current way?AlexJSun, 16 Jul 2017 05:32:13 -0500https://ask.sagemath.org/question/38283/multi commodity algorithm referencehttps://ask.sagemath.org/question/37028/multi-commodity-algorithm-reference/ Hello,
I'm using "multicommodity_flow()" method for my research and I really like to know what is the reference for the solution used in the code, like a publication, book or article.
Thanks,
AmirAmir19Wed, 22 Mar 2017 03:09:04 -0500https://ask.sagemath.org/question/37028/Multi-Commodity Flow problem, solution referencehttps://ask.sagemath.org/question/37029/multi-commodity-flow-problem-solution-reference/ Hello,
I am using "multicommodity_flow()" method for my research and I would like to know the reference behind the solution, like a paper, book or an article.
Thanks,
AmirAmir19Wed, 22 Mar 2017 03:12:08 -0500https://ask.sagemath.org/question/37029/Recursive Algorithm for Graph Coloringhttps://ask.sagemath.org/question/34051/recursive-algorithm-for-graph-coloring/In a 2014 article by Exoo, Ismailescu, and Lim ("On the Chromatic Number of R^4"), a recursive algorithm is described that verifies the absence of a proper $k$-coloring of a graph $G$. The authors include only the following description of the algorithm.
"[The program is] based on the following recursive procedure that does an exhaustive search for a $K$-coloring of a graph of order $N$. It employs a global variable *color*, an array of order $N$, which records the color of each vertex $v$ for $1 \leq v \leq N$. The search is initiated with the call DFS(1)."
procedure DFS(v):
Local variable: FCSet - the set of feasible colors for vertex v.
if v > N:
All vertices have been colored, report G is K-colorable.
Exit.
end if
FCSet = {1 ... K}
for u = 1 to v-1:
if u is adjacent to v:
FCSet = FCSet - color(u)
end if
end for
for c in FCSet:
color(v) = c
DFS(v+1)
end for
end procedure
I am having difficulty implementing this algorithm in Sage. Given the nature of the program, I thought Java would be a more natural programming language to use for this algorithm, but I'm afraid I am not familiar with Java syntax.
Any help with implementing this algorithm would be greatly appreciated! JEAThu, 07 Jul 2016 12:53:25 -0500https://ask.sagemath.org/question/34051/Dotted and dashed lines in directed graphshttps://ask.sagemath.org/question/31304/dotted-and-dashed-lines-in-directed-graphs/Hi,
I would like to know if it is possible to do (one of) the following with Sage.
Reading
http://doc.sagemath.org/html/en/reference/plotting/sage/graphs/graph_plot.html
I saw that it is possible to draw dashed and dotted lines. Now my questions are
1) Is it possible to produce an output graphic where some edges are dotted and some edges are dashed?
2) Is it possible to force the text in the labels of the vertices, e.g. M2, M4, M1 instead of 0,1,2?
Thanks for the help!
BernThu, 03 Dec 2015 20:39:18 -0600https://ask.sagemath.org/question/31304/