Monotone Grapheigenschaft

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Monotone Grapheneigenschaft)
Zur Navigation springen Zur Suche springen

Als monotone Grapheigenschaft oder monotone Grapheneigenschaft bezeichnet man in der Graphentheorie eine Eigenschaft von Graphen, die für jeden Teilgraphen eines Graphen gilt, sobald der Graph selbst diese Eigenschaft hat.

Beispiele monotoner Eigenschaften

[Bearbeiten | Quelltext bearbeiten]

Nach dem Satz von Bollobás besitzt jede monotone Grapheneigenschaft eine Schwellenfunktion.[1]

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. B. Bollobás, A. G. Thomason: Threshold functions. In: Combinatorica. Band 7, Nr. 1, 1. März 1987, ISSN 1439-6912, S. 35–38, doi:10.1007/BF02579198.