![\"\"](\"http:\/\/blog.wenzlaff.de\/wp-content\/uploads\/2023\/08\/hausvomnikolaus-circo.png\")
<\/p>\n<\/p>\n
Das „Haus vom Nikolaus<\/a>„, ein einfaches geometrisches Muster aus f\u00fcnf Linien, das die Form eines stilisierten Hauses darstellt, mag auf den ersten Blick wie eine unschuldige Kindermalerei wirken. Doch hinter diesem scheinbar simplen Muster verbirgt sich eine faszinierende Verbindung zur Graphentheorie, einem Teilgebiet der Mathematik, das sich mit den Eigenschaften und Beziehungen von Graphen besch\u00e4ftigt. Dann mal los, und ein kleines Java Programm dazu.<\/p>\n Was ist das „Haus vom Nikolaus“?<\/strong><\/p>\n Das „Haus vom Nikolaus“ ist eine Zeichnung, die aus f\u00fcnf Strichen besteht und die Form eines stilisierten Hauses zeigt. Es besteht aus einem Quadrat als Basis, einem Dreieck als Dach und einem rechteckigen Schornstein oben auf dem Dach. Es ist benannt nach dem „Nikolaus, dem Schutzpatron der Kinder“, da es oft von Kindern gezeichnet wird.<\/p>\n Graphentheorie und das „Haus vom Nikolaus“<\/strong><\/p>\n Die Verbindung zwischen dem „Haus vom Nikolaus“ und der Graphentheorie liegt in der M\u00f6glichkeit, die Zeichnung als Graphen darzustellen. Ein Graph in der Mathematik besteht aus Knoten (auch als Ecken oder Punkte bezeichnet) und Kanten (auch als Linien oder Verbindungen bezeichnet), die die Beziehungen zwischen den Knoten repr\u00e4sentieren. In diesem Zusammenhang k\u00f6nnen die Ecken des „Hauses vom Nikolaus“ als Knoten betrachtet werden, w\u00e4hrend die Linien zwischen den Ecken die Kanten darstellen. Wie oben oder hier als gerichteter Graph:<\/p>\n Die Bedeutung der „Haus vom Nikolaus“-Graphen<\/strong><\/p>\n Der „Haus vom Nikolaus“-Graph ist ein Beispiel f\u00fcr einen nicht-planaren Graphen. Ein planarer Graph ist ein Graph, der so auf einer Ebene gezeichnet werden kann, dass sich keine seiner Kanten \u00fcberschneiden. Der „Haus vom Nikolaus“-Graph kann jedoch nicht ohne Kanten\u00fcberschneidungen auf eine Ebene gezeichnet werden, was ihn zu einem klassischen Beispiel f\u00fcr einen nicht-planaren Graphen macht.<\/p>\n Ein Graph G ist ein Tupel (V,E), wobei V eine Menge von Knoten (englisch vertex, oft auch Ecken genannt) und E eine Menge von Kanten (engl. edge, manchmal auch B\u00f6gen genannt) bezeichnet.<\/p>\n In der Graphentheorie gibt es den ber\u00fchmten Satz von dem polnischen Mathematiker Kuratowski<\/a>, der besagt, dass ein Graph genau dann nicht-planar ist, wenn er einen Teilgraphen enth\u00e4lt, der homomorph zu einem „Haus vom Nikolaus“-Graphen ist. Das bedeutet, dass das „Haus vom Nikolaus“ eine wichtige Rolle in der Untersuchung von nicht-planaren Graphen spielt und als Beispiel dient, um verschiedene Konzepte und Eigenschaften von Graphen zu veranschaulichen.<\/p>\n Das „Haus vom Nikolaus“ mag auf den ersten Blick wie eine einfache Kindermalerei aussehen, aber es hat eine tiefere Bedeutung in der Welt der Graphentheorie. Es veranschaulicht die Idee von nicht-planaren Graphen und bietet ein anschauliches Beispiel f\u00fcr den ber\u00fchmten Satz von Kuratowski. Dieses scheinbar unschuldige Muster ist ein hervorragendes Beispiel daf\u00fcr, wie abstrakte mathematische Konzepte in visuellen Darstellungen veranschaulicht werden k\u00f6nnen, um komplexe Ideen zu vermitteln.<\/p>\n Dann mal hier ein Beispiel in Java und mit jGrapht<\/a>:<\/p>\n Und eine Testklasse dazu:<\/p>\n Wer noch ein Template f\u00fcr Graphviz<\/a> braucht:<\/p>\n Nun fehlt noch ein kleines Programm, um alle 88 M\u00f6glichkeiten zu erzeugen. Der ganze Quellcode ist auf GitLab<\/a>. Aber nicht mehr heute …<\/p>\n","protected":false},"excerpt":{"rendered":" Das „Haus vom Nikolaus„, ein einfaches geometrisches Muster aus f\u00fcnf Linien, das die Form eines stilisierten Hauses darstellt, mag auf den ersten Blick wie eine unschuldige Kindermalerei wirken. Doch hinter diesem scheinbar simplen Muster verbirgt sich eine faszinierende Verbindung zur Graphentheorie, einem Teilgebiet der Mathematik, das sich mit den Eigenschaften und Beziehungen von Graphen besch\u00e4ftigt. … <\/p>\n![\"\"](\"http:\/\/blog.wenzlaff.de\/wp-content\/uploads\/2023\/08\/hausvomnikolaus-dot.png\")
<\/p>\npackage de.wenzlaff.twgraph;\r\n\r\nimport java.util.ArrayList;\r\nimport java.util.List;\r\n\r\nimport org.apache.logging.log4j.LogManager;\r\nimport org.apache.logging.log4j.Logger;\r\nimport org.jgrapht.ListenableGraph;\r\nimport org.jgrapht.alg.cycle.HierholzerEulerianCycle;\r\nimport org.jgrapht.graph.DefaultEdge;\r\nimport org.jgrapht.graph.DefaultListenableGraph;\r\nimport org.jgrapht.graph.SimpleDirectedGraph;\r\nimport org.jgrapht.traverse.DepthFirstIterator;\r\nimport org.jgrapht.traverse.GraphIterator;\r\n\r\n\/**\r\n * Ziel ist es, ein \u201eHaus\u201c in einem Linienzug aus genau acht Strecken zu\r\n * zeichnen, ohne eine Strecke zweimal zu durchlaufen. Begleitet wird das\r\n * Zeichnen mit dem simultan gesprochenen Reim aus acht Silben: \u201eDas ist das\r\n * Haus vom Ni-ko-laus.\u201c\r\n * \r\n * https:\/\/de.wikipedia.org\/wiki\/Haus_vom_Nikolaus\r\n * \r\n * @author Thomas Wenzlaff\r\n *\/\r\npublic class HausVomNikolaus {\r\n\r\n\tprivate static final Logger LOG = LogManager.getLogger(HausVomNikolaus.class);\r\n\r\n\tprivate ListenableGraph<Object, DefaultEdge> graph;\r\n\r\n\tpublic HausVomNikolaus() {\r\n\t\terstelleHausVomNikolausGraph();\r\n\t}\r\n\r\n\tprivate void erstelleHausVomNikolausGraph() {\r\n\r\n\t\t\/\/ Erstelle einen gerichteten Graphen mit SimpleDirectedGraph edges\r\n\t\tgraph = new DefaultListenableGraph<>(new SimpleDirectedGraph<>(DefaultEdge.class));\r\n\r\n\t\t\/\/ F\u00fcge 5 Knoten zum Graphen hinzu\r\n\t\tgraph.addVertex(\"1\");\r\n\t\tgraph.addVertex(\"2\");\r\n\t\tgraph.addVertex(\"3\");\r\n\t\tgraph.addVertex(\"4\");\r\n\t\tgraph.addVertex(\"5\");\r\n\r\n\t\t\/\/ F\u00fcge 8 Kanten = Verbindungsstrecken zwischen den Knoten hinzu\r\n\t\tgraph.addEdge(\"1\", \"2\");\r\n\t\tgraph.addEdge(\"2\", \"4\");\r\n\t\tgraph.addEdge(\"4\", \"3\");\r\n\t\tgraph.addEdge(\"3\", \"5\");\r\n\t\tgraph.addEdge(\"5\", \"4\");\r\n\t\tgraph.addEdge(\"4\", \"1\");\r\n\t\tgraph.addEdge(\"1\", \"3\");\r\n\t\tgraph.addEdge(\"3\", \"2\");\r\n\r\n\t\talleKnotenAusgeben();\r\n\t}\r\n\r\n\tpublic ListenableGraph<Object, DefaultEdge> getGraph() {\r\n\t\treturn graph;\r\n\t}\r\n\r\n\t\/**\r\n\t * Problemgegenstand ist ein Graph, f\u00fcr den ein Eulerweg, aber kein Eulerkreis\r\n\t * existiert, da er zwei Knoten von ungeradem Grad (die Knoten 1 und 2 haben\r\n\t * hier jeweils einen Grad von 3) enth\u00e4lt.\r\n\t * \r\n\t * @return true wenn es ein eulerscher Graph w\u00e4hre, sonst immer false\r\n\t *\/\r\n\tpublic boolean isHausVomNikolausEulerian() {\r\n\r\n\t\tHierholzerEulerianCycle<Object, DefaultEdge> hier = new HierholzerEulerianCycle<>();\r\n\t\tboolean isEulerian = hier.isEulerian(graph); \/\/ eigentlich nur f\u00fcr ungerichtete Graphen, geht in diesem Fall aber so auch\r\n\t\tif (isEulerian) {\r\n\t\t\tLOG.info(\"Das HausVomNikolaus ist ein eulerscher Graph. Das trifft nie zu.\");\r\n\t\t} else {\r\n\t\t\tLOG.info(\"Das HausVomNikolaus f\u00fcr den es ein Eulerweg, aber kein Eulerkreis existiert wenn von 1 oder 2 gestartet wird.\");\r\n\t\t}\r\n\t\treturn isEulerian;\r\n\t}\r\n\r\n\tpublic List<Object> alleKnotenAusgeben() {\r\n\r\n\t\tString startVertex = \"1\"; \/\/ start Knoten\r\n\r\n\t\tGraphIterator<Object, DefaultEdge> it = new DepthFirstIterator<>(graph, startVertex);\r\n\r\n\t\tList<Object> ergebnisKnoten = new ArrayList<>();\r\n\r\n\t\twhile (it.hasNext()) {\r\n\t\t\tergebnisKnoten.add(it.next());\r\n\t\t}\r\n\t\tLOG.info(ergebnisKnoten);\r\n\t\treturn ergebnisKnoten;\r\n\t}\r\n}\r\n<\/pre>\npackage de.wenzlaff.twgraph;\r\n\r\nimport static org.junit.jupiter.api.Assertions.assertFalse;\r\nimport static org.junit.jupiter.api.Assertions.assertNotNull;\r\nimport static org.junit.jupiter.api.Assertions.assertTrue;\r\n\r\nimport java.io.File;\r\n\r\nimport org.apache.logging.log4j.LogManager;\r\nimport org.apache.logging.log4j.Logger;\r\nimport org.jgrapht.ListenableGraph;\r\nimport org.jgrapht.alg.cycle.HierholzerEulerianCycle;\r\nimport org.jgrapht.graph.DefaultEdge;\r\nimport org.jgrapht.graph.DefaultListenableGraph;\r\nimport org.jgrapht.graph.SimpleGraph;\r\nimport org.jgrapht.nio.dot.DOTExporter;\r\nimport org.junit.jupiter.api.Test;\r\n\r\n\/**\r\n * \r\n * @author Thomas Wenzlaff\r\n *\r\n *\/\r\nclass HausVomNikolausTest {\r\n\r\n\tprivate static final Logger LOG = LogManager.getLogger(HausVomNikolausTest.class);\r\n\r\n\t\/** SUT. *\/\r\n\tprivate HausVomNikolaus graph = new HausVomNikolaus();\r\n\r\n\t@Test\r\n\tvoid testHausVomNikoloaus() {\r\n\t\tassertNotNull(graph);\r\n\t}\r\n\r\n\t@Test\r\n\tvoid testIsHausVomNikolausEulerian() {\r\n\r\n\t\tDotExporter dotExp = new DotExporter();\r\n\r\n\t\tassertFalse(graph.isHausVomNikolausEulerian());\r\n\r\n\t\tFile dotFile = new File(\"target\", \"junit-test-hausvomnikolaus.dot\");\r\n\r\n\t\tDOTExporter<Object, DefaultEdge> writeDotFile = dotExp.writeDotFile(graph.getGraph(), dotFile);\r\n\r\n\t\tassertNotNull(writeDotFile);\r\n\t\tassertTrue(dotFile.exists());\r\n\t}\r\n\r\n\t@Test\r\n\tvoid testIsEulerian() {\r\n\r\n\t\t\/\/ https:\/\/de.wikipedia.org\/wiki\/Algorithmus_von_Hierholzer\r\n\t\t\/\/ der in einem ungerichteten Graphen Eulerkreise bestimmt\r\n\t\tHierholzerEulerianCycle<Object, DefaultEdge> hier = new HierholzerEulerianCycle<>();\r\n\t\tboolean isEulerian = hier.isEulerian(getTestEulerGraph());\r\n\r\n\t\tassertTrue(isEulerian);\r\n\t}\r\n\r\n\tprivate ListenableGraph<Object, DefaultEdge> getTestEulerGraph() {\r\n\r\n\t\tListenableGraph<Object, DefaultEdge> eulersGraphQuadrat = new DefaultListenableGraph<>(new SimpleGraph<>(DefaultEdge.class));\r\n\r\n\t\teulersGraphQuadrat.addVertex(\"1\");\r\n\t\teulersGraphQuadrat.addVertex(\"2\");\r\n\t\teulersGraphQuadrat.addVertex(\"3\");\r\n\t\teulersGraphQuadrat.addVertex(\"4\");\r\n\r\n\t\teulersGraphQuadrat.addEdge(\"1\", \"2\");\r\n\t\teulersGraphQuadrat.addEdge(\"2\", \"3\");\r\n\t\teulersGraphQuadrat.addEdge(\"3\", \"4\");\r\n\t\teulersGraphQuadrat.addEdge(\"4\", \"1\");\r\n\r\n\t\treturn eulersGraphQuadrat;\r\n\t}\r\n}\r\n<\/pre>\nstrict digraph G {\r\n 1 [ label=\"1\" style=\"filled\" fillcolor=\"#EEEEEE\" color=\"#31CEF0\" ];\r\n 2 [ label=\"2\" style=\"filled\" fillcolor=\"#EEEEEE\" color=\"#31CEF0\" ];\r\n 3 [ label=\"3\" style=\"filled\" fillcolor=\"#EEEEEE\" color=\"#31CEF0\" ];\r\n 4 [ label=\"4\" style=\"filled\" fillcolor=\"#EEEEEE\" color=\"#31CEF0\" ];\r\n 5 [ label=\"5\" style=\"filled\" fillcolor=\"#EEEEEE\" color=\"#31CEF0\" ];\r\n 1 -> 2;\r\n 2 -> 4;\r\n 4 -> 3;\r\n 3 -> 5;\r\n 5 -> 4;\r\n 4 -> 1;\r\n 1 -> 3;\r\n 3 -> 2;\r\n}\r\n<\/pre>\n