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
  made.

* "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().