Sie sind hier
E-Book

Ein polynomialer Alogrithmus zur Erkennung der Isomorphie von Graphen

AutorGisbert Rostock
VerlagGRIN Verlag
Erscheinungsjahr2008
Seitenanzahl65 Seiten
ISBN9783640110469
FormatPDF
Kopierschutzkein Kopierschutz
GerätePC/MAC/eReader/Tablet
Preis29,99 EUR
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.

Kaufen Sie hier:

Horizontale Tabs

Blick ins Buch

Weitere E-Books zum Thema: Sonstiges IT

Citrix Presentation Server

E-Book Citrix Presentation Server
Format: PDF

Der Citrix MetaFrame Presentation Server ist unangefochtener Marktführer unter den Terminalservern für Windows-Systeme. Unternehmen setzen ihn ein, um die Systemverwaltung von Windows-Netzwerken…

Citrix Presentation Server

E-Book Citrix Presentation Server
Format: PDF

Der Citrix MetaFrame Presentation Server ist unangefochtener Marktführer unter den Terminalservern für Windows-Systeme. Unternehmen setzen ihn ein, um die Systemverwaltung von Windows-Netzwerken…

Home Networking

E-Book Home Networking
Format: PDF

Home Networking - das bedeutet die Verbindung der unterschiedlichsten im Haushalt vorhandenen elektronischen Geräte, sei es per Kabel oder drahtlos per Funk. Das beginnt meist mit der Vernetzung von…

Weitere Zeitschriften

Bibel für heute

Bibel für heute

BIBEL FÜR HEUTE ist die Bibellese für alle, die die tägliche Routine durchbrechen wollen: Um sich intensiver mit einem Bibeltext zu beschäftigen. Um beim Bibel lesen Einblicke in Gottes ...

Deutsche Hockey Zeitung

Deutsche Hockey Zeitung

Informiert über das nationale und internationale Hockey. Die Deutsche Hockeyzeitung ist Ihr kompetenter Partner für Ihren Auftritt im Hockeymarkt. Sie ist die einzige bundesweite Hockeyzeitung ...

FileMaker Magazin

FileMaker Magazin

Das unabhängige Magazin für Anwender und Entwickler, die mit dem Datenbankprogramm Claris FileMaker Pro arbeiten. In jeder Ausgabe finden Sie von kompletten Lösungsschritten bis zu ...