ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sat, 18 Feb 2023 09:33:44 +0100Number of disjoint hamiltonian cycles in a graphhttps://ask.sagemath.org/question/65157/number-of-disjoint-hamiltonian-cycles-in-a-graph/I wish to obtain the maximum number of mutually disjoint hamiltonian cycles in a given graph. Is there any command in SageMath to do it. I think of iterating over getting the hamiltonian cycle of the graph using `G.hamiltonian_cycle()` function, by deleting the edges of the cycles obtained at each successive iteration from the graph. However, is there a built-in function in SageMath for this? Thanks beforehand.Fri, 02 Dec 2022 16:26:06 +0100https://ask.sagemath.org/question/65157/number-of-disjoint-hamiltonian-cycles-in-a-graph/Comment by vidyarthi for <p>I wish to obtain the maximum number of mutually disjoint hamiltonian cycles in a given graph. Is there any command in SageMath to do it. I think of iterating over getting the hamiltonian cycle of the graph using <code>G.hamiltonian_cycle()</code> function, by deleting the edges of the cycles obtained at each successive iteration from the graph. However, is there a built-in function in SageMath for this? Thanks beforehand.</p>
https://ask.sagemath.org/question/65157/number-of-disjoint-hamiltonian-cycles-in-a-graph/?comment=65191#post-id-65191@vdelecroix yes, I want the maximum number of disjoint hamiltonian cycles in a graph. Yes, my method would work for maximal, but I actually wanted maximum of such cycles. edited the questionSat, 03 Dec 2022 16:28:10 +0100https://ask.sagemath.org/question/65157/number-of-disjoint-hamiltonian-cycles-in-a-graph/?comment=65191#post-id-65191Comment by vidyarthi for <p>I wish to obtain the maximum number of mutually disjoint hamiltonian cycles in a given graph. Is there any command in SageMath to do it. I think of iterating over getting the hamiltonian cycle of the graph using <code>G.hamiltonian_cycle()</code> function, by deleting the edges of the cycles obtained at each successive iteration from the graph. However, is there a built-in function in SageMath for this? Thanks beforehand.</p>
https://ask.sagemath.org/question/65157/number-of-disjoint-hamiltonian-cycles-in-a-graph/?comment=65192#post-id-65192@David Coudert thanks, but could you just slightly elaborate?Sat, 03 Dec 2022 16:28:51 +0100https://ask.sagemath.org/question/65157/number-of-disjoint-hamiltonian-cycles-in-a-graph/?comment=65192#post-id-65192Comment by vdelecroix for <p>I wish to obtain the maximum number of mutually disjoint hamiltonian cycles in a given graph. Is there any command in SageMath to do it. I think of iterating over getting the hamiltonian cycle of the graph using <code>G.hamiltonian_cycle()</code> function, by deleting the edges of the cycles obtained at each successive iteration from the graph. However, is there a built-in function in SageMath for this? Thanks beforehand.</p>
https://ask.sagemath.org/question/65157/number-of-disjoint-hamiltonian-cycles-in-a-graph/?comment=65167#post-id-65167Also, your question is not entirely clear. You want the maximal number of pairwise disjoint hamiltonian cycles? I doubt that starting with a random hamiltonian cycle (such as given by `G.hamiltonian_cycle()`), deleting it and repeating the procedure would give this maximum. If you want a maximal collection of pairwise disjoint hamiltonian cycles (ie such that what remains is not hamiltonian) your suggestion would certainly works.Fri, 02 Dec 2022 21:18:13 +0100https://ask.sagemath.org/question/65157/number-of-disjoint-hamiltonian-cycles-in-a-graph/?comment=65167#post-id-65167Comment by David Coudert for <p>I wish to obtain the maximum number of mutually disjoint hamiltonian cycles in a given graph. Is there any command in SageMath to do it. I think of iterating over getting the hamiltonian cycle of the graph using <code>G.hamiltonian_cycle()</code> function, by deleting the edges of the cycles obtained at each successive iteration from the graph. However, is there a built-in function in SageMath for this? Thanks beforehand.</p>
https://ask.sagemath.org/question/65157/number-of-disjoint-hamiltonian-cycles-in-a-graph/?comment=65159#post-id-65159We don't have such method in Sagemath. This is a hard optimisation problem. You can use integer linear programming to model and solve it.Fri, 02 Dec 2022 18:16:15 +0100https://ask.sagemath.org/question/65157/number-of-disjoint-hamiltonian-cycles-in-a-graph/?comment=65159#post-id-65159Answer by David Coudert for <p>I wish to obtain the maximum number of mutually disjoint hamiltonian cycles in a given graph. Is there any command in SageMath to do it. I think of iterating over getting the hamiltonian cycle of the graph using <code>G.hamiltonian_cycle()</code> function, by deleting the edges of the cycles obtained at each successive iteration from the graph. However, is there a built-in function in SageMath for this? Thanks beforehand.</p>
https://ask.sagemath.org/question/65157/number-of-disjoint-hamiltonian-cycles-in-a-graph/?answer=65209#post-id-65209This method will return the maximum number of edge disjoint Hamiltonian cycles. This is certainly not the best possible formulation.
def disjoint_hamiltonian_cycles(g, solver=None, verbose=0,
*, integrality_tolerance=1e-3):
"""
"""
from sage.numerical.mip import MixedIntegerLinearProgram
from sage.numerical.mip import MIPSolverException
from sage.graphs.graph import Graph
UB = min(g.degree()) // 2
if not UB:
raise EmptySetError("the given graph is not Hamiltonian")
eps = 1 / (2*Integer(g.order()))
x = next(g.vertex_iterator())
while True:
# Search for UB edge disjoint Hamiltonian cycles
p = MixedIntegerLinearProgram(solver=solver)
f = p.new_variable(binary=True)
r = p.new_variable(nonnegative=True)
# An edge belongs to a unique cycle
for e in g.edge_iterator(labels=False):
p.add_constraint(p.sum(f[frozenset(e), i] for i in range(UB)) <= 1)
# All the vertices of cycle i have degree 2
for i in range(UB):
for v in g:
p.add_constraint(p.sum(f[frozenset((u, v)), i] for u in g.neighbor_iterator(v)), min=2, max=2)
# Connectivity constraints based on the maximum average degree
for i in range(UB):
# r is greater than f
for u, v in g.edge_iterator(labels=None):
p.add_constraint(r[u, v, i] + r[v, u, i] - f[frozenset((u, v)), i], min=0)
# no cycle which does not contain x
for v in g:
if v != x:
p.add_constraint(p.sum(r[u, v, i] for u in g.neighbor_iterator(v)), max=1 - eps)
try:
p.solve(log=verbose)
f_val = p.get_values(f, convert=bool, tolerance=integrality_tolerance)
tsp = [Graph() for i in range(UB)]
for i in range(UB):
tsp[i].add_vertices(g.vertex_iterator())
tsp[i].set_pos(g.get_pos())
for (e, i), b in f_val.items():
if b:
tsp[i].add_edge(e)
return tsp
except MIPSolverException:
UB -= 1
if not UB:
raise EmptySetError("the given graph is not Hamiltonian")
You get:
sage: G = graphs.CompleteGraph(5)
sage: T = disjoint_hamiltonian_cycles(G)
sage: T
[Graph on 5 vertices, Graph on 5 vertices]
sage: [t.edges(labels=False, sort=True) for t in T]
[[(0, 1), (0, 3), (1, 4), (2, 3), (2, 4)],
[(0, 2), (0, 4), (1, 2), (1, 3), (3, 4)]]
sage: G = graphs.CompleteGraph(7)
sage: T = disjoint_hamiltonian_cycles(G)
sage: [t.edges(labels=False, sort=True) for t in T]
[[(0, 1), (0, 4), (1, 6), (2, 3), (2, 5), (3, 6), (4, 5)],
[(0, 2), (0, 5), (1, 3), (1, 4), (2, 6), (3, 5), (4, 6)],
[(0, 3), (0, 6), (1, 2), (1, 5), (2, 4), (3, 4), (5, 6)]]
Sun, 04 Dec 2022 12:40:53 +0100https://ask.sagemath.org/question/65157/number-of-disjoint-hamiltonian-cycles-in-a-graph/?answer=65209#post-id-65209Comment by David Coudert for <p>This method will return the maximum number of edge disjoint Hamiltonian cycles. This is certainly not the best possible formulation.</p>
<pre><code>def disjoint_hamiltonian_cycles(g, solver=None, verbose=0,
*, integrality_tolerance=1e-3):
"""
"""
from sage.numerical.mip import MixedIntegerLinearProgram
from sage.numerical.mip import MIPSolverException
from sage.graphs.graph import Graph
UB = min(g.degree()) // 2
if not UB:
raise EmptySetError("the given graph is not Hamiltonian")
eps = 1 / (2*Integer(g.order()))
x = next(g.vertex_iterator())
while True:
# Search for UB edge disjoint Hamiltonian cycles
p = MixedIntegerLinearProgram(solver=solver)
f = p.new_variable(binary=True)
r = p.new_variable(nonnegative=True)
# An edge belongs to a unique cycle
for e in g.edge_iterator(labels=False):
p.add_constraint(p.sum(f[frozenset(e), i] for i in range(UB)) <= 1)
# All the vertices of cycle i have degree 2
for i in range(UB):
for v in g:
p.add_constraint(p.sum(f[frozenset((u, v)), i] for u in g.neighbor_iterator(v)), min=2, max=2)
# Connectivity constraints based on the maximum average degree
for i in range(UB):
# r is greater than f
for u, v in g.edge_iterator(labels=None):
p.add_constraint(r[u, v, i] + r[v, u, i] - f[frozenset((u, v)), i], min=0)
# no cycle which does not contain x
for v in g:
if v != x:
p.add_constraint(p.sum(r[u, v, i] for u in g.neighbor_iterator(v)), max=1 - eps)
try:
p.solve(log=verbose)
f_val = p.get_values(f, convert=bool, tolerance=integrality_tolerance)
tsp = [Graph() for i in range(UB)]
for i in range(UB):
tsp[i].add_vertices(g.vertex_iterator())
tsp[i].set_pos(g.get_pos())
for (e, i), b in f_val.items():
if b:
tsp[i].add_edge(e)
return tsp
except MIPSolverException:
UB -= 1
if not UB:
raise EmptySetError("the given graph is not Hamiltonian")
</code></pre>
<p>You get:</p>
<pre><code>sage: G = graphs.CompleteGraph(5)
sage: T = disjoint_hamiltonian_cycles(G)
sage: T
[Graph on 5 vertices, Graph on 5 vertices]
sage: [t.edges(labels=False, sort=True) for t in T]
[[(0, 1), (0, 3), (1, 4), (2, 3), (2, 4)],
[(0, 2), (0, 4), (1, 2), (1, 3), (3, 4)]]
sage: G = graphs.CompleteGraph(7)
sage: T = disjoint_hamiltonian_cycles(G)
sage: [t.edges(labels=False, sort=True) for t in T]
[[(0, 1), (0, 4), (1, 6), (2, 3), (2, 5), (3, 6), (4, 5)],
[(0, 2), (0, 5), (1, 3), (1, 4), (2, 6), (3, 5), (4, 6)],
[(0, 3), (0, 6), (1, 2), (1, 5), (2, 4), (3, 4), (5, 6)]]
</code></pre>
https://ask.sagemath.org/question/65157/number-of-disjoint-hamiltonian-cycles-in-a-graph/?comment=66501#post-id-66501Note that the number of edge disjoint Hamiltonian cycles is upper bounded by half the minimum degree of the graph
sage: G = graphs.CompleteGraph(5)
sage: min(G.degree()) // 2
2
sage: G = graphs.CompleteGraph(7)
sage: min(G.degree()) // 2
3Sat, 18 Feb 2023 09:33:44 +0100https://ask.sagemath.org/question/65157/number-of-disjoint-hamiltonian-cycles-in-a-graph/?comment=66501#post-id-66501Comment by vidyarthi for <p>This method will return the maximum number of edge disjoint Hamiltonian cycles. This is certainly not the best possible formulation.</p>
<pre><code>def disjoint_hamiltonian_cycles(g, solver=None, verbose=0,
*, integrality_tolerance=1e-3):
"""
"""
from sage.numerical.mip import MixedIntegerLinearProgram
from sage.numerical.mip import MIPSolverException
from sage.graphs.graph import Graph
UB = min(g.degree()) // 2
if not UB:
raise EmptySetError("the given graph is not Hamiltonian")
eps = 1 / (2*Integer(g.order()))
x = next(g.vertex_iterator())
while True:
# Search for UB edge disjoint Hamiltonian cycles
p = MixedIntegerLinearProgram(solver=solver)
f = p.new_variable(binary=True)
r = p.new_variable(nonnegative=True)
# An edge belongs to a unique cycle
for e in g.edge_iterator(labels=False):
p.add_constraint(p.sum(f[frozenset(e), i] for i in range(UB)) <= 1)
# All the vertices of cycle i have degree 2
for i in range(UB):
for v in g:
p.add_constraint(p.sum(f[frozenset((u, v)), i] for u in g.neighbor_iterator(v)), min=2, max=2)
# Connectivity constraints based on the maximum average degree
for i in range(UB):
# r is greater than f
for u, v in g.edge_iterator(labels=None):
p.add_constraint(r[u, v, i] + r[v, u, i] - f[frozenset((u, v)), i], min=0)
# no cycle which does not contain x
for v in g:
if v != x:
p.add_constraint(p.sum(r[u, v, i] for u in g.neighbor_iterator(v)), max=1 - eps)
try:
p.solve(log=verbose)
f_val = p.get_values(f, convert=bool, tolerance=integrality_tolerance)
tsp = [Graph() for i in range(UB)]
for i in range(UB):
tsp[i].add_vertices(g.vertex_iterator())
tsp[i].set_pos(g.get_pos())
for (e, i), b in f_val.items():
if b:
tsp[i].add_edge(e)
return tsp
except MIPSolverException:
UB -= 1
if not UB:
raise EmptySetError("the given graph is not Hamiltonian")
</code></pre>
<p>You get:</p>
<pre><code>sage: G = graphs.CompleteGraph(5)
sage: T = disjoint_hamiltonian_cycles(G)
sage: T
[Graph on 5 vertices, Graph on 5 vertices]
sage: [t.edges(labels=False, sort=True) for t in T]
[[(0, 1), (0, 3), (1, 4), (2, 3), (2, 4)],
[(0, 2), (0, 4), (1, 2), (1, 3), (3, 4)]]
sage: G = graphs.CompleteGraph(7)
sage: T = disjoint_hamiltonian_cycles(G)
sage: [t.edges(labels=False, sort=True) for t in T]
[[(0, 1), (0, 4), (1, 6), (2, 3), (2, 5), (3, 6), (4, 5)],
[(0, 2), (0, 5), (1, 3), (1, 4), (2, 6), (3, 5), (4, 6)],
[(0, 3), (0, 6), (1, 2), (1, 5), (2, 4), (3, 4), (5, 6)]]
</code></pre>
https://ask.sagemath.org/question/65157/number-of-disjoint-hamiltonian-cycles-in-a-graph/?comment=65212#post-id-65212Thanks! that is so kind of you! Actually, I wanted just the maximum number of disjoint hamiltonian cycles, but you gave the full construction. Anyways, the `len()` would suffice for my needsSun, 04 Dec 2022 20:01:25 +0100https://ask.sagemath.org/question/65157/number-of-disjoint-hamiltonian-cycles-in-a-graph/?comment=65212#post-id-65212