Monotone Grapheigenschaft
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]
Eigenschaften[Bearbeiten | Quelltext bearbeiten]
Nach dem Satz von Bollobás besitzt jede monotone Grapheneigenschaft eine Schwellenfunktion.[1]
Literatur[Bearbeiten | Quelltext 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 | Quelltext 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.