{"id":3520,"date":"2023-08-03T23:48:52","date_gmt":"2023-08-03T21:48:52","guid":{"rendered":"https:\/\/blogs.uni-bremen.de\/scienceblog\/?p=3520"},"modified":"2023-08-03T23:50:11","modified_gmt":"2023-08-03T21:50:11","slug":"die-theorie-der-graphen-ein-grosses-raetsel","status":"publish","type":"post","link":"https:\/\/blogs.uni-bremen.de\/scienceblog\/2023\/08\/03\/die-theorie-der-graphen-ein-grosses-raetsel\/","title":{"rendered":"Die Theorie der Graphen – ein gro\u00dfes R\u00e4tsel?!"},"content":{"rendered":"

von Jona Dirks<\/em><\/p>\n

\"Bestimmt

Bestimmt ein ganz einfaches R\u00e4tsel! Oder vielleicht auch nicht? Quelle: Eigene Graphik und Pixabay<\/p><\/div>\n

Du denkst, Informatiker*innen sitzen den ganzen Tag vor\u2018m Computer und sehen lustige Zahlenreihen \u00fcber den Bildschirm tanzen? Falsch gedacht! F\u00fcr den R\u00e4tselspa\u00df der Graphtheorie gen\u00fcgen erstmal Stift und Papier – oder eine W\u00e4scheleine und ein paar B\u00e4ume.<\/strong><\/p>\n

Vielleicht kennst du das folgende R\u00e4tsel: \u00a0Es gibt drei H\u00e4user und jeweils ein Gas-, Wasser- und Stromwerk. Jedes der H\u00e4user soll an Gas, Wasser und Strom angeschlossen werden. Die Leitungen sollen aber alle auf derselben H\u00f6he gebaut werden, d\u00fcrfen sich also nicht \u00fcberschneiden. Versuche doch einmal selbst, ob du eine L\u00f6sung findest:<\/p>\n

\"R\u00e4tsel:

Abbildung 1 – R\u00e4tsel: Alle H\u00e4user sollen an die Versorger (Gas, Wasser und Strom) angeschlossen werden. Die Leitungen sollen sich dabei aber nicht \u00fcberkreuzen. Wie kann das gelingen? Quelle: Eigene Abbildung<\/p><\/div>\n

Ich bin mir sicher, dass du keine L\u00f6sung gefunden hast. Ich \u00fcbrigens auch nicht. W\u00e4hrend ich das bei mir noch auf meine Einfalt schieben kann, muss das bei dir ja andere Ursachen haben. Also, woran liegt das? Ok, dass ist einfach: Weil es keine L\u00f6sung gibt. Die entscheidende Frage ist doch: Warum gibt es keine L\u00f6sung?<\/p>\n

Um diese Frage zu beantworten, machen wir einen Ausflug in die Graphtheorie. Ein Graph, das ist ein ganz simples Konzept. Er besteht aus Punkten, die \u00fcber Linien miteinander verbunden sind. Wie hier zu sehen:<\/p>\n

\"Beispiele

Abbildung 2 – Beispiele f\u00fcr Graphen. Quelle: Eigene Abbildung<\/p><\/div>\n

Die Punkte nennen wir Knoten und die Linien Kanten.<\/p>\n

Graphen k\u00f6nnen hier an sehr vielen Stellen als Vereinfachung eingesetzt werden. So k\u00f6nnen wir zum Beispiel Bahnh\u00f6fe als Knoten auffassen und Schienenverbindung zwischen diesen Bahnh\u00f6fen als Kanten. Oder alternativ: Fahrradwege und Stra\u00dfen als Kanten und Kreuzungen als Knoten. Auch soziale Beziehungen lassen sich als Graphen ausdr\u00fccken. Knoten k\u00f6nnen dabei f\u00fcr Personen stehen und Kanten zum Beispiel f\u00fcr Freundschaften. Aber auch farbige \u00a0Fl\u00e4chen und deren Ber\u00fchrungen k\u00f6nnen als Knoten und Kanten aufgefasst werden. Graphen sind also vielf\u00e4ltig einsetzbar und stellen eine wichtige Vereinfachung dar, die es sich lohnt genau zu untersuchen.<\/p>\n

\"All

Abbildung 3 – All diese Beispiele k\u00f6nnen durch den gleichen Graphen beschrieben werden. Quelle: Eigene Abbildung<\/p><\/div>\n

Aber nicht alle Graphen sind gleich. Einige haben bestimmte Eigenschaften. An dieser Stelle soll es nun um eine besonders wichtige Eigenschaft gehen: Die sogenannte Planarit\u00e4t. Wir bezeichnen einen Graphen als planar, wenn wir ihn aufzeichnen k\u00f6nnen, ohne dass sich Kanten \u00fcberschneiden [1]. Von den Beispielen oben in Abbildung 2 w\u00e4ren also die ersten beiden Graphen planar.<\/p>\n\n\n\n
Infobox<\/em><\/span><\/p>\n

Mengenschreibweise<\/strong><\/span><\/p>\n

Seit gut einem Jahrhundert ist die Mengenlehre aus der Mathematik nicht mehr wegzudenken. Eine Menge ist eine Ansammlung von Teilen, ohne das diese weiter geordnet sind. Ein Teil kann also nur in einer bestimmten Menge vorkommen oder nicht. Auch Graphen sind in diese spezifische Schreibweise \u00fcbertragen worden. So fassen wir die Knoten und Kanten in je einer Menge zusammen. Sollen Mengen benannt werden, werden h\u00e4ufig gro\u00dfe Buchstaben genommen. Bei den Knoten ist dieses meist V, f\u00fcr das englische Wort \u201eVertices\u201c und bei Kanten E, f\u00fcr das englische Wort \u201eEdges\u201c.<\/span><\/p>\n

Ist, wie in unserem Fall, nur die Anzahl der Teile von Relevanz, so gibt es auch daf\u00fcr spezielle Schreibweisen. Diese sind aber nicht einheitlich, oft werden aber vertikale Striche genommen. Die Anzahl der Knoten wird also mit |V| bezeichnet.<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Nun k\u00f6nnen wir anfangen, in diesen Graphen bestimmte Dinge zu z\u00e4hlen. N\u00e4mlich Knoten, Kanten und Fl\u00e4chen. Machen wir das doch einmal f\u00fcr Graph 2 in Abbildung 2: Relativ einfach lassen sich die 4 Knoten z\u00e4hlen. Mathematisch bezeichnen wir die Knotenanzahl mit |V|. Wir haben hier also |V| = 4. Auch die Kanten lassen sich gut z\u00e4hlen. Mathematisch notieren wir die Kantenanzahl mit |E|. Wir haben also |E| = 6.<\/p>\n

\"\"

Abbildung 4 – Besonders interessant sind die Fl\u00e4chen! Wie viele Fl\u00e4chen besitzt dieser planare Graph? Quelle: Eigene Abbildung<\/p><\/div>\n

Und bei den Fl\u00e4chen? 3 Fl\u00e4chen werden von den Kanten eingeschlossen und aufgepasst – wir m\u00fcssen auch die \u00e4u\u00dfere Fl\u00e4che mitz\u00e4hlen. Also: |F| = 4 Fl\u00e4chen.<\/p>\n

H\u00e4ngen diese Zahlen vielleicht irgendwie zusammen? Nehmen wir die Kanten Anzahl und ziehen die Anzahlder Knoten ab. Danach addieren wir 2 darauf, so erhalten wir die Anzahl der Fl\u00e4chen:<\/p>\n

\u00a0 |E| – |V| + 2 = |F|<\/p>\n

ist<\/p>\n

6 \u2013 4 + 2 = 4<\/p>\n

Zufall? Probieren wir das doch nochmal mit einem anderen Graphen aus:<\/p>\n

\"Best\u00e4tigt

Abbildung 5 – Best\u00e4tigt sich auch bei diesem Graphen der Zusammenhang zwischen Knoten, Kanten und Fl\u00e4chen? Quelle: Eigene Abbildung<\/p><\/div>\n

Hier haben wir |E| = 5, |V| = 4 und |F| = 3. Und auch hier gilt die gleiche Formel wie eben:<\/p>\n

5 \u2013 4 + 2 = 3<\/p>\n

Tats\u00e4chlich gilt dieser Zusammenhang immer bei planaren Graphen, vorausgesetzt, sie sind zusammenh\u00e4ngend [1]. Zusammenh\u00e4ngend hei\u00dft dabei, dass der Graph ein Konstrukt ist und nicht aus zwei verschiedenen Teilen besteht, die gar nicht miteinander zusammen h\u00e4ngen.<\/p>\n

Moment mal, damit das gilt d\u00fcrfen sich also Linien nicht\u00a0 \u00fcberschneiden? Sich nicht \u00fcberschneidende Linien kommen uns doch von unserem R\u00e4tsel bekannt vor!<\/p>\n

Bevor wir uns dem widmen, m\u00fcssen wir uns noch eine Sache \u00fcberlegen: Dass wir uns mit H\u00e4usern und Werken besch\u00e4ftigen, ist komplett egal. Genauso gut k\u00f6nnten wir auch W\u00e4scheleinen zwischen runden und eckigen Balken ziehen:<\/p>\n

\"Dasselbe

Abbildung 6 – Dasselbe in gr\u00fcn. Dieses W\u00e4scheleinen-R\u00e4tsel ist ein vollst\u00e4ndig bipartiter Graph. Quelle: Eigene Abbildung<\/p><\/div>\n

Wichtig ist nur, dass wir zwei verschiedene Mengen haben und diese insgesamt verbinden. Hierbei sprechen wir auch von vollst\u00e4ndigen bipartiten Graphen. \u201eBipartit\u201c, weil wir unsere Knoten in zwei Mengen aufteilen k\u00f6nnen, ohne dass es Kanten innerhalb dieser Mengen gibt. \u201eVollst\u00e4ndig\u201c sagen wir, weil wir alle erlaubten Kanten zwischen zwei Objekten ziehen. Dabei m\u00fcssen wir jedoch beachten, dass Kanten zwischen zwei Objekten verschiedener Mengen verboten sind, damit der Graph bipartit bleibt.<\/p>\n

Jetzt, wo wir das wissen, k\u00f6nnen wir uns mal \u00fcberlegen, wie eine m\u00f6gliche L\u00f6sung aussieht und die entscheidenden Kennzahlen bestimmen. Die Knoten sind einfach, wir k\u00f6nnen sie z\u00e4hlen: Es sind |V| = 6. Bei den Kanten m\u00fcssen wir schon etwas rechnen. Wir haben jeweils 3 Werke und 3 H\u00e4user und, weil wir alle Kombinationen daraus abdecken wollen, gibt es insgesamt 3×3=9 Kanten. Also |E| = 9.<\/p>\n

\"Zur\u00fcck

Abbildung 7 – Zur\u00fcck zu dem H\u00e4user-R\u00e4tsel: Wie viele Knoten, Kanten und Fl\u00e4chen haben wir hier? Quelle: Eigene Abbildung<\/p><\/div>\n

Wie sieht das nun mit den Fl\u00e4chen aus? Hier zu m\u00fcssen wir uns \u00fcberlegen, dass immer zwei Werke und zwei H\u00e4user ein Viereck bilden:<\/p>\n

In diesen Vierecken kann weder etwas drin liegen, was Kontakt nach au\u00dfen hat, noch kann irgendetwas hinein ragen. Wir k\u00f6nnen insgesamt folgende Vierecke bilden:<\/p>\n

\"Alle

Abbildung 8 – Alle m\u00f6glichen Vierecke in unserem Beispiel. Quelle: Eigene Abbildung<\/p><\/div>\n

Wir haben also |F| = 9 Fl\u00e4chen. Setzen wir das nun in die Gleichung ein, sehen wir, dass<\/p>\n

9 \u2013 6 + 2 \u2260<\/strong> 9.<\/p>\n

Also kann es keine L\u00f6sung f\u00fcr das Problem geben.<\/p>\n

Probieren wir das nochmal f\u00fcr ein anderes Beispiel aus. Lassen wir doch ein Werk einfach mal weg:<\/p>\n

\"Neuer

Abbildung 9 – Neuer Versuch: K\u00f6nnen wir das R\u00e4tsel diesmal l\u00f6sen? Quelle: Eigene Abbildung<\/p><\/div>\n

 <\/p>\n

Jetzt haben wir |V| = 5 Knoten. 2×3 also |E| = 6 Kanten und [1,2,a,b] [1,3,a,b] [2,3,a,b] Fl\u00e4chen bzw. gez\u00e4hlt |F| = 3. Die Formel geht hier also wieder auf:<\/p>\n

6 \u2013 5 + 2 = 3<\/p>\n

Und tats\u00e4chlich gibt es auch eine L\u00f6sung:<\/p>\n

\"Tats\u00e4chlich!

Abbildung 10 – Tats\u00e4chlich! Dies ist eine m\u00f6gliche L\u00f6sung. Warum hat es diesmal geklappt? Quelle: Eigene Abbildung<\/p><\/div>\n

 <\/p>\n

Wir konnten hier sehen, dass planare Graphen bestimmte Eigenschaften haben, die f\u00fcr allgemeine Graphen nicht gelten — wie unsere Formel |E| – |V| + 2 = |F|. Das ist aber nat\u00fcrlich nur ein Beispiel, es gibt noch viel, viel mehr, was explizit nur f\u00fcr planare Graphen gilt. Wie wir gesehen haben, verbergen sich hinter Problemen aus der realen Welt nicht selten planare Graphen. Einige derer Eigenschaften sind insbesondere dann interessant, wenn wir diese Graphen mit dem Computer behandeln wollen.<\/p>\n

Betrachten wir Graphen auf dem Computer, tun wir der Einfachhalt halber so, als ob uns nur interessiert, ob ein Graph bestimmte Werte besitzt. Ein einfaches Beispiel w\u00e4re, ob der Graph mehr als n Kanten hat. Dabei kann n jede beliebige ganze Zahl sein. Oder alternativ schaffen wir es, mit dem Einf\u00e4rben von n Knoten daf\u00fcr zu sorgen, dass jede Kante mindestens an einen farbigen Nachbar grenzt. F\u00fcr einige dieser Entscheidungen k\u00f6nnen wir Computerprogramme schreiben, die dieses schnell herausfinden, f\u00fcr manche \u00a0kennen wir nur sehr ineffiziente Programme. Manchmal k\u00f6nnen wir Programme effizienter gestalten, wenn wir wissen, dass der zu untersuchende Graph planar ist (vergleiche [2]).<\/p>\n

Hier setzt meine Masterarbeit an: Es geht darum, f\u00fcr eine bestimmte Art von Entscheidung kombiniert mit einem kleinem n, ein schnelles Programm zu schreiben, dass funktioniert, wenn der Graph planar ist. Diese Arbeit schreibe ich in der Arbeitsgruppe Theoretische Informatik<\/a> am Fachbereich Mathematik und Informatik an der Uni Bremen.<\/p>\n

Quellen<\/strong><\/p>\n

[1] Kaveh, A. (2022).\u00a0 Introduction to Graph Theory and Algebraic Graph Theory. In:\u00a0 Topological Transformations for Efficient Structural Analysis. Springer, Cham<\/p>\n

[2] Flum, J. and Grohe, M. (2006) , Parameterized Complexity Theory. Springer, Berlin<\/p>\n","protected":false},"excerpt":{"rendered":"

von Jona Dirks Du denkst, Informatiker*innen sitzen den ganzen Tag vor\u2018m Computer und sehen lustige Zahlenreihen \u00fcber den Bildschirm tanzen? Falsch gedacht! F\u00fcr den R\u00e4tselspa\u00df der Graphtheorie gen\u00fcgen erstmal Stift und Papier – oder eine W\u00e4scheleine und ein paar B\u00e4ume.<\/p>\n","protected":false},"author":12876,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_bbp_topic_count":0,"_bbp_reply_count":0,"_bbp_total_topic_count":0,"_bbp_total_reply_count":0,"_bbp_voice_count":0,"_bbp_anonymous_reply_count":0,"_bbp_topic_count_hidden":0,"_bbp_reply_count_hidden":0,"_bbp_forum_subforum_count":0,"footnotes":""},"categories":[486],"tags":[1010250,1010248,1010252,1010246],"class_list":["post-3520","post","type-post","status-publish","format-standard","hentry","category-informatik","tag-graphtheorie","tag-informatik","tag-mengen","tag-raetsel","post-preview"],"_links":{"self":[{"href":"https:\/\/blogs.uni-bremen.de\/scienceblog\/wp-json\/wp\/v2\/posts\/3520","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.uni-bremen.de\/scienceblog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.uni-bremen.de\/scienceblog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.uni-bremen.de\/scienceblog\/wp-json\/wp\/v2\/users\/12876"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.uni-bremen.de\/scienceblog\/wp-json\/wp\/v2\/comments?post=3520"}],"version-history":[{"count":5,"href":"https:\/\/blogs.uni-bremen.de\/scienceblog\/wp-json\/wp\/v2\/posts\/3520\/revisions"}],"predecessor-version":[{"id":3537,"href":"https:\/\/blogs.uni-bremen.de\/scienceblog\/wp-json\/wp\/v2\/posts\/3520\/revisions\/3537"}],"wp:attachment":[{"href":"https:\/\/blogs.uni-bremen.de\/scienceblog\/wp-json\/wp\/v2\/media?parent=3520"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.uni-bremen.de\/scienceblog\/wp-json\/wp\/v2\/categories?post=3520"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.uni-bremen.de\/scienceblog\/wp-json\/wp\/v2\/tags?post=3520"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}