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.Wed, 01 Jul 2020 23:04:48 +0200Adding edges to a graphhttps://ask.sagemath.org/question/52261/adding-edges-to-a-graph/This is my first time using this forum so please let me know if more information is needed
I am trying to some basic conjecture testing, so I'm not too concerned about runtime. I am trying to count graphs which are "maximal triangle-free and 3-colorable", ie triangle-free and 3-colorable, and adding any missing edge breaks one of those 2 properties. But I don't know how to test that property about adding edges to a graph, since I don't know how to add edges to a graph. I'm mainly using the Sage page on undirected graphs. My rudimentary code so far is below:
> n = 5
> list = []
> for i in range(1, n):
> list.append([])
> for g in graphs(i):
> if g.is_triangle_free() and g.chromatic_number() <= 3:
> list[i-1].append(g)
listMon, 29 Jun 2020 20:55:59 +0200https://ask.sagemath.org/question/52261/adding-edges-to-a-graph/Comment by FrédéricC for <p>This is my first time using this forum so please let me know if more information is needed</p>
<p>I am trying to some basic conjecture testing, so I'm not too concerned about runtime. I am trying to count graphs which are "maximal triangle-free and 3-colorable", ie triangle-free and 3-colorable, and adding any missing edge breaks one of those 2 properties. But I don't know how to test that property about adding edges to a graph, since I don't know how to add edges to a graph. I'm mainly using the Sage page on undirected graphs. My rudimentary code so far is below: </p>
<pre><code>> n = 5
> list = []
> for i in range(1, n):
> list.append([])
> for g in graphs(i):
> if g.is_triangle_free() and g.chromatic_number() <= 3:
> list[i-1].append(g)
</code></pre>
<p>list</p>
https://ask.sagemath.org/question/52261/adding-edges-to-a-graph/?comment=52282#post-id-52282Like this
sage: G = Graph()
sage: G.add_edge((1,2))
sage: G
Graph on 2 verticesWed, 01 Jul 2020 12:55:23 +0200https://ask.sagemath.org/question/52261/adding-edges-to-a-graph/?comment=52282#post-id-52282Answer by tmonteil for <p>This is my first time using this forum so please let me know if more information is needed</p>
<p>I am trying to some basic conjecture testing, so I'm not too concerned about runtime. I am trying to count graphs which are "maximal triangle-free and 3-colorable", ie triangle-free and 3-colorable, and adding any missing edge breaks one of those 2 properties. But I don't know how to test that property about adding edges to a graph, since I don't know how to add edges to a graph. I'm mainly using the Sage page on undirected graphs. My rudimentary code so far is below: </p>
<pre><code>> n = 5
> list = []
> for i in range(1, n):
> list.append([])
> for g in graphs(i):
> if g.is_triangle_free() and g.chromatic_number() <= 3:
> list[i-1].append(g)
</code></pre>
<p>list</p>
https://ask.sagemath.org/question/52261/adding-edges-to-a-graph/?answer=52284#post-id-52284Your loop `for g in graphs(i):` iterates over all graphs of size `i`, which is a big waste of time. The `graphs()` generator works by adding edges, so if a property P is stable by edge removal, then it can serve as a filter *during* the generation (not after) : if some graphs does not satifsy P, then its "descendance" in the generation tree is not explored.
Here, the property P is "being triangle-free and having chromatic number at most 3", which is stable by edge removal.
Hence `graphs(n, property=lambda g : g.is_triangle_free() and g.chromatic_number() <= 3)` will generate all graphs of size `n` with that property, see `graphs?` for more details.
So, here is a possible way to construct the maximal graphs you are looking for:
def maximal_graphs(n):
mg = []
for G in graphs(n, property=lambda g : g.is_triangle_free() and g.chromatic_number() <= 3):
maximal=True
for e in G.complement().edges():
H = copy(G)
H.add_edge(e)
if H.is_triangle_free() and H.chromatic_number() <= 3:
maximal=False
break
if maximal:
mg.append(G)
return mg
You can use that function to count the graphs you ar looking for:
sage: L = [len(maximal_graphs(n)) for n in range(3,11)] ; L
[1, 2, 3, 4, 6, 10, 16, 31]
You can then search in the OEIS, in case something is known about such sequence:
sage: oeis(L)
0: A216783: Number of maximal triangle-free graphs with n vertices.
sage: s = _[0]
sage: s.first_terms()
(1, 1, 1, 2, 3, 4, 6, 10, 16, 31, 61, 147, 392, 1274, 5036, 25617, 164796, 1337848, 13734745, 178587364, 2911304940, 58919069858, 1474647067521, 45599075629687)
Unfortunately, the next term differs:
sage: len(maximal_graphs(11))
60
So, for graphs with 11 vertices, being maximal triangle-free is not equivalent to being maximal triangle-free and 3-colorable.
You can see the following answers to get more details about generation of graphs satisfying an hereditary property:
- https://ask.sagemath.org/question/33384/using-a-lambda-expression-in-digraphs-fails-for-lengsinks/
- https://ask.sagemath.org/question/24199/why-the-function-graphs-cant-generate-graphs/Wed, 01 Jul 2020 17:49:15 +0200https://ask.sagemath.org/question/52261/adding-edges-to-a-graph/?answer=52284#post-id-52284Comment by bottled-caps for <p>Your loop <code>for g in graphs(i):</code> iterates over all graphs of size <code>i</code>, which is a big waste of time. The <code>graphs()</code> generator works by adding edges, so if a property P is stable by edge removal, then it can serve as a filter <em>during</em> the generation (not after) : if some graphs does not satifsy P, then its "descendance" in the generation tree is not explored.</p>
<p>Here, the property P is "being triangle-free and having chromatic number at most 3", which is stable by edge removal.</p>
<p>Hence <code>graphs(n, property=lambda g : g.is_triangle_free() and g.chromatic_number() <= 3)</code> will generate all graphs of size <code>n</code> with that property, see <code>graphs?</code> for more details.</p>
<p>So, here is a possible way to construct the maximal graphs you are looking for:</p>
<pre><code>def maximal_graphs(n):
mg = []
for G in graphs(n, property=lambda g : g.is_triangle_free() and g.chromatic_number() <= 3):
maximal=True
for e in G.complement().edges():
H = copy(G)
H.add_edge(e)
if H.is_triangle_free() and H.chromatic_number() <= 3:
maximal=False
break
if maximal:
mg.append(G)
return mg
</code></pre>
<p>You can use that function to count the graphs you ar looking for:</p>
<pre><code>sage: L = [len(maximal_graphs(n)) for n in range(3,11)] ; L
[1, 2, 3, 4, 6, 10, 16, 31]
</code></pre>
<p>You can then search in the OEIS, in case something is known about such sequence:</p>
<pre><code>sage: oeis(L)
0: A216783: Number of maximal triangle-free graphs with n vertices.
sage: s = _[0]
sage: s.first_terms()
(1, 1, 1, 2, 3, 4, 6, 10, 16, 31, 61, 147, 392, 1274, 5036, 25617, 164796, 1337848, 13734745, 178587364, 2911304940, 58919069858, 1474647067521, 45599075629687)
</code></pre>
<p>Unfortunately, the next term differs:</p>
<pre><code>sage: len(maximal_graphs(11))
60
</code></pre>
<p>So, for graphs with 11 vertices, being maximal triangle-free is not equivalent to being maximal triangle-free and 3-colorable.</p>
<p>You can see the following answers to get more details about generation of graphs satisfying an hereditary property:</p>
<ul>
<li><a href="https://ask.sagemath.org/question/33384/using-a-lambda-expression-in-digraphs-fails-for-lengsinks/">https://ask.sagemath.org/question/333...</a></li>
<li><a href="https://ask.sagemath.org/question/24199/why-the-function-graphs-cant-generate-graphs/">https://ask.sagemath.org/question/241...</a></li>
</ul>
https://ask.sagemath.org/question/52261/adding-edges-to-a-graph/?comment=52287#post-id-52287wow this exactly anticipates what I was going to do next, thanks so much for the thorough answer!Wed, 01 Jul 2020 20:11:40 +0200https://ask.sagemath.org/question/52261/adding-edges-to-a-graph/?comment=52287#post-id-52287Comment by tmonteil for <p>Your loop <code>for g in graphs(i):</code> iterates over all graphs of size <code>i</code>, which is a big waste of time. The <code>graphs()</code> generator works by adding edges, so if a property P is stable by edge removal, then it can serve as a filter <em>during</em> the generation (not after) : if some graphs does not satifsy P, then its "descendance" in the generation tree is not explored.</p>
<p>Here, the property P is "being triangle-free and having chromatic number at most 3", which is stable by edge removal.</p>
<p>Hence <code>graphs(n, property=lambda g : g.is_triangle_free() and g.chromatic_number() <= 3)</code> will generate all graphs of size <code>n</code> with that property, see <code>graphs?</code> for more details.</p>
<p>So, here is a possible way to construct the maximal graphs you are looking for:</p>
<pre><code>def maximal_graphs(n):
mg = []
for G in graphs(n, property=lambda g : g.is_triangle_free() and g.chromatic_number() <= 3):
maximal=True
for e in G.complement().edges():
H = copy(G)
H.add_edge(e)
if H.is_triangle_free() and H.chromatic_number() <= 3:
maximal=False
break
if maximal:
mg.append(G)
return mg
</code></pre>
<p>You can use that function to count the graphs you ar looking for:</p>
<pre><code>sage: L = [len(maximal_graphs(n)) for n in range(3,11)] ; L
[1, 2, 3, 4, 6, 10, 16, 31]
</code></pre>
<p>You can then search in the OEIS, in case something is known about such sequence:</p>
<pre><code>sage: oeis(L)
0: A216783: Number of maximal triangle-free graphs with n vertices.
sage: s = _[0]
sage: s.first_terms()
(1, 1, 1, 2, 3, 4, 6, 10, 16, 31, 61, 147, 392, 1274, 5036, 25617, 164796, 1337848, 13734745, 178587364, 2911304940, 58919069858, 1474647067521, 45599075629687)
</code></pre>
<p>Unfortunately, the next term differs:</p>
<pre><code>sage: len(maximal_graphs(11))
60
</code></pre>
<p>So, for graphs with 11 vertices, being maximal triangle-free is not equivalent to being maximal triangle-free and 3-colorable.</p>
<p>You can see the following answers to get more details about generation of graphs satisfying an hereditary property:</p>
<ul>
<li><a href="https://ask.sagemath.org/question/33384/using-a-lambda-expression-in-digraphs-fails-for-lengsinks/">https://ask.sagemath.org/question/333...</a></li>
<li><a href="https://ask.sagemath.org/question/24199/why-the-function-graphs-cant-generate-graphs/">https://ask.sagemath.org/question/241...</a></li>
</ul>
https://ask.sagemath.org/question/52261/adding-edges-to-a-graph/?comment=52290#post-id-52290.^_^ .Wed, 01 Jul 2020 23:04:48 +0200https://ask.sagemath.org/question/52261/adding-edges-to-a-graph/?comment=52290#post-id-52290