Magischer Graph - LinkFang.de





Magischer Graph


Magische Graphen sind in der Graphentheorie eine Graphenklasse mit speziellen Bewertungen von Ecken und Kanten. Das Gewicht einer Kante ist dabei gleich der Summe der Bewertungen der Anfangs-, Endecke und der Kante selbst. Sind alle Kantengewichte gleich, redet man von einem kantenmagischen Graphen. Das Gewicht einer Ecke ergibt sich als Summe der Eckenbewertung und der Bewertung jeder dort beginnenden Kante. Sind alle Eckengewichte gleich, so redet man von eckenmagischen Graphen. Graphen, die sowohl ecken- als auch kantenmagisch sind, werden total magische Graphen genannt.

Eckenmagische Graphen

Sei [math]G=(E, K) [/math] ein endlicher einfacher ungerichteter Graph mit einer totalen Bewertung [math]\lambda: E\cup K\to\{1, 2, ... , |E|+|K|\} [/math]. [math] G [/math] bzw. [math]\lambda [/math] sind ecken-magisch, wenn eine Eckenkonstante [math]h\in \N [/math] existiert, so dass für jede Ecke [math]e \in E[/math] gilt:

[math]wt(e):=\lambda(e)+\sum_{eb\in K}\lambda(eb) =h[/math] (Eckengewicht)

Gewicht einer Ecke ergibt sich als Summe der Eckenbewertung und der Bewertung jeder dort beginnenden Kante.

Kantenmagische Graphen

Sei [math]G=(E, K) [/math] ein endlicher einfacher ungerichteter Graph mit einer totalen Bewertung [math]\lambda: E\cup K\to\{1, 2, ... , |E|+|K|\} [/math]. [math] G [/math] bzw. [math]\lambda [/math] sind kanten-magisch, wenn eine Kantenkonstante [math]k \in \N[/math] existiert, so dass für jede Kante [math]ab\in K [/math] gilt:

[math]wt(ab):=\lambda(a)+\lambda(ab)+\lambda(b) =k[/math] (Kantengewicht)

Man gewichtet eine Kante mit der Summe der Bewertungen der Anfangs- und Endecke und der Kante selbst.

Total magische Graphen

Sei [math]G=(E, K) [/math] ein endlicher einfacher ungerichteter Graph mit einer totalen Bewertung [math]\lambda: E\cup K\to\{1, 2, ... , |E|+|K|\} [/math]. [math] G [/math] bzw. [math]\lambda [/math] sind total magisch, wenn eine Eckenkonstante [math]h \in \N[/math] und eine Kantenkonstante [math]k\in \N [/math] existiert, so dass [math]G [/math] bzw. [math]\lambda [/math] sowohl ecken- als auch kantenmagisch ist.

Beispiele

  • Der triviale Graph [math]K_1 [/math] (Graph mit einer Ecke und keiner Kante) ist total magisch mit der Eckenkonstante [math]1 [/math]. Die Kantenkonstante ist diskutabel.
  • Der Kreisgraph [math]C_3 [/math] (Dreieck) ist total magisch.
  • Der lineare Graph [math]P_3 [/math] ist total magisch.
  • [math]P_3 [/math] und [math]K_1 [/math] sind die einzigen total magischen Sterne.
  • Der Graph [math]K_1\cup P_3 [/math] ist total magisch.

Literatur

  • Alison M. Marr, W. D. Wallis: Magic Graphs. 2. Auflage. Springer, 2012, ISBN 978-0-8176-8391-7.
  • A. Kotzig, A. Rosa: Magic valuations of finite graphs. Canad. Math. Bull. 13 (1970), S. 451–461

Weblinks


Kategorien: Grundbegriff (Graphentheorie) | Graphenklasse

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Magischer Graph (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.