2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 Re: Теория графов(Дискретка)
Сообщение12.01.2014, 18:37 
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. Я тут писал все это в предположении, конечно, что в графе нет петель и одинаковых ребер.

 
 
 
 Re: Теория графов(Дискретка)
Сообщение12.01.2014, 20:16 
Наверно не $n=8^2-8-7$, а $n=\frac{8^2-8}{2}-7$

 
 
 
 Re: Теория графов(Дискретка)
Сообщение12.01.2014, 20:28 
Null в сообщении #813449 писал(а):
Наверно не $n=8^2-8-7$, а $n=\frac{8^2-8}{2}-7$

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

 
 
 
 Re: Теория графов(Дискретка)
Сообщение12.01.2014, 20:36 

(Оффтоп)

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

 
 
 
 Re: Теория графов(Дискретка)
Сообщение12.01.2014, 23:37 
Аватара пользователя
patzer2097, не могли бы вы объяснить, откуда взялись такие числа: $8^2-8-7$ и $8^2-8-6$?

 
 
 
 Re: Теория графов(Дискретка)
Сообщение12.01.2014, 23:49 
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$ ребер, будут сильно связными.. у Вас получилось это доказать?

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

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

 
 
 
 Re: Теория графов(Дискретка)
Сообщение14.01.2014, 20:07 
MestnyBomzh в сообщении #814342 писал(а):
Ну и если даже они все соединены хотя бы один ребром, то останутся две вершины, не соединенные ни одним ребром.
это непонятное предложение. все проще: попробуйте проверить, что при $n=7$ будет вершина, в которую не входит ни одно ребро.
MestnyBomzh в сообщении #814342 писал(а):
Про б) спасибо большое, отличное объяснение! Только я не понял, зачем раскрывать скобки $(8-1)^2$
да, это ни к чему, можно даже написать $49$ :-) осталось только понять, почему графы с $(8-1)^2+1=50$ ребрами будут всегда сильно связными.

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

 
 
 
 Re: Теория графов(Дискретка)
Сообщение14.01.2014, 23:20 
MestnyBomzh в сообщении #814516 писал(а):
а) давайте тогда подробно распишем вершины по очереди: на первую вершину два ребра: входящее, исходящее. На вторую: исходящее, на третью: исходящее, на четвертую: исходящее, на пятую: исходящее, на шестую: исходящее. Лимит рёбер исчерпан, у нас задействовано 7 вершин ( в седьмую входит последнее ребро) Есть ещё незадействованное ребро первой вершины (входящее), тогда для незадействованной восьмой вершины оно будет исходящим. Итого:ребра исчерпаны, две вершины только с одним ребром

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

 
 
 
 Re: Теория графов(Дискретка)
Сообщение15.01.2014, 00:46 
Аватара пользователя
patzer2097, да, вы правы, мои рассуждения были лишком длинны и нерациональны, если можно было рассмотреть вместо 8 только 1 вершину. Спасибо)

 
 
 [ Сообщений: 12 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group