понедельник, 1 марта 2010 г.

n-юродность

Я долгое время не мог понять родственные отношения с n-юродностью, n >= 3. "Троюродная сестра" или "двоюродный дядя" - эти абстракции не помещались у меня в голове. Двоюродные братья/сестры у меня есть, дяди/тети тоже имеются, а всех кто дальше я причисляю к дальним родственникам.

Таки въехал. Оказывается все просто. Берем две вершины. Ищем lca. n = min(r(lca, v_1), r(lca, v_2)). \ldots Дедушка/дядя/брат/племянник/внук /ldots определяется простой разницей: r(lca, v_1) - r(lca, v_2), где r(i, j) - расстояние между прямыми потомками, не симметрично; lca - по определению :) .

Объективно пол определяется по записи в свидетельстве о рождении. Хотя я знаю нескольких физиологически-мальчиков с головами девочек, и несколько физиологически-девочек с головами мальчиков. Так что пол для меня вещь субъективная.

Комментариев нет: