Я бы так подошел...
Пусть A и B - две вершины графа G, а (AB) - множество всех путей из А в B, являющеееся подграфом G'
Надо доказать, что если не существует двух непересекающихся путей, то G' может быть разбит еще на 2 подграфа, имеющих только одну общую вершину, что ессно противоречит.
Вот с последним есть некие технические сложности
Я думаю, на доказательстве Grigoriy можно поставить точку. Вполне нормальное доказательство.
А вот и простая, но реальная иллюстрация к этой задачке - Питерская подземка.
Сегодня Петербургское метро состоит из 5 линий и 7 узлов пересадки. Все узлы представляют собой пересечения двух линий, хотя один узел и подпорчен пересадкой с концевой станции еще одной ветки; эта станция работает, но не имеет пока самостоятельного выхода на поверхность, поэтому позволю себе ее проигнорировать. Буквально через несколько дней должно состояться открытие новой станции - Адмиралтейская, которая первоначально задумывалась как восьмой пересадочный узел (вроде как недостающий), но пока, в ближайшие годы, собственно пересадки, увы, не будет. Итого имеем граф из 5 вершин (линий) и 7 ребер (пересадок). Я нарисовал схему СПб-метро, раскрасив ее не в оригинальные цвета с официального сайта www.metro.spb.ru/map.html, а в привычные для моего графа цвета.
Раз уж занялись графами, такая задачка: доказать, что в любом простом планарном графе найдется вершина, степень которой не больше 5.
(Имеется в виду, что граф конечный, т.е., всякие бесконечные решетки можно не рассматривать. Простой граф = не более одного ребра между каждой парой вершин, и нет петель. Планарный граф = можно нарисовать на плоскости. Степень вершины = количество исходящих из нее ребер.)
Vladimirovich написал(а):Ну это вот из теоремы Эйлера следует
Это да. Все задачки про планарные графы решаются через нее
А что-нибудь действительно полезное из нее следует? Возьмем, к примеру, схему Московского метрополитена. Довольно большой граф. Если вдруг окажется, что это планарный граф, то что реально полезного о нем через нее можно сказать?
А что-нибудь действительно полезное из нее следует? Возьмем, к примеру, схему Московского метрополитена. Довольно большой граф. Если вдруг окажется, что это планарный граф, то что реально полезного о нем через нее можно сказать?
Почему вдруг? Это планарный граф. Вроде
Я не помню, чтобы там были пересечения без пересадок. Хотя ...
Например, с синей ветки на желтую нет пересадки, и поэтому мне постоянно приходится ездить с двумя пересадками вместо одной. www.mosmetro.ru/flash/scheme01.html Схема.
Накануне 10 декабря всем московским школам было предписано провести в день митинга на Болотной площади контрольные работы по русскому языку. 24 декабря состоится митинг на проспекте Сахарова, и департамент образования Москвы снова выдал указание провести контрольные - на этот раз по математике. Мы в Ленте.ру решили помочь чиновникам департамента и набросали небольшой список идеологически верных задач разного уровня сложности, которые можно предлагать всем - от учеников пятого класса средней школы до олимпиадников.
1) Наймит Госдепа Алексей Навальный был задержан во время несанкционированного марша по Мясницкой улице. От места задержания предателя до ОВД Таганское - 8 километров, до ОВД Тверское - 3 километра, а до ОВД Измайлово - 15 километров. В какое из ОВД увезли Навального, если первый твит из обезьянника он написал спустя 3 часа, а средняя скорость передвижения автозака по московским пробкам составила 5 км/ч?
2) Дизайнер Игорь получил за участие в митинге на Болотной 500 рублей, фотограф Илья - 800 рублей, а популярный блогер Рустем - 1200 рублей. На какую сумму обманул этих трех участников сборища грантоедов их координатор Максим, если Госдеп потребовал от него привести на митинг 20 человек и выделил на привлечение массовки, исходя из условия равномерной оплаты, 50 тысяч рублей?
3) Из собирающихся раскачивать лодку на Проспекте Сахарова 24 декабря 90% составляют хипстеры, записавшиеся на ивент в модной американской социальной сети Фейсбук, а 10% - прогуливающие школу ученики, которые организовали встречу благодаря отечественной сети ВКонтакте. Из тех, кто все-таки явится на Сахарова, записавшиеся на ивент в Фейсбуке составят только 12 процентов. Сколько предателей интересов Родины придет на митинг, если собиралось прийти 44 тысячи человек, пользователи ВКонтакте придут в полном составе, а помимо хипстеров и школьников никого больше не будет? (Считайте, что хипстеры не используют ВКонтакте, а школьники - фейсбук).
4) Когда известный политический деятель и дипломат Дмитрий Рогозин выступает на 25-тысячных митингах в поддержку конституционного строя, он любит кричать Слава России!. Владимир Владимирович, будучи в гостях у Дмитрия Анатольевича в Кремле, слышит этот правильный и патриотический лозунг спустя 1,1764705 секунды. Вслед за Дмитрием Рогозиным Слава России! кричат собравшиеся на площади молодые патриоты. Учитывая, что температура воздуха составляет примерно 0 градусов по Цельсию, ветер дует с северо-запада и 25 тысяч человек кричат громче мегафона Рогозина, вычислите, как скоро Владимир Владимирович Путин и Дмитрий Анатольевич Медведев услышат одобрительный народный глас.
5) Добрый волшебник Владимир Чуров творит особую электоральную магию при помощи компьютера в ЦИК. К несчастью, в любимую программу волшебника, предназначенную для честного подсчета голосов избирателей, пробрался вредоносный вирус, и она стала выдавать результаты в какой-то другой, не десятичной системе счисления! Так, например, она показала, что в Ростовской области проголосовали 146 процентов избирателей. Помогите разобраться доброму волшебнику Владимиру Чурову, в какой системе счисления работает компьютер, если на самом деле выборы в Ростовской области прошли без нарушений.
6) Восхищенные разгоном демонстраций несогласных на Триумфальной американские полицейские пригласили доблестный московский ОМОН помочь разобраться с движением Захвати все подряд на нью-йоркском Манхэттене. Манхэттен разбит двумя семействами параллельных улиц - стритами и авеню, которые нумеруются последовательно - на прямоугольные кварталы со сторонами 200 на 70 метров (авеню идут вдоль коротких сторон). На углу 9-й авеню и 34-й стрит доблестный московский ОМОН обнаружил мистера Лемона - одного из лидеров Захвати все подряд - и по доброте душевной решил отнести его на санкционированный митинг, который проходил на углу 40-й стрит и 6-й авеню. Успеет ли доблестный московский ОМОН доставить мистера Лемона на место к началу митинга, если тот начинается через 10 минут, а скорость передвижения омоновцев - 6 километров в час? Ответ обоснуйте.
7) По Болотной площади бродят три вида нерешительных хомячков - либеральные прислужники Госдепа, леваки и русские националисты. Когда два хомячка с разными взглядами встречаются, они начинают бесплодно спорить, быстро разочаровываются в собственных убеждениях и убеждениях оппонента и одновременно меняют свои политические взгляды на третий оставшийся вариант (например, после разговора прислужник Госдепа и левак становятся русскими националистами). В начальный момент времени на площади было 24 999 хомячков, из которых 12 996 были леваками, 6 001 - русскими националистами и 6 002 - прислужниками Госдепа. Fox News сообщает, что на площади вполне может сложиться ситуация, в которой все хомячки перейдут под влияние американского империализма. Уличите рупор Вашингтонского обкома во лжи.
8) Полковник ФСБ Сергей Петрович занимается мониторингом деятельности оппозиции в социальных сетях. Ему удалось установить неожиданный факт - если у двух активистов оппозиции одинаковое число френдов-оппозиционеров, то среди них нет таких, которые бы дружили одновременно с обоими этими оппозиционерами. Для очередного отчета Сергею Петровичу потребовался оппозиционер-неудачник - человек, который дружит всего лишь с одним другим оппозиционером. Необходимо доказать, что уважаемый полковник сможет найти такого персонажа. Предложите Сергею Петровичу алгоритм поиска такого человека.
Это не предполагается, но это и не используется. Важно, что он длиннее чем k, но это по определению точки D - она от A на расстоянии k+1 - т е кратчайший путь из неё в А имеет длину k +1
ок. Но тогда непонятно, почему BA и DC не могут пересечься.
Если пути ВА и ДА пересекаются, то возьмем ближайшую к Д точку пересечения и отступим один шаг назад по пути ДА, это и будет нужная для индукции точка С, отстоящая от А, как и точка В, не более чем на k шагов.
Если пути ВА и ДА пересекаются, то возьмем ближайшую к Д точку пересечения и отступим один шаг назад по пути ДА, это и будет нужная для индукции точка С, отстоящая от А, как и точка В, не более чем на k шагов.
А чего никто не возразит? Ведь пока еще не все доказано.
Да, похоже дырка заделывается легко.
Предположим, что для всех точек, отстоящих от А не более чем на k доказано существование 2-х непересекающихся путей в А.
Пусть Точка С отстоит от А на расстоянии k+1, т е существует B, отстоящая от А на k и прямо соединённая с С.
Существуют неперересекающиеся 2 пути из В в А. Существует путь из С в А, не проходящий через В. Если он не пересекается ни с одним из предыдущих, то всё доказано - берём его и один из этих путей, дополненый веткой СА. Если пересекается, идём по нему из С до 1-ого пересечения с одним из тех путей, а дальше по тому пути, с которым пересеклись. Это один путь. А 2-ой - оставшийся путь из В в А, дополненный веткой СВ.
Вроде бы самоед предложил нечто похожее, но меня смутило, что он воспользовался моим дефектным построением, и я не стал вникать.
Да, похоже дырка заделывается легко.
Предположим, что для всех точек, отстоящих от А мне более чем на k доказано существование 2-х непересекающихся путей в А.
Пусть Точка С отстоит от А на расстоянии k+1, т е существует B, отстоящая от А на k и прямо соединённая с С.
Существуют неперересекающиеся 2 пути из В в А. Существует путь из С в А, не проходящий через В. Если он не пересекается ни с одним из предыдущих, то всё доказано - берём его и один из этих путей, дополненый веткой СА. Если пересекается, идём по нему из С до 1-ого пересечения с одним из тех путей, а дальше по тому пути, с которым пересеклись. Это один путь. А 2-ой - оставшийся путь из В в А, дополненный веткой СВ.
Путь CA, не проходящий через В , как и любая его часть, может пересекать каждый из двух построенных путей AB. Поэтому, путь, построенный как идём по нему из С до 1-ого пересечения с одним из тех путей, а дальше по тому пути, с которым пересеклись может пересечься с А 2-ой - оставшийся путь из В в А, дополненный веткой СВ.
Разумеется, это при условии, что я правильно понял доказательство..
О Вашем доказательстве я ничего не говорил. Но раз уж Вы спросили..
Serge_P написал(а):
Пусть есть какой-то другой путь из А в В, который не использует С. Пусть он отходит от нашего первоначального пути в точке С1 (до С), и сливается с оным в точке С2 (после С). Докажем, что тогда есть 2 непересекающихся пути из А в С2. (Тут надо картинку рисовать.) Действительно, один идет от А до С1 по первоначальному пути, а далее обходит С. Другой идет до С по пути, не совпадающему с первоначальным (который существует по предположению), а далее идет от С до С2 по первоначальному.
путь из А в В, который не использует С, в том числе и та часть, которая обходит C, может пересекать любой из построенных путей AC.
Поэтому два построенных пути A-C1-C2 и A-C-C2 могут пересечься.
Путь CA, не проходящий через В , как и любая его часть, может пересекать каждый из двух построенных путей AB. Поэтому, путь, построенный как идём по нему из С до 1-ого пересечения с одним из тех путей, а дальше по тому пути, с которым пересеклись может пересечься с А 2-ой - оставшийся путь из В в А, дополненный веткой СВ.
Мне кажется, Вы неправы. Мы же идём до 1-ого пересечения - а дальше по тому пути - и он не пересекается со 2-м. А с веткой СВ не может пересекаться ибо это отрезок.
Мне кажется, Вы неправы. Мы же идём до 1-ого пересечения - а дальше по тому пути - и он не пересекается со 2-м. А с веткой СВ не может пересекаться ибо это отрезок.
Вот это самое от C до 1-ого пересечения и может пересекать. Ведь это часть обходного пути CA, о котором известно только то, что он не проходит через В.
Впрочем, поскольку Вы с Serge_P делаете одно и тоже предположение, то я уже начинаю сомневаться..
путь из А в В, который не использует С, в том числе и та часть, которая обходит C, может пересекать любой из построенных путей AC.
Поэтому два построенных пути A-C1-C2 и A-C-C2 могут пересечься.
Тогда все равно будет 2 пути до С2. Посмотрите на картинку:
