Связное множество

[carpediem]

Помогите, пожалуйста, решить задачку:

Есть связное множество $A = \bigcup^k_{i=1} A_i$, где $A_i$ тоже связные. Нужно доказать, что существует индекс i, такой что $A\setminus A_i$ - связное множество

[ИСН]

Переформулируем в терминах теории графов. Множества станут вершинами, а рёбра проведём между теми из них, которые пересекаются. Тогда во что превратится вопрос?

[carpediem]

Честно, без понятия

[carpediem]

Наверно тогда не только между теми, которые пересекаются, но и между теми, которые имеют общую границу.

-- Сб июн 25, 2011 21:44:30 --

И видимо, тогда задача превратится в такую: что существует вершина этого графа, такая что при выкидывании ее и всех смежных ей ребер, граф останется связным?

[ИСН]

Ну да, пусть так.

-- Сб, 2011-06-25, 22:45 --

И тогда - да, вот в такую.

[carpediem]

На самом деле, неправда, это неправильная формулировка.

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

Видимо, надо как-то по-другому

-- Вс июн 26, 2011 22:26:04 --

По ходу, это вообще неправильное утверждение.

Например:


При выкидывании любого из этих двух эллипсов, оставшаяся часть будет несвязной

-- Вс июн 26, 2011 22:26:32 --

Так что вопрос снимается, спасибо