1
1

Какое максимальное количество ребер может быть в простом слабо связном ориентированном графе на 10 вершинах, не являющимся сильно связным?

задан 26 Окт '15 11:39

10|600 символов нужно символов осталось
3

Здесь, как я понимаю, рассматривается простой орграф, то есть допускаются рёбра разного направления, соединяющие две вершины. В полном простом орграфе на $%n$% вершинах будет $%n(n-1)$% направленное ребро. Если мы уберём все рёбра, входящие в фиксированную вершину, то в неё будет не попасть, и орграф не будет сильно связным. Число (направленных) рёбер при этом будет равно $%(n-1)^2$%.

Осталось показать, что при большем числе рёбер орграф окажется сильно связным. Действительно, в противном случае найдётся вершина $%u$%, из которой нельзя попасть по стрелкам в некоторую вершину $%v$%. Рассмотрим множество всех вершин, в которые можно прийти из $%u$%. По предположению, их число $%k$% удовлетворяет неравенствам $%1\le k < n$%. Тогда у нас отсутствует стрелка, идущая из любой из $%k$% вершин в любую из оставшихся $%n-k$% вершин, то есть число отсутствующих рёбер не меньше $%k(n-k)$%. Ранее было показано, что эта величина не меньше $%n-1$%.

ссылка

отвечен 26 Окт '15 13:25

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×544
×525
×174
×130
×14

задан
26 Окт '15 11:39

показан
3234 раза

обновлен
26 Окт '15 13:25

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru