SharedDay1.sagewsOpen in CoCalc
3+4

7
is_prime(47)

True
is_prime(12345678910987654321)

True
is_prime(1111111111111111111)

True
k3 = graphs.CompleteGraph(3)

k3

Complete graph: Graph on 3 vertices
k3.show()

k3.is_hamiltonian()

True
k3.is_clique??

   File: /ext/sage/sage-8.1/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py
Source:
def is_clique(self, vertices=None, directed_clique=False):
"""
Tests whether a set of vertices is a clique

A clique is a set of vertices such that there is an edge between any two
vertices.

INPUT:

-  vertices - Vertices can be a single vertex or an
iterable container of vertices, e.g. a list, set, graph, file or
numeric array. If not passed, defaults to the entire graph.

-  directed_clique - (default False) If set to
False, only consider the underlying undirected graph. If set to
True and the graph is directed, only return True if all possible
edges in _both_ directions exist.

EXAMPLES::

sage: g = graphs.CompleteGraph(4)
sage: g.is_clique([1,2,3])
True
sage: g.is_clique()
True
sage: h = graphs.CycleGraph(4)
sage: h.is_clique([1,2])
True
sage: h.is_clique([1,2,3])
False
sage: h.is_clique()
False
sage: i = graphs.CompleteGraph(4).to_directed()
sage: i.delete_edge([0,1])
sage: i.is_clique()
True
sage: i.is_clique(directed_clique=True)
False
"""
if directed_clique and self._directed:
subgraph=self.subgraph(vertices, immutable = False)
subgraph.allow_loops(False)
subgraph.allow_multiple_edges(False)
n=subgraph.order()
return subgraph.size()==n*(n-1)
else:
if vertices is None:
subgraph = self
else:
subgraph=self.subgraph(vertices)

if self._directed:
subgraph = subgraph.to_simple()

n=subgraph.order()
return subgraph.size()==n*(n-1)/2


load("conjecturing.py")

propertyBasedConjecture?

File: /home/user/conjecturing.py
Signature : propertyBasedConjecture(objects, properties, mainProperty, time=5, debug=False, verbose=False, sufficient=True, operators=None, theory=None, precomputed=None)
Docstring :
Runs the conjecturing program for properties with the provided
objects, properties and main property. This method requires the
program "expressions" to be in the current working directory of
Sage.

INPUT:

* "objects" - a list of objects about which conjectures should be

* "properties" - a list of functions (callable objects) which
take a single argument and return a boolean value. Each function
should be able to produce a value for each of the elements of
objects.

* "mainProperty" - an integer that is the index of one of the
elements of properties. All conjectures will then be a bound for
the property that corresponds to this index.

* "sufficient" - if given, this boolean value specifies whether
sufficient or necessary conditions for the main property should
be generated. If "True", then sufficient conditions are
generated. If "False", then necessary conditions are generated.
The default value is "True"

* "time" - if given, this integer specifies the number of seconds
before the conjecturing program times out and returns the best
conjectures it has at that point. The default value is 5.

* "theory" - if given, specifies a list of known bounds. If this
is "None", then no known bounds are used. Otherwise each
conjecture will have to be more significant than the conditions
in this list. The default value is "None".

* "operators" - if given, specifies a set of operators that can
be used. If this is "None", then all known operators are used.
Otherwise only the specified operators are used. It is advised to
use the method "allPropertyBasedOperators()" to get a set
containing all operators and then removing the operators which
are not needed. The default value is "None".

* "debug" - if given, this boolean value specifies whether the
output of the program "expressions" to "stderr" is printed. The
default value is "False".

* "verbose" - if given, this boolean value specifies whether the
program "expressions" is ran in verbose mode. Note that this has
nu purpose if "debug" is not also set to "True". The default
value is "False".

EXAMPLES:

A very simple example uses just two properties of integers and
generates sufficient conditions for an integer to be prime based on
the integer 3:

>>> propertyBasedConjecture([3], [is_prime,is_even], 0)
[(~(is_even))->(is_prime)]

We can also generate necessary condition conjectures:

>>> propertyBasedConjecture([3], [is_prime,is_even], 0, sufficient=False)
[(is_prime)->(~(is_even))]

In some cases strange conjectures might be produced or one
conjecture you might be expecting does not show up. In this case
you can use the "debug" and "verbose" option to find out what is
going on behind the scene. By enabling "debug" the program prints
the reason it stopped generating conjectures (time limit, no better
conjectures possible, ...) and gives some statistics about the
number of conjectures it looked at:

>>> propertyBasedConjecture([3], [is_prime,is_even], 0, debug=True)
> Generation process was stopped by the conjecturing heuristic.
> Found 2 unlabeled trees.
> Found 2 labeled trees.
> Found 2 valid expressions.
[(~(is_even))->(is_prime)]

By also enabling "verbose", you can discover which values are
actually given to the program:

