2014 dxdy logo

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

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




 
 Вершинная связность графа
Сообщение21.01.2013, 17:15 
Доброго времени суток всем. У меня возникла такая проблемка: на зачете попалась задачка
. Узнав новость, госпожа 1 сообщает ее своим знакомым дамам; та, в свою очередь, своим знакомым, и т.д. Наконец, новость становится известна всем дамам. Какое наименьшее число дам должно внезапно оне¬меть, чтобы НОВОСТЬ, сообщенная госпожой 1, никогда не стала известной
всем дамам?
Знакомые госпожи 1: 2,3,4,7
Знакомые госпожи 2: 1,3,4
Знакомые госпожи 3:1,2,6,8
Знакомые госпожи 4: 1,2,5
Знакомые госпожи 5: 4,6,7,8
Знакомые госпожи 6: 3,5,7,8
Знакомые госпожи 7: 1,5,6,8
Знакомые госпожи 8: 3,5,6,7
Насколько я понял, задача сводится к отысканию вершинной связности графа. Ее нужно решить без использования критерия. (например "методом пристального всматривания")
Собственно говоря, у меня получилось 4. Преподаватель сказал, что он сомневается, и по его мнению ответ 3. Его авторитету я доверяю больше чем в себе в таких вопросах. Но все таки, кто не прав? И какие еще методы можно использовать при решении этой задачи?

 
 
 
 Re: Вершинная связность графа
Сообщение21.01.2013, 17:32 
Ничего не рисуя и смотря только на первые 2 ваши строчки (дальше не смотрел) заметил, что если онемеют дамы 3, 4, 7 то новость дальше круга (1, 2, 3, 4, 7) никуда не пойдет.

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


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