понедельник, 13 сентября 2010 г.

Вопрос по Луркоморью графам

Вместо вступления

Как показывает практика, вот это безобразие на самом деле никого особо не волнует, и контора готова платить за плевание в потолок потери 2-3 и более часов в день. Ну и ладно - пытливый ум способен найти себе занятие (и 'освоить' офисный канал:) ).
Так вот, наткнулся я вот на этот замечательный сайт, и оказалось, что осознать всю глубину написанного мне мешает недостаточное знание русского-матерного и всяких там сленговых словечек. Благо, существует довольно подробные разъяснения практически всех непонятных слов и выражений (интересно, познавательно и с картинками).
После того, как количество закладок в браузере превысило отметку 30, родился резонный вопрос: 'А сколько же это может продолжаться?'

Более форматизированная постановка вопроса

На сколько я понимаю, ближайшая мат. модель - 'граф с однонаправленными связями'. Статья это вершина, связь это гиперссылка с одной статьи на др.
Интересует 3 вопроса:
1. Сколько переходов надо совершить, чтобы посетить все узлы этого графа? Или какой порядок этой цифры?
2. Есть ли несвязанные вершины (без входящих, и исходящий связей)?
3. Есть ли вершины, у которых есть только исходящие связи (т.е. нет входящих)?