>>> propertyBasedConjecture([3], [is_prime,is_even], 0, debug=True, verbose=True)
Using the following command
./expressions -pcv --dalmatian --all-operators --time 5 --invariant-names --output stack --sufficient --allowed-skips 0
>      Invariant  1  Invariant  2
>   1)    TRUE          FALSE
> Generating trees with 0 unary nodes and 0 binary nodes.
> Saving expression
> is_prime <- is_even
> Status: 1 unlabeled tree, 1 labeled tree, 1 expression
> Generating trees with 1 unary node and 0 binary nodes.
> Conjecture is more significant for object 1.
> Saving expression
> is_prime <- ~(is_even)
> Conjecture 2 is more significant for object 1.
> Status: 2 unlabeled trees, 2 labeled trees, 2 expressions
> Generation process was stopped by the conjecturing heuristic.
> Found 2 unlabeled trees.
> Found 2 labeled trees.
> Found 2 valid expressions.
[(~(is_even))->(is_prime)]

#Sample Run 1.
graph_objects = [k3]
properties = [Graph.is_hamiltonian, Graph.is_clique]
property_of_interest = 0

propertyBasedConjecture(graphs, properties, property_of_interest)

[(is_clique)->(is_hamiltonian)]
reset("graphs")

pete = graphs.PetersenGraph()
pete.show()

pete.is_hamiltonian()

False
pete.is_apex

c5 = graphs.CycleGraph(5)
c5.show()

k3_4 = graphs.CompleteBipartiteGraph(3,4)
k3_4.show()

k5_5 = graphs.CompleteBipartiteGraph(5,5)
k5_5.show()

#Observation. (is_clique)->(is_hamiltonian) is True

#Sample Run 2. Add more graphs.
#Sample Run 1.
graph_objects = [k3,pete,c5,k5_5,k3_4]
properties = [Graph.is_hamiltonian, Graph.is_clique, Graph.is_regular,Graph.is_cycle, Graph.is_bipartite]
property_of_interest = 0

propertyBasedConjecture(graph_objects, properties, property_of_interest)

[((is_bipartite)&(is_regular))->(is_hamiltonian), (is_cycle)->(is_hamiltonian)]
#generate all connected graphs on 4 vertices
for g in graphs(4):
if g.is_connected():
g.show()


#test is the first conjecture is true for the connected graphs on 4 vertices
#((is_bipartite)&(is_regular))
#1st approach
#want a counterexample (CE): a connected graph g that is bipartite, regular, and NOT hamiltonian
for g in graphs(4):
if g.is_connected() and g.is_bipartite() and g.is_regular() and not g.is_hamiltonian():
g.show()

#test is the first conjecture is true for the connected graphs on 5 vertices
#((is_bipartite)&(is_regular))
#1st approach
#want a counterexample (CE): a connected graph g that is bipartite, regular, and NOT hamiltonian
for g in graphs(5):
if g.is_connected() and g.is_bipartite() and g.is_regular() and not g.is_hamiltonian():
g.show()

#test is the first conjecture is true for the connected graphs on 6 vertices
#((is_bipartite)&(is_regular))
#1st approach
#want a counterexample (CE): a connected graph g that is bipartite, regular, and NOT hamiltonian
for g in graphs(6):
if g.is_connected() and g.is_bipartite() and g.is_regular() and not g.is_hamiltonian():
g.show()

#2nd way to run a test for all connected graphs on 6 vertices
#note: conjs[0] = ((is_bipartite)&(is_regular))->(is_hamiltonian)
for g in graphs(6):
if g.is_connected():
if conjs[0](g) == False:
g.show()

#2nd way to run a test for all connected graphs on 2 vertices
#note: conjs[0] = ((is_bipartite)&(is_regular))->(is_hamiltonian)
for g in graphs(2):
if g.is_connected():
if conjs[0](g) == False:
g.show()
g.graph6_string()

'A_'
#how to convert from the graph6 string representation back to a useable graph
useable = Graph("A_")
useable.show()

#test is the first conjecture is true for the connected graphs on 7 vertices
#((is_bipartite)&(is_regular))
#1st approach
#want a counterexample (CE): a connected graph g that is bipartite, regular, and NOT hamiltonian
for g in graphs(7):
if g.is_connected() and g.is_bipartite() and g.is_regular() and not g.is_hamiltonian():
g.show()

#test is the first conjecture is true for the connected graphs on 8 vertices
#((is_bipartite)&(is_regular))
#1st approach
#want a counterexample (CE): a connected graph g that is bipartite, regular, and NOT hamiltonian
for g in graphs(8):
if g.is_connected() and g.is_bipartite() and g.is_regular() and not g.is_hamiltonian():
g.show()

#Observation. (is_clique)->(is_hamiltonian) is True

#Sample Run 2 rerun. Add more graphs.
#Sample Run 1.
graph_objects = [k3,pete,c5,k5_5,k3_4]
properties = [Graph.is_hamiltonian, Graph.is_clique, Graph.is_regular,Graph.is_cycle, Graph.is_bipartite]
property_of_interest = 0

