{"id":20427,"date":"2023-08-18T04:42:03","date_gmt":"2023-08-18T02:42:03","guid":{"rendered":"http:\/\/blog.wenzlaff.de\/?p=20427"},"modified":"2023-08-25T16:59:46","modified_gmt":"2023-08-25T14:59:46","slug":"koenigsberger-brueckenproblem-oder-etwas-graphentheorie-mit-jgrapht-in-java","status":"publish","type":"post","link":"http:\/\/blog.wenzlaff.de\/?p=20427","title":{"rendered":"K\u00f6nigsberger Br\u00fcckenproblem oder etwas Graphentheorie mit jgrapht in Java"},"content":{"rendered":"

Das K\u00f6nigsberger<\/a> Br\u00fcckenproblem<\/a> ist eine klassische mathematische Herausforderung, die im 18. Jahrhundert entstand und einen wichtigen Einfluss auf die Entwicklung der Graphentheorie hatte. Es handelt sich um eine Fragestellung bez\u00fcglich der \u00dcberquerung von Br\u00fccken \u00fcber den Fl\u00fcssen Pregel und seinen Inseln in der Stadt K\u00f6nigsberg (heute Kaliningrad, Russland). Das Problem wurde erstmals von dem Schweizer Mathematiker Leonhard Euler im Jahr 1735 gel\u00f6st und legte den Grundstein f\u00fcr die moderne Graphentheorie.<\/p>\n

In K\u00f6nigsberg gab es sieben Br\u00fccken<\/a>, die die Fl\u00fcsse Pregel und die beiden Inseln verbunden haben. Die Frage war, ob es m\u00f6glich war, die Stadt zu durchqueren, indem man jede Br\u00fccke nur einmal \u00fcberquerte und schlie\u00dflich an einem beliebigen Punkt endete.<\/p>\n

\"\"<\/p>\n

Euler bewies, dass es keine<\/strong> M\u00f6glichkeit gibt, das K\u00f6nigsberger Br\u00fcckenproblem zu l\u00f6sen. Er zeigte, dass mindestens zwei der vier Landpunkte eine ungerade Anzahl von Br\u00fccken haben m\u00fcssten, um eine L\u00f6sung unm\u00f6glich zu machen. Dies f\u00fchrte zur Entwicklung der Graphentheorie, bei der das Problem als ein Graph dargestellt werden kann, wobei die Landpunkte die Knoten und die Br\u00fccken die Kanten des Graphen sind.<\/p>\n

Da kommt nun die Implementierung mit JGraphT<\/a> in Java ins Spiel.<\/p>\n

JGraphT<\/a> ist eine Java-Bibliothek, die es erm\u00f6glicht, Graphen einfach zu erstellen, zu manipulieren und zu analysieren. <\/p>\n

Hier ist ein Beispiel, wie das K\u00f6nigsberger Br\u00fcckenproblem mit JGraphT in Java implementiert werden kann.<\/p>\n

Zuerst m\u00fcssen Sie die JGraphT-Bibliothek zu Ihrem Projekt hinzuf\u00fcgen. Dies kann normalerweise durch das Hinzuf\u00fcgen einer Abh\u00e4ngigkeit in Ihrer Build-Datei (z.B. Maven pom.xml) erfolgen.<\/p>\n

\r\n                <dependency>\r\n\t\t\t<groupId>org.jgrapht<\/groupId>\r\n\t\t\t<artifactId>jgrapht-core<\/artifactId>\r\n\t\t\t<version>1.5.2<\/version>\r\n\t\t<\/dependency>\r\n\t\t<dependency>\r\n\t\t\t<groupId>org.jgrapht<\/groupId>\r\n\t\t\t<artifactId>jgrapht-ext<\/artifactId>\r\n\t\t\t<version>1.5.2<\/version>\r\n\t\t<\/dependency>\r\n\t\t<dependency>\r\n\t\t\t<groupId>com.github.vlsi.mxgraph<\/groupId>\r\n\t\t\t<artifactId>jgraphx<\/artifactId>\r\n\t\t\t<version>4.2.2<\/version>\r\n\t\t<\/dependency>\r\n\t\t<dependency>\r\n\t\t\t<groupId>org.jgrapht<\/groupId>\r\n\t\t\t<artifactId>jgrapht-io<\/artifactId>\r\n\t\t\t<version>1.5.2<\/version>\r\n\t\t<\/dependency>\r\n<\/pre>\n
Dann k\u00f6nnen wir in Java den ungerichteten Graphen mit der Multigraph Klasse erzeugen:<\/p>\n
\r\n\r\n                \/\/ Erstelle einen ungerichteten Graphen mit Multiple edges\r\n\t\tgraph = new DefaultListenableGraph<>(new Multigraph<>(DefaultEdge.class));\r\n\r\n\t\t\/\/ F\u00fcge 4 Knoten (Landpunkte) zum Graphen hinzu\r\n\t\tgraph.addVertex(\"A\");\r\n\t\tgraph.addVertex(\"B\");\r\n\t\tgraph.addVertex(\"C\");\r\n\t\tgraph.addVertex(\"D\");\r\n\r\n\t\t\/\/ F\u00fcge 7 Kanten (Br\u00fccken) zwischen den Knoten hinzu\r\n\t\tgraph.addEdge(\"A\", \"B\");\r\n\t\tgraph.addEdge(\"A\", \"B\");\r\n\t\tgraph.addEdge(\"A\", \"D\");\r\n\t\tgraph.addEdge(\"B\", \"D\");\r\n\t\tgraph.addEdge(\"B\", \"C\");\r\n\t\tgraph.addEdge(\"B\", \"C\");\r\n\t\tgraph.addEdge(\"C\", \"D\");\r\n<\/pre>\n
Wir k\u00f6nnen auch eine dot Datei erzeugen:<\/p>\n
\r\n\r\ngraph G {\r\n  1 [ label=\"A\" style=\"filled\" fillcolor=\"#EEEEEE\" color=\"#31CEF0\" ];\r\n  2 [ label=\"B\" style=\"filled\" fillcolor=\"#EEEEEE\" color=\"#31CEF0\" ];\r\n  3 [ label=\"C\" style=\"filled\" fillcolor=\"#EEEEEE\" color=\"#31CEF0\" ];\r\n  4 [ label=\"D\" style=\"filled\" fillcolor=\"#EEEEEE\" color=\"#31CEF0\" ];\r\n  1 -- 2;\r\n  1 -- 2;\r\n  1 -- 4;\r\n  2 -- 4;\r\n  2 -- 3;\r\n  2 -- 3;\r\n  3 -- 4;\r\n}\r\n<\/pre>\n
Die kann dann leicht mit<\/p>\n
dot<\/a> -T png -o koenigsberger-dot.png $inputDateiname<\/p>\n
in diese Grafik \u00fcbersetzt werden.<\/p>\n
\"\"<\/p>\n
Die Frage war, ob es einen Weg gibt, bei dem man alle sieben Br\u00fccken genau einmal \u00fcberquert, und wenn ja, ob auch ein Rundweg m\u00f6glich ist, bei dem man wieder zum Ausgangspunkt gelangt. Leonhard Euler<\/a> bewies 1736, dass ein solcher Weg bzw. Eulerscher Weg<\/a> in K\u00f6nigsberg nicht m\u00f6glich war, da zu allen vier Ufergebieten bzw. Inseln eine ungerade Zahl von Br\u00fccken f\u00fchrte. Es d\u00fcrfte maximal zwei<\/strong> Ufer (Knoten) mit einer ungeraden Zahl<\/strong> von angeschlossenen Br\u00fccken (Kanten) geben. Diese zweiUfer k\u00f6nnten Ausgangs- bzw. Endpunkt sein. Die restlichen Ufer m\u00fcssten eine gerade Anzahl von Br\u00fccken haben, um sie auch wieder auf einem neuen Weg verlassen zu k\u00f6nnen.<\/p>\n
Durch Kriegseinwirkung und Umbauten nach 1945 ist die urspr\u00fcngliche Situation im heutigen Kaliningrad nicht mehr gegeben. Zwei der zur Insel Kneiphof f\u00fchrenden Br\u00fccken existieren nicht mehr; am n\u00f6rdlichen und s\u00fcdlichen Ufer enden nur noch jeweils zwei anstatt drei Br\u00fccken. Nun ist zwar ein Eulerweg m\u00f6glich, jedoch noch immer kein Eulerkreis.<\/p>\n
Zum \u00fcberpr\u00fcfen des Graph ob er einen „Eulerschen Weg“ erm\u00f6glicht, kann die die HierholzerEulerianCycle<\/strong> Klasse wie folgt aufgerufen werden.<\/p>\n
HierholzerEulerianCycle<Object, DefaultEdge> hier = new HierholzerEulerianCycle<>();\r\nboolean isEulerian = hier.isEulerian(graph);<\/pre>\n
Hier gibt es auch eine sch\u00f6ne Online-Seite<\/a> dazu.<\/p>\n
Das K\u00f6nigsberger Br\u00fcckenproblem hat nicht nur die Graphentheorie beeinflusst, sondern auch dazu beigetragen, die Grundlagen f\u00fcr das Verst\u00e4ndnis von Netzwerken und Verbindungen zu legen. Durch die Verwendung von JGraphT und anderen modernen Technologien k\u00f6nnen wir diese historische mathematische Herausforderung m\u00fchelos in Java implementieren und verstehen, wie graphentheoretische Konzepte auf reale Probleme angewendet werden k\u00f6nnen.<\/p>\n
Das ganze Projekt und auch die JUnit-Test kann von hier geclont<\/a> werden. Auch gibt es dort noch einige Bilder zu dem Thema bzw. Scripte.<\/p>\n
\r\n\r\nIn K\u00f6nigsberg, Stadt am Fluss so klar,\r\nDas Br\u00fcckenproblem war wahrlich rar.\r\nSieben Br\u00fccken f\u00fchrten \u00fcber's Wasser blau,\r\nDie Frage war: \"Wie kommt man auf die andere Au?\"\r\n\r\nLeonhard Euler kam, mit Geist so wach,\r\nEr dachte nach, und ohne Zwang und Drach'.\r\nGraphentheorie, sein Werk so klug,\r\nL\u00f6ste das R\u00e4tsel, mit einem einzigen Zug.\r\n\r\nVier Landpunkte standen, A, B, C und D,\r\nKanten und Knoten, ein kniffliges Gedicht.\r\nDie Br\u00fccken verbanden, mit List und Verstand,\r\nDoch eine Route fand sich nicht im Land.\r\n\r\nDie Graphen halfen, das R\u00e4tsel zu l\u00f6sen,\r\nMit Algorithmen und Wissen, so gro\u00df.\r\nEulerkreis und Konnektivit\u00e4t,\r\nDie Mathematik brachte Klarheit herbei.\r\n\r\nSo bleibt das R\u00e4tsel, in Erinnerung stets,\r\nWie Euler's K\u00f6pfchen das Problem erfasst.\r\nDie sieben Br\u00fccken, ein Denkspiel f\u00fcr die Zeit,\r\nGraphentheorie, im Mittelalter geweiht.\r\n\r\n-Thomas Wenzlaff<\/pre>\n
Hier noch der Graph<\/a>, von dem ganzen Projekt:<\/p>\n
\"\" oder wer es als Video<\/a> sehen will.<\/p>\n","protected":false},"excerpt":{"rendered":"
Das K\u00f6nigsberger Br\u00fcckenproblem ist eine klassische mathematische Herausforderung, die im 18. Jahrhundert entstand und einen wichtigen Einfluss auf die Entwicklung der Graphentheorie hatte. Es handelt sich um eine Fragestellung bez\u00fcglich der \u00dcberquerung von Br\u00fccken \u00fcber den Fl\u00fcssen Pregel und seinen Inseln in der Stadt K\u00f6nigsberg (heute Kaliningrad, Russland). Das Problem wurde erstmals von dem Schweizer … <\/p>\n
\u201eK\u00f6nigsberger Br\u00fcckenproblem oder etwas Graphentheorie mit jgrapht in Java\u201c <\/span>weiterlesen<\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[220,5,5348,79,7],"tags":[5646,5659,1596,5668,5676,5669,5656,5654,5647,1632,5651,5663,5667,5665,5664,5681,5680,5649,5648,5658,5662,5687,5678,5673,2178,5650,5643,5666,5653,5657,5652,5645,5644,5672,5670,5683,5677,5661,1582,5679,2182,5660,5671,5682,5684,5655,5674,5675],"class_list":["post-20427","post","type-post","status-publish","format-standard","hentry","category-anleitung","category-java","category-openais-gpt-4","category-programmierung","category-tools","tag-brueckenproblem","tag-connectivityinspector","tag-dot","tag-euler","tag-eulerkreis","tag-flussproblem","tag-gerichtete-graphen","tag-gewichtete-graphen","tag-graf","tag-graph","tag-graph-algorithmen","tag-graph-datenstrukturen","tag-graph-modellierungswerkzeug","tag-graph-operationen","tag-graph-transformation","tag-graphalgorithmen","tag-graphanalysen","tag-graphenmodellierung","tag-graphentheorie","tag-graphtraversierung","tag-graphvisualisierung","tag-hierholzer","tag-historische-herausforderung","tag-inseln","tag-java","tag-java-bibliothek","tag-jgrapht","tag-jgrapht-bibliothek","tag-kanten","tag-kantengewichtung","tag-knoten","tag-koenigsberger","tag-koenigsberger-brueckenproblem","tag-landpunkte","tag-leonhard-euler","tag-mathematische-loesung","tag-mathematische-raetsel","tag-maxflowmincutalgorithm","tag-netzwerkanalyse","tag-netzwerkproblem","tag-programmierung","tag-shortestpathalgorithm","tag-sieben-bruecken","tag-topologie","tag-ueber-7-bruecken-musst-du-gehen","tag-ungerichtete-graphen","tag-ungerichteter-graph","tag-zusammenhangskomponenten"],"_links":{"self":[{"href":"http:\/\/blog.wenzlaff.de\/index.php?rest_route=\/wp\/v2\/posts\/20427","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/blog.wenzlaff.de\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/blog.wenzlaff.de\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/blog.wenzlaff.de\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/blog.wenzlaff.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=20427"}],"version-history":[{"count":0,"href":"http:\/\/blog.wenzlaff.de\/index.php?rest_route=\/wp\/v2\/posts\/20427\/revisions"}],"wp:attachment":[{"href":"http:\/\/blog.wenzlaff.de\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=20427"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/blog.wenzlaff.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=20427"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/blog.wenzlaff.de\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=20427"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}