Citation
Adamatzky, A. (2003), "KBGRAPH: How to manage mathematical zoo", Kybernetes, Vol. 32 No. 4. https://doi.org/10.1108/k.2003.06732dad.001
Publisher
:Emerald Group Publishing Limited
Copyright © 2003, MCB UP Limited
KBGRAPH: How to manage mathematical zoo
Software report
KBGRAPH: How to manage mathematical zoo
The term “mathematical zoo”, coined by the mathematician E. Hecke in 1937, denotes a bulk of mathematical knowledge, which belongs to a specific field of mathematics; is rather homogeneous with each element belonging to one of a small number of patterns; all elements of the bulk are independent. The number of entries in the mathematical zoo may exceed the capacity of human memory, which makes it difficult to check all entries for their contribution to a given problem. Therefore, a computerised administration and utilisation becomes actual.
The knowledge-based system KBGRAPH offers assistance in analysing a class of graphs – finite undirected graphs, without loops, multiple edges, or isolated vertices (Gernert, 1989). The main purpose of the system is to support or to simplify proofs of undecided graph-theoretic conjectures. The KBGRAPH is based on a collection of more than 1,500 theorems from graph theory, including conditional and unconditional equations and inequalities between graph-theoretic variables. The properties of a class of graphs, as defined by the user, are matched with all entries in the knowledge base. In this way, new properties of the given class may be found. To simplify proofs of the conjectures the user inputs hypothetical counter examples and the program discovers further properties of the class of such counter examples. In many cases, proofs of a claim are found under additional assumptions, for e.g. planar graphs, toroidal graphs, regular graphs, etc. The KBGRAPH finds values for certain graph invariants, lower and/or upper bounds for other graph invariants, and other restrictions in the form of inequalities to be fulfilled by the invariants.
After the end of an inference process it is possible to display a derivation tree for each single result, such that all findings can be rewritten in the traditional mathematical style. By replacing the knowledge base by a different, however similarly-structured one the system can be transformed into a general database system of mathematical theorems, applicable outside graph theory (Gernert, 1989) and capable of handling another mathematical zoo.
An application of KBGARPH studies of properties of minimally imperfect graphs is discussed in Gernert (1997).
For further information please contact: Professor Dieter Gernert, TU München, Arcisstr. 21, D-80333 München, Germany.E-mail: t4141ax@mail.lrz-muenchen.de
Andrew AdamatzkyCEMS, UWE, BristolSoftware Reviews Editor
References
Gernert, D. (1989), “A knowledge-based system for graph theory”, Methods of Operations Research, Vol. 63, pp. 457-64.
Gernert, D. (1997), “A survey of the strong perfect graph conjecture and some recent results”, Graph Theory Notes of New York, Vol. 31, pp. 25-9.