Stellen Sie sich ein elektrisches Netzwerk vor, das als ebener Graph G modelliert ist, wobei jede Kante einen 1Ω-Widerstand darstellt. Wie schnell können wir den genauen effektiven Widerstand zwischen zwei Eckpunkten in G berechnen ? Wie schnell können wir den exakten Strom berechnen, der entlang jeder Kante fließt, wenn wir eine 1-V-Batterie an zwei Eckpunkten in G anbringen?
Kirchhoffs bekannte Spannungs- und Stromgesetze reduzieren dieses Problem auf die Lösung eines linearen Gleichungssystems mit einer Variablen pro Kante. Neuere Ergebnisse - explizit von Klein und Randić (1993) beschrieben, aber in früheren Arbeiten von Doyle und Snell (1984) impliziert - reduzieren das Problem auf die Lösung eines linearen Systems mit einer Variablen pro Scheitelpunkt, die das Potential dieses Knotens darstellt . Die Matrix für dieses lineare System ist die Laplace-Matrix des Graphen.
Entweder kann lineares System genau in lösenden die Zeit nested Dissektion und planar Separatoren mit [ Lipton Rose Tarjan 1979 ]. Ist dies der schnellste bekannte Algorithmus?
Neueste bahnbrechende Ergebnisse von Spielman, Teng und anderen deuten darauf hin, dass das Laplace-System in willkürlichen Graphen ungefähr in nahezu linearer Zeit gelöst werden kann . Siehe [ Koutis Miller Peng 2010 ] für die aktuell beste Laufzeit und diesen erstaunlichen Artikel von Erica Klarreich von der Simons Foundation für einen Überblick auf höchstem Niveau. Aber ich interessiere mich speziell für exakte Algorithmen für planare Graphen.
Nehmen Sie ein Rechenmodell an, das exakte reelle Arithmetik in konstanter Zeit unterstützt.
Antworten:
Mit verschachtelten Dissektionen können Sie sogar ein lineares System (basierend auf einem planaren Graphen) in ) lösenO ( nω--√)
quelle