мимоходом, очевидное

Чем больше мозги заржавели, тем противнее они скрипят, когда все же пытаешься ими пользоваться.

в стране моей любви

Попытался воспользоваться поддержкой субтитров в Ютюбе, чтобы вставить русский подстрочник в эту ивритскую песню. Песня называется "Бе-эрец ахавати" (в стране моей любви), на слова Леи Гольдберг - очень люблю это стихотворение.

P.S. Русские субтитры должны появляться прямо в клипе; если вам не видно, попробуйте перезагрузить еще раз, или нажать на буквы CC, которые выпадают в меню в правом нижнем углу окошка.

немного о графах (математическое)

(эта запись может быть интересна математикам и сочувствующим)

Вчера узнал красивый и одновремнно очень простой пример использования вероятностного метода в комбинаторике - настолько простой, что можно стоя на одной ноге рассказать, пожалуй.

Пусть G - граф; доминирующим называется такое подмножество вершин G, что любая вершина либо в нем, либо соседствует с кем-то, кто в нем. Например, в полном графе - где любые две вершины соединены - подмножество из любой одной вершины является доминирующим.

Интуитивно ясно, что в графе с очень высокой минимальной степенью d - из каждой вершины выходит не менее d ребер - должны существовать небольшие по размеру доминирующие множества - связей очень много, поэтому даже из небольшого множества будет можно добраться до всех за один шаг. Теорема: в графе из n вершин с минимальной степенью d есть доминирующее множество размером не больше n*(1+ln(d+1))/(d+1). При большом d это всего лишь малая часть n - например, при минимальной степени около 100 теорема говорит, что можно составить доминирующее множество из всего 5% вершин графа.

Доказательство. ( Read more... )