conjs = propertyBasedConjecture(graph_objects, properties, property_of_interest)
for c in conjs:
print c

((is_bipartite)&(is_regular))->(is_hamiltonian) (is_cycle)->(is_hamiltonian)
#Observation: #2nd way to run a test for all connected graphs on 6 vertices
#note: conjs[0] = (is_cycle)->(is_hamiltonian) is TRUE

conjs[0]

((is_bipartite)&(is_regular))->(is_hamiltonian)
conjs[0](k3)

True
conjs[0](k2)

False
k2 = graphs.CompleteGraph(2)
k2.show()
k2.size()

1
EH = graphs.EllinghamHorton54Graph()
EH.show()

EH.is_hamiltonian()

False
EH.is_bipartite()

True
EH.degree()

[3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
EH.is_regular()

True
conjs[0](EH)

False
#EH is a CE to ((is_bipartite)&(is_regular))->(is_hamiltonian)
#Sample Run 1.
#Sample Run 3. Add EH graph (Ellingham-Horton-54)

graph_objects = [k3,pete,c5,k5_5,k3_4,EH]
properties = [Graph.is_hamiltonian, Graph.is_clique, Graph.is_regular,Graph.is_cycle, Graph.is_bipartite]
property_of_interest = 0

conjs = propertyBasedConjecture(graph_objects, properties, property_of_interest)
for c in conjs:
print c

(is_cycle)->(is_hamiltonian)
k3.is

#no good conjectures. what should we do?!?!?!
#one idea: add more properties
#the produced conjecture IS sharp for ythe hamiltonian graphs that are cycles
#no conjecture applies to the hamiltonian K5_5 graph
graph_objects = [k3,pete,c5,k5_5,k3_4,EH]

properties = [Graph.is_hamiltonian, Graph.is_clique, Graph.is_regular,Graph.is_cycle,Graph.is_bipartite,Graph.is_chordal,Graph.is_strongly_regular,Graph.is_eulerian]

property_of_interest = 0

conjs = propertyBasedConjecture(graph_objects, properties, property_of_interest)
for c in conjs:
print c


((is_strongly_regular)&(is_bipartite))->(is_hamiltonian) (is_cycle)->(is_hamiltonian)
Graph.is_strongly_regular?

File: /ext/sage/sage-8.1/src/sage/graphs/base/static_dense_graph.pyx
Signature : Graph.is_strongly_regular(g, parameters=False)
Docstring :
Tests whether "self" is strongly regular.

A simple graph G is said to be strongly regular with parameters (n,
k, lambda, mu) if and only if:

* G has n vertices.

* G is k-regular.

* Any two adjacent vertices of G have lambda common
neighbors.

* Any two non-adjacent vertices of G have mu common
neighbors.

By convention, the complete graphs, the graphs with no edges and
the empty graph are not strongly regular.

See https://en.wikipedia.org/wiki/Strongly regular graph

INPUT:

* "parameters" (boolean) -- whether to return the quadruple (n,
k,lambda,mu). If "parameters = False" (default), this method
only returns "True" and "False" answers. If "parameters=True",
the "True" answers are replaced by quadruples (n, k,lambda,mu).
See definition above.

EXAMPLES:

Petersen's graph is strongly regular:

sage: g = graphs.PetersenGraph()
sage: g.is_strongly_regular()
True
sage: g.is_strongly_regular(parameters = True)
(10, 3, 0, 1)

And Clebsch's graph is too:

sage: g = graphs.ClebschGraph()
sage: g.is_strongly_regular()
True
sage: g.is_strongly_regular(parameters = True)
(16, 5, 0, 2)

But Chvatal's graph is not:

sage: g = graphs.ChvatalGraph()
sage: g.is_strongly_regular()
False

Complete graphs are not strongly regular.
(https://trac.sagemath.org/14297)

sage: g = graphs.CompleteGraph(5)
sage: g.is_strongly_regular()
False

Completements of complete graphs are not strongly regular:

sage: g = graphs.CompleteGraph(5).complement()
sage: g.is_strongly_regular()
False

The empty graph is not strongly regular:

sage: g = graphs.EmptyGraph()
sage: g.is_strongly_regular()
False

If the input graph has loops or multiedges an exception is raised:

sage: Graph([(1,1),(2,2)]).is_strongly_regular()
Traceback (most recent call last):
...
ValueError: This method is not known to work on graphs with
loops. Perhaps this method can be updated to handle them, but in the
meantime if you want to use it please disallow loops using
allow_loops().
sage: Graph([(1,2),(1,2)]).is_strongly_regular()
Traceback (most recent call last):
...
ValueError: This method is not known to work on graphs with
multiedges. Perhaps this method can be updated to handle them, but in
the meantime if you want to use it please disallow multiedges using
allow_multiple_edges().