2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Теория графов(Дискретка)
Сообщение12.01.2014, 17:35 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Теория графов(Дискретка)
Сообщение12.01.2014, 18:37 
Заслуженный участник


14/03/10
867
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 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Теория графов(Дискретка)
Сообщение12.01.2014, 20:28 
Заслуженный участник


14/03/10
867
Null в сообщении #813449 писал(а):
Наверно не $n=8^2-8-7$, а $n=\frac{8^2-8}{2}-7$

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

 Профиль  
                  
 
 Re: Теория графов(Дискретка)
Сообщение12.01.2014, 20:36 
Заслуженный участник


12/08/10
1608

(Оффтоп)

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

 Профиль  
                  
 
 Re: Теория графов(Дискретка)
Сообщение12.01.2014, 23:37 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Теория графов(Дискретка)
Сообщение12.01.2014, 23:49 
Заслуженный участник


14/03/10
867
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 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Теория графов(Дискретка)
Сообщение14.01.2014, 20:07 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Теория графов(Дискретка)
Сообщение14.01.2014, 23:10 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Теория графов(Дискретка)
Сообщение14.01.2014, 23:20 
Заслуженный участник


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

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

 Профиль  
                  
 
 Re: Теория графов(Дискретка)
Сообщение15.01.2014, 00:46 
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 12 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group