Теория графов(Дискретка)

[MestnyBomzh]

Ориентированный граф на 8 вершинах содержит $n$ ребер.
а)Сколько ребер необходимо, чтобы он мог быть сильно связен
б)Сколько ребер достаточно, чтобы он был заведомо сильно связен?
В пункте а) ответ 8, как я понимаю, потому что при $n=7$ будет одна висячая вершина.
А как подступиться к пункту б)?

[patzer2097]

MestnyBomzh в сообщении #813386 писал(а):

Ориентированный граф на 8 вершинах содержит $n$ ребер.
а)Сколько ребер необходимо, чтобы он мог быть сильно связен
б)Сколько ребер достаточно, чтобы он был заведомо сильно связен?
В пункте а) ответ 8, как я понимаю, потому что при $n=7$ будет одна висячая вершина.
А как подступиться к пункту б)?

в пункте а) у Вас ответ правильный (но решение не вполне) -- ведь при $n=7$, конечно, висячих вершин может не быть (рассмотрите произвольную ориентацию какого-нибудь дерева). А при $n=8$, конечно, достаточно рассмотреть большой цикл..
Что касается пункта б), то там $n=8^2-8-7$ недостаточно - можно рассмотреть граф $(V,E)$, у которого $(u,v)\notin E$ если и только если $u$ равно какой-то заранее фиксированной вершине $u_0$. А попробуйте понять, почему достаточно $n=8^2-8-6$..

P.S. Я тут писал все это в предположении, конечно, что в графе нет петель и одинаковых ребер.

[Null]

Наверно не $n=8^2-8-7$, а $n=\frac{8^2-8}{2}-7$

[patzer2097]

Null в сообщении #813449 писал(а):

Наверно не $n=8^2-8-7$, а $n=\frac{8^2-8}{2}-7$

я имел в виду графы, которые могут содержать одновременно ребро из $u$ в $v$ и ребро из $v$ в $u$.. вроде именно они называются ориентированными. а те, которые получены ориентацией простых графов - "направленными", согласно википедии..
а если все-таки мы имеем в виду направленные графы, то в пункте а) ничего не изменяется, а пункт б) становтися тривиальным..

[Null]

(Оффтоп)

Читаю невнимательно.

[MestnyBomzh]

patzer2097, не могли бы вы объяснить, откуда взялись такие числа: $8^2-8-7$ и $8^2-8-6$?

[patzer2097]

MestnyBomzh в сообщении #813566 писал(а):

patzer2097, не могли бы вы объяснить, откуда взялись такие числа: $8^2-8-7$ и $8^2-8-6$?

$n=8^2-8-7$ -- это число ребер в примере, приведенном выше. Т.е., когда мы выделяем одну вершину $u_0$, и полагаем, что из $u_0$ не выходит ни одного ребра, а все другие ребра в графе есть. То есть, из каждой вершины, кроме $u_0$, выходит по $8-1$ ребер, всего их значит $(8-1)^2=8^2-8-7$.
И оказывается, что $n=(8-1)^2$ -- это оптимальное значение, то есть, любые графы, содержащие $>(8-1)^2$ ребер, будут сильно связными.. у Вас получилось это доказать?

а с пунктом а) кстати, как Вы разобрались?

[MestnyBomzh]

patzer2097, про пункт а): я подумал, что для того чтобы граф был хотя бы слабо связен требуется 7 ребер, при меньшем количестве он будет даже не слабо связен. Теперь для $n=7$ нужно сказать, что все вершины должны быть соединены хотя бы одним ребром (не имеет значения какого направления). Ну и если даже они все соединены хотя бы один ребром, то останутся две вершины, не соединенные ни одним ребром, то есть две висячие вершины, так сказать, тупиковые.
Про б) спасибо большое, отличное объяснение! Только я не понял, зачем раскрывать скобки $(8-1)^2$ В случае для произвольного количества вершин ($k$) имеем: $>(k-1)^2$

[patzer2097]

MestnyBomzh в сообщении #814342 писал(а):

Ну и если даже они все соединены хотя бы один ребром, то останутся две вершины, не соединенные ни одним ребром.

это непонятное предложение. все проще: попробуйте проверить, что при $n=7$ будет вершина, в которую не входит ни одно ребро.

MestnyBomzh в сообщении #814342 писал(а):

Про б) спасибо большое, отличное объяснение! Только я не понял, зачем раскрывать скобки $(8-1)^2$

да, это ни к чему, можно даже написать $49$ осталось только понять, почему графы с $(8-1)^2+1=50$ ребрами будут всегда сильно связными.

[MestnyBomzh]

а) давайте тогда подробно распишем вершины по очереди: на первую вершину два ребра: входящее, исходящее. На вторую: исходящее, на третью: исходящее, на четвертую: исходящее, на пятую: исходящее, на шестую: исходящее. Лимит рёбер исчерпан, у нас задействовано 7 вершин ( в седьмую входит последнее ребро) Есть ещё незадействованное ребро первой вершины (входящее), тогда для незадействованной восьмой вершины оно будет исходящим. Итого:ребра исчерпаны, две вершины только с одним ребром

[patzer2097]

MestnyBomzh в сообщении #814516 писал(а):

а) давайте тогда подробно распишем вершины по очереди: на первую вершину два ребра: входящее, исходящее. На вторую: исходящее, на третью: исходящее, на четвертую: исходящее, на пятую: исходящее, на шестую: исходящее. Лимит рёбер исчерпан, у нас задействовано 7 вершин ( в седьмую входит последнее ребро) Есть ещё незадействованное ребро первой вершины (входящее), тогда для незадействованной восьмой вершины оно будет исходящим. Итого:ребра исчерпаны, две вершины только с одним ребром

наверное, идея правильная, но решение Ваше все-таки неясно. можно же сделать проще: у нас 8 вершин и 7 ребер. Поэтому будет вершина, в которую не будет входить ни одного ребра, и в эту вершину мы ниоткуда не попадем; т.е., граф не является сильно связным.

[MestnyBomzh]

patzer2097, да, вы правы, мои рассуждения были лишком длинны и нерациональны, если можно было рассмотреть вместо 8 только 1 вершину. Спасибо)