Monotone Grapheigenschaft
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
Eigenschaften Bearbeiten
Nach dem Satz von Bollobás besitzt jede monotone Grapheneigenschaft eine Schwellenfunktion.[1]
Literatur Bearbeiten
- Béla Bollobás: Hereditary and Monotone Properties of Graphs. doi:10.1007/978-3-642-60406-5_7
- Ehud Friedgut, Gil Kalai: Every monotone graph property has a sharp threshold
- Noga Alon, Asaf Shapira: Every monotone graph property is testable
- B. Bollobás, A. G. Thomason: . In: . Band 7, Nr. 1, 1. März 1987, ISSN 1439-6912, S. 35–38, doi:10.1007/BF02579198
Einzelnachweise Bearbeiten
- ↑ 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.