В теории графов , разделе математики, семейством графов Леви называется семейство графов G n , n = 1, 2, 3, ..., которые обладают определенным типом «компактности» или «запутанности». Многие естественные семейства графов являются семействами Леви. Многие математики отметили этот факт и выразили удивление тем, что ему не существует готового объяснения.
Формально семейство графов G n , n = 1, 2, 3, ..., является семейством Леви, если для любого
где
Здесь D — диаметр графа G , а A ( n ) — окрестность n - графа A. Обратите внимание, что максимизация распространяется на подмножества A из G , при условии, что размер A превышает половину размера G.
На словах это означает, что можно взять подмножество размером не менее половины G и увеличить его только на диаметр графа и в итоге получить почти все множество.
Длинные «нитчатые» (то есть не «компактные») семейства графов, такие как граф циклов порядка n, явно не обладают таким свойством: можно рассмотреть подмножество, содержащее n/2 окрестностей точки (от полуночи до шести часов утра). «часы», скажем). Граф имеет диаметр D около n/2 . Таким образом, -окрестность подмножества имеет размер около n/2 . Семья Леви хотела бы, чтобы этот район охватывал почти всю территорию. Должно быть ясно, что семья Леви должна иметь совершенно особый тип компактной структуры.
