2014 dxdy logo

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

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


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


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

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

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

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

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



Начать новую тему Ответить на тему
 
 Теория графов
Сообщение14.12.2014, 16:26 


14/12/14
7
Помогите, пожалуйста, с задачей
" Переформулировать задачу в теории графов, определив, что является вершинами, а что ребрами графа. Выбрать способ задания графа. Описать алгоритм решения поставленной задачи. Записать протокол работы этого алгоритма на некотором примере.
Знания передаются от "учителей" к "ученикам", причем некоторые "учителя" являются "учениками" и наоборот. У каждого "учителя" может быть несколько "учеников", а у каждого "ученика" несколько "учителей". Информация от любого "учителя" может дойти до любого "ученика". Найти все такие пары "учитель-ученик", разрыв отношений в любой из которых разобьет все множество людей на две группы, не обменивающиеся знаниями. "
Пока предположил только, что вершина - учитель/ученик, при чем не могу понять, как сделать вершину одновременно и учителем и учеником
ребро - "передача знаний", при чем ребро, я так понял, должно быть направленным
а вот дальше совсем тупик :/
буду благодарен любым подсказкам

 Профиль  
                  
 
 Posted automatically
Сообщение14.12.2014, 16:31 


20/03/14
12041
 i  Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Тема перемещена в Карантин по следующим причинам:

Наберите текст задачи в самом сообщении, пожалуйста.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

 Профиль  
                  
 
 Posted automatically
Сообщение14.12.2014, 17:27 
Админ форума
Аватара пользователя


19/03/10
8952
 i  Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

 Профиль  
                  
 
 Re: Теория графов
Сообщение14.12.2014, 17:53 
Заслуженный участник
Аватара пользователя


18/01/13
12044
Казань
А зачем делать вершины "учителями" или "учениками"? Это означает только, что в каждую ребра могут как входить, так и выходить.
Искомое вами ребро называется, кажется, "мост".
А в каком смысле вам надо его "найти"? На конкретном графе? Или программу написать?

 Профиль  
                  
 
 Re: Теория графов
Сообщение14.12.2014, 18:01 


15/04/12
175
Ребро $(u,v)$ означает, что информация может передаваться от $u$ к $v$. То есть в данном случаем $u$ учитель $v$.

Для дальнейшего решения задачи используйте теорему: "Граф является сильно связным тогда и только тогда, если существует цикл Эйлера."

Причем при поиске цикла Эйлера останов в алгоритме будет происходить как раз по той причине, что алгоритм напарывается на то ребро, при удалении которого граф перестает быть сильно связным.

 Профиль  
                  
 
 Re: Теория графов
Сообщение14.12.2014, 18:05 
Заслуженный участник
Аватара пользователя


18/01/13
12044
Казань
dikiy, вы уверены, что имеется в виду именно сильная связность? Условие сформулировано как-то неясно. Не сказано "люди все попарно обмениваются знаниями", а только "группы обмениваются знаниями".

 Профиль  
                  
 
 Re: Теория графов
Сообщение14.12.2014, 18:19 


14/12/14
7
provincialka
Спасибо, о том, что не надо делать вершины "учителем" или "учеником" уже догадался :)
Сейчас проблема именно в том, что бы описать алгоритм нахождения такого "моста"

Но ведь цикл эйлера может быть только в сильно связанном графе, а здесь такое не подходит
Я вот нарисовал пример графа, для этой задачи. Визуально то я могу найти это ребро :) а вот описать это словесно
Изображение

нет, программу писать не надо
необходимо просто словесно объяснить алгоритм поиска "моста" и привести пример работы

 Профиль  
                  
 
 Re: Теория графов
Сообщение14.12.2014, 18:20 


15/04/12
175
provincialka в сообщении #946254 писал(а):
dikiy, вы уверены, что имеется в виду именно сильная связность?

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

но я только что посмотрел теорему. Я неправильно ее сформулировал. Там еще надо, чтобы в каждой веришне количество входящих ребер было равно колиеству исходящих.

Цитата:
Условие сформулировано как-то неясно. Не сказано "люди все попарно обмениваются знаниями", а только "группы обмениваются знаниями".

ну, если до этого граф был сильно связен, то если при удалении какого либо ребра граф может распасться максимум на две сильно связные компоненты. Ибо если бы одна из этих компонент была не сильно связна, то и исходный граф не был бы сильно связен.

 Профиль  
                  
 
 Re: Теория графов
Сообщение14.12.2014, 18:24 
Заслуженный участник
Аватара пользователя


28/04/14
968
спб
Поиск мостов осуществляется с помощью обхода в глубину, без всяких теорем. Здесь можно прочитать об этом со всеми подробностями.

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

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



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

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


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

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