Haben Sie jemals versucht, eine Denkaufgabe zu machen, bei der Sie die Punkte verbinden müssen, um in einem zusammenhängenden Strich den Umriss eines Hauses zu zeichnen, ohne die Linien noch einmal durchgehen zu müssen? Oder vielleicht haben Sie auf Facebooks Freundesempfehlungen geklickt oder Siedler von Catan gespielt.
Wenn ja, haben Sie eine Form der Graphentheorie kennengelernt, ein Gebiet der Mathematik, das Dr. Xujun Liu von der Xi’an Jiaotong-Liverpool University, China, fasziniert.
„Mein ursprünglicher Plan bestand darin, mich einem anderen Bereich der Mathematik zu widmen, aber ich war fasziniert von der Eleganz und Schönheit der Beweisideen in der Graphentheorie“, sagt Dr. Liu.
Die Graphentheorie ist ein Zweig der Mathematik, der die Beziehungen und Eigenschaften von Graphen untersucht – wir sprechen hier jedoch nicht von Kreisdiagrammen und Streudiagrammen.
Angenommen, Sie möchten herausfinden, wie Sie am effizientesten mit dem Zug zwischen London und Wien reisen können. Sie könnten jede Stadt als Punkt (in der Mathematik als Scheitelpunkt bezeichnet) und die Routen zwischen den Städten als Linien oder Kurven (als Kanten bezeichnet) zeichnen. Diese Kombination aus Eckpunkten und Kanten ergibt einen Graphen.
Mithilfe der Grafik könnten dann die Verbindungen und Routen zwischen den beiden Städten untersucht werden.
Die Graphentheorie kann Mathematikern dabei helfen, komplexe Netzwerke in verschiedenen Bereichen, einschließlich Informatik und Elektrotechnik, zu modellieren und zu analysieren.
In Zusammenarbeit mit Dr. Michael Santana und Dr. Taylor Short von der Grand Valley State University, USA, hat Dr. Liu habe kürzlich ein Problem gelöst Das hat bei Forschern der Graphentheorie große Aufmerksamkeit erregt. Der Artikel „Every subcubic multigraph is (1,27)-packing edge-colorable“ wurde veröffentlicht in Das Journal of Graph Theory.
Färbe mich anders
Die Forschung des Teams umfasst einen Aspekt der Graphentheorie namens Färbung. Die Theorie der Farbgebung beschäftigt sich mit dem Problem, Teile eines Diagramms so zu kennzeichnen, dass sie bestimmten Regeln entsprechen und bestimmte Konflikte vermeiden.
Stellen Sie sich zum Beispiel vor, Sie möchten jeden darunter liegenden Punkt so einfärben, dass nie zwei Punkte derselben Farbe nebeneinander liegen – dies ist ein Beispiel für die Einfärbung.
Dr. Liu erklärt: „Ich arbeite an einer Art der Farbgebung namens Packing Coloring, die durch ein Frequenzzuweisungsproblem in Rundfunknetzen entsteht.
„Es gibt viele Rundfunksender auf der Welt, und wir möchten jedem Sender eine Frequenz zuweisen. Sender, denen dieselbe Frequenz zugewiesen ist, müssen mindestens einen bestimmten Abstand voneinander haben, und jede Frequenz erfordert einen anderen kleinsten Abstand.
„Eine der Fragen, die sich aus diesem Problem ergibt, lautet: ‚Wie viele Frequenzen sind für eine solche Zuweisung mindestens erforderlich?‘“
Strategische Entwicklung
In seiner jüngsten Arbeit haben Dr. Liu und seine Mitarbeiter erfolgreich ein von den Mathematikern Hocquard, Lajou und Lužar vorgeschlagenes Problem gelöst Zeitschrift für Graphentheorie im Jahr 2022.
Bei diesem Problem handelt es sich um die Aufteilung subkubischer Graphen, wobei an jedem Scheitelpunkt (Punkt) maximal drei Kanten (Linien) befestigt sind.
Die Aufgabe besteht darin, zu bestimmen, wie die Kanten in mehrere Klassen unterteilt werden können, wobei zu berücksichtigen ist, dass es zwei verschiedene Arten von Kanten gibt
Typ I – erfordert, dass jedes Kantenpaar keinen gemeinsamen Endpunkt hat (jede Kante hat zwei Endpunkte).
Typ II – erfordert, dass jedes darin enthaltene Kantenpaar nicht nur keinen gemeinsamen Endpunkt hat, sondern auch, dass ihre Endpunkte nicht durch eine andere Kante verbunden sind.
Die Frage, die das Team lösen wollte, ist, ob es möglich ist, die Anzahl der Typ-II-Klassen zu minimieren und gleichzeitig die Anzahl der Typ-I-Klassen auf eins zu belassen.
Dr. Liu sagt: „Durch die Lösung dieser Vermutung haben wir einen wesentlichen Beitrag zur Verbesserung unseres Verständnisses der strukturellen Eigenschaften subkubischer Graphen geleistet und könnten Erkenntnisse zur Lösung der berühmten Erdős-Nešetřil-Vermutung liefern.“
„Es kann auch als Leitfaden für die Lösung von Problemen in Kommunikationsnetzwerken dienen.“
Da Dr. Liu die Entscheidung getroffen hat, Graphentheorie im Rahmen des Ph.D. zu studieren. Unter der Leitung von Professor Alexandr Kostochka an der University of Illinois hat er mehrere Vermutungen erfolgreich gelöst, darunter ein Problem, das vom Abel-Preisträger 2012 Szemerédi und seinen Co-Autoren vorgeschlagen wurde.
Dr. Liu sagt, er werde weiterhin weitere Probleme auf diesem Gebiet angehen. „Ich habe vor, weiterhin Probleme mit der Graphenfärbung zu erforschen und mich dabei auf die Erforschung von Packungsfärbungen mithilfe zusätzlicher Methoden wie dem kombinatorischen Nullstellensatz und probabilistischen Methoden zu konzentrieren.
„Durch die Verfolgung dieser Forschungsrichtungen hoffe ich, sinnvolle Beiträge auf diesem Gebiet zu leisten“, sagt er.
Mehr Informationen:
Xujun Liu et al, Jeder subkubische Multigraph ist (1,27)-Packungskante färbbar, Zeitschrift für Graphentheorie (2023). DOI: 10.1002/jgt.23004