Теория графов

[TssDragon]

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

[Lia]

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

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

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

[Toucan]

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

[provincialka]

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

[dikiy]

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

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

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

[provincialka]

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

[TssDragon]

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

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


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

[dikiy]

provincialka в сообщении #946254 писал(а):

dikiy, вы уверены, что имеется в виду именно сильная связность?

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

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

Цитата:

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

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

[demolishka]

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