Ein polynomialer Alogrithmus zur Erkennung der Isomorphie von Graphen

Doktorarbeit / Dissertation aus dem Jahr 2002 im Fachbereich Informatik - Theoretische Informatik, Note: 1,7, Universit?t Potsdam, Sprache: Deutsch, Abstract: Zusammenfassung: Die vorliegende Arbeit zeigt eine M?glichkeit, die lsomorphie zweier Graphen in polynomialer Zeit nachzuweisen. Die Korrektheit des vorgestellten Algorithmus wird nicht bewiesen, aber es wird eine Reihe von Plausibilit?ten aufgelistet, die eine Korrektheit sehr wahrscheinlich erscheinen l?sst. Kern des Algorithmus ist die Venrvendung der neu eingef?hrten Graphkantenprodukte und Hankematrizen. Ein Vorgang, der "Reinigung" genannt wird, visualisiert eine Hankematrix in einem Graphkantenprodukt. Die Zahl der Schritte bei der Reinigung erfolgt in polynomial vielen Schritten und es wird vermutet, dass allein die Existenz einer Hankematrix in einem Graphkantenprodukt auf die lsomorphie der Graphen schliessen l?sst. lm Anhang werden Hinweise f?r die lmplementierung eines solchen Algorithmus und f?r m?gliche verwandte Anwendungen wie Teilgraphensuche gegeben. Summary: We can see here, how the isomorphy of two graphs may be shown by an algorithm, which works in polynomial time. lt is not proved, that this algorithm works correctly. However, there are shown some ideas, which let us assume that the algorithm is correct. In the kernel of the algorithm we use a tool named "Graphkantenprodukt" i.e. product of edges and "Hankematrix", which is a new construction (specially for the present paper). An algorithm named "Reiniguf, g", i.e. cleaning, Shows a Hankematrix within a Graphkantenprodukt. The number of steps for "Reinigung" is equal to a polynome above o, the number of nodes of one of the graphs. The central conjecture in this, paper is: A Hankematrix in a Graphkantenprodukt means, that the graphs are isomorphic. In the attachments of this paper clues are given on to how to implement a computer program as well as how to find subgraphs.

Author: Gisbert Rostock

Publisher: Grin Verlag

Publication Date: Jul 30, 2008

Number of Pages: 72 pages

Binding: Paperback or Softback

ISBN-10: 3640115007

ISBN-13: 9783640115006