Magischer Graph

aus Wikipedia, der freien Enzyklopädie
Dies ist die aktuelle Version dieser Seite, zuletzt bearbeitet am 20. April 2022 um 11:16 Uhr durch imported>HatsuneMilku(2614042) (Änderung 222223509 von 2A02:908:2214:5C00:B8B9:80D1:F21A:3C38 rückgängig gemacht;).
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)

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 ein endlicher einfacher ungerichteter Graph mit einer totalen Bewertung . bzw. sind ecken-magisch, wenn eine Eckenkonstante existiert, so dass für jede Ecke gilt:

(Eckengewicht)

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

Kantenmagische Graphen

Sei ein endlicher einfacher ungerichteter Graph mit einer totalen Bewertung . bzw. sind kanten-magisch, wenn eine Kantenkonstante existiert, so dass für jede Kante gilt:

(Kantengewicht)

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

Total magische Graphen

Sei ein endlicher einfacher ungerichteter Graph mit einer totalen Bewertung . bzw. sind total magisch, wenn eine Eckenkonstante und eine Kantenkonstante existiert, so dass bzw. sowohl ecken- als auch kantenmagisch ist.

Beispiele

  • Der triviale Graph (Graph mit einer Ecke und keiner Kante) ist total magisch mit der Eckenkonstante . Die Kantenkonstante ist diskutabel.
  • Der Kreisgraph (Dreieck) ist total magisch.
  • Der lineare Graph ist total magisch.
  • und sind die einzigen total magischen Sterne.
  • Der Graph ist total magisch.

Literatur

  • A. Kotzig, A. Rosa: Magic valuations of finite graphs. In: Canad. Math. Bull., 13, 1970, S. 451–461

Weblinks