2014 dxdy logo

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

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




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

 
 
 
 Posted automatically
Сообщение14.12.2014, 16:31 
 i  Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Тема перемещена в Карантин по следующим причинам:

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

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

 
 
 
 Posted automatically
Сообщение14.12.2014, 17:27 
Аватара пользователя
 i  Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

 
 
 
 Re: Теория графов
Сообщение14.12.2014, 17:53 
Аватара пользователя
А зачем делать вершины "учителями" или "учениками"? Это означает только, что в каждую ребра могут как входить, так и выходить.
Искомое вами ребро называется, кажется, "мост".
А в каком смысле вам надо его "найти"? На конкретном графе? Или программу написать?

 
 
 
 Re: Теория графов
Сообщение14.12.2014, 18:01 
Ребро $(u,v)$ означает, что информация может передаваться от $u$ к $v$. То есть в данном случаем $u$ учитель $v$.

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

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

 
 
 
 Re: Теория графов
Сообщение14.12.2014, 18:05 
Аватара пользователя
dikiy, вы уверены, что имеется в виду именно сильная связность? Условие сформулировано как-то неясно. Не сказано "люди все попарно обмениваются знаниями", а только "группы обмениваются знаниями".

 
 
 
 Re: Теория графов
Сообщение14.12.2014, 18:19 
provincialka
Спасибо, о том, что не надо делать вершины "учителем" или "учеником" уже догадался :)
Сейчас проблема именно в том, что бы описать алгоритм нахождения такого "моста"

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

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

 
 
 
 Re: Теория графов
Сообщение14.12.2014, 18:20 
provincialka в сообщении #946254 писал(а):
dikiy, вы уверены, что имеется в виду именно сильная связность?

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

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

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

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

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

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


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