Book a Demo!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutPoliciesSign UpSign In
Download
2188 views
Tweet
Share
Share
1
'''

2
This file assumes that the conjecturing spkg and nauty spkg is installed and that 'conjecturing.py' and

3
'graphtheory.py' are loaded.

4
'''

5


6
def automatedGraphSearch(objects, invariants, minimumVertices, maximumVertices, upperBound=True, steps=10, mainInvariant=1, verbose=False):

7
    if verbose:

8
        print("Starting with these objects:")

9
        for g in objects:

10
            print("    {}: {}".format(g, g.graph6_string()))

11
        print("")

12
        print("Available invariants:")

13
        for pos, invariant in enumerate(invariants):

14
            if type(invariant) == tuple:

15
                name, _ = invariant

16
            elif hasattr(invariant, '__name__'):

17
                name = invariant.__name__

18
            else:

19
                name = 'invariant_{}'.format(pos)

20
            if pos + 1 == mainInvariant:

21
                print(" *  {}".format(name))

22
            else:

23
                print("    {}".format(name))

24
        print("")

25
    for _ in range(steps):

26
        l = conjecture(objects, invariants, mainInvariant, upperBound=upperBound)

27
        if verbose:

28
            print("Found the following conjectures:")

29
            for c in l:

30
                print("    {}".format(c))

31
            print("")

32
        noCounterExample = True

33
        for i in range(minimumVertices, maximumVertices+1):

34
            if verbose:

35
                print("Looking for counterexamples with {} {}".format(i, "vertex" if i==1 else "vertices"))

36
            for g in graphs.nauty_geng('-c {}'.format(i)):

37
                if any([not c.evaluate(g) for c in l]):

38
                    print("Adding {}: {}".format(g, g.graph6_string()))

39
                    objects.append(g)

40
                    noCounterExample = False

41
                    break

42
            if not noCounterExample: break

43
        if noCounterExample:

44
            print("No counterexample found")

45
            break

46
    return l

47


48
objects = [graphs.CompleteGraph(3), 

49
           Graph('WxEW?CB?I?_R????_?W?@?OC?AW???O?C??B???G?A?_??R'),

50
           Graph('PKKOGCO?G?gH?@_?_?_?@C?C'),

51
           Graph('T{aAA@?G@?C?C?A??_??_?A??C?@??A??A??')]

52


53
# counterexamples:

54
#

55
# WxEW?CB?I?_R????_?W?@?OC?AW???O?C??B???G?A?_??R  --> dominationNumber(x) <= residue(x) + 1

56
# PKKOGCO?G?gH?@_?_?_?@C?C  --> dominationNumber(x) <= diameter(x) + 1

57
# T{aAA@?G@?C?C?A??_??_?A??C?@??A??A??  --> dominationNumber(x) <= 2*girth(x) + 2

58


59
knownUpperBounds = [matching_number, annihilation_number, fractional_alpha, lovasz_theta, cvetkovic]

60
for bound in knownUpperBounds:

61
    invariants.remove(bound)

62
mainInvariant = invariants.index(dominationNumber)

63


64
conjectures = automatedGraphSearch(objects, invariants, 3, 10, mainInvariant=mainInvariant, steps=100, verbose=True)

65


66
print("The conjectures are stored in the variable conjectures.")

67


68