Grin logo
en de es fr
Shop
GRIN Website
Publish your texts - enjoy our full service for authors
Go to shop › Computer Science - Theory

Ein polynomialer Alogrithmus zur Erkennung der Isomorphie von Graphen

Title: Ein polynomialer Alogrithmus zur Erkennung der Isomorphie von Graphen

Doctoral Thesis / Dissertation , 2002 , 65 Pages , Grade: 1,7

Autor:in: Gisbert Rostock (Author)

Computer Science - Theory
Excerpt & Details   Look inside the ebook
Summary Details

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.

Details

Title
Ein polynomialer Alogrithmus zur Erkennung der Isomorphie von Graphen
College
University of Potsdam
Grade
1,7
Author
Gisbert Rostock (Author)
Publication Year
2002
Pages
65
Catalog Number
V112718
ISBN (eBook)
9783640110469
ISBN (Book)
9783640115006
Language
German
Tags
Alogrithmus Erkennung Isomorphie Graphen
Product Safety
GRIN Publishing GmbH
Quote paper
Gisbert Rostock (Author), 2002, Ein polynomialer Alogrithmus zur Erkennung der Isomorphie von Graphen, Munich, GRIN Verlag, https://www.grin.com/document/112718
Look inside the ebook
  • Depending on your browser, you might see this message in place of the failed image.
  • https://cdn.openpublishing.com/images/brand/1/preview_popup_advertising.jpg
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
Excerpt from  65  pages
Grin logo
  • Grin.com
  • Payment & Shipping
  • Contact
  • Privacy
  • Terms
  • Imprint