На одном берегу реки находятся 4 человека

Как перевезти гопников и философов с одного берега на другой

Олимпиадная задачка для старшеклассников. Но справитесь ли с ней вы?

Это кавер-версия задачи про волка, козу и капусту — классическую задачу на алгоритмическое мышление. Она очень простая для разработчиков, и если вы можете решить её с первого раза, можете гордиться собой — только 1 человек из 10 решает эту задачу правильно с первого раза.

Зачем уметь решать такие задачи: помогает в составлении сортировочных алгоритмов и успешно проходить собеседования в ИТ-компаниях. Также важно уметь обосновывать свой ход мыслей.

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

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

Для первой поездки есть пять вариантов:

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

Значит, первым рейсом пара «философ-гопник» отправляется на другой берег:

Теперь лодку надо как-то отправить назад. Но так как философ не умеет ей управлять, то он остаётся на берегу, а гопник — возвращается. Философы не взрывают никому мозг:

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

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

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

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

Значит, остаётся только один вариант: отправить в путь двух гопников. В итоге на том берегу всех будет поровну и всё пройдёт спокойно:

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

Поэтому назад отправляются философ и гопник:

Теперь единственный безопасный вариант — отправить на тот берег двух гопников:

Назад отправим одного гопника. Чтобы не выходить из лодки, он позовёт в неё философа (например, фразой «Что вы думаете о солипсизме?») и вернётся с ним обратно на тот берег:

Точно так же забираем оставшегося философа:

И в итоге вся компания оказывается на том берегу, бездонное небо — над головой, а нравственный закон — внутри:

Источник

Разбор задачки о львах и людях: как перевезти всех с одного берега на другой так, чтобы львы не съели людей?

На одной стороне реки находятся три человека и три льва. Все они должны оказаться на другом берегу реки. Есть лишь одна лодка, в которой могут поместиться лишь два живых существа одновременно (человека или льва). Вы не можете оставлять на том или другом берегу реки больше львов, чем людей, так как в этом случае животные съедят людей, оставшихся в меньшинстве. Как вы переправите всех через реку?

Решение

Есть пять возможных вариантов первой поездки: один человек, один лев, человек и лев, два человека, два льва.

Так как львы не могут грести, а лодка сама не поплывет, значит, это исключает варианты с одним и двумя львами. Один и два человека тоже исключается, так как на одном берегу львов станет больше. Поэтому для первой поездки остается только один вариант: в лодке окажутся человек и лев.

Они переправляются на дальний берег.

Но лодка сама вернуться не может. Из этого следует, что человек возвращается вместе с лодкой.

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

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

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

Вместо этого отправляем на другой берег двух людей, поскольку они по численности не уступают львам.

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

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

Отправим обратно только одного человека. Он заберет льва (заманить его в лодку можно куском мяса) и вернется обратно.

Затем один человек возвращается за оставшимся львом.

И наконец, на дальний берег переплывают человек и лев.

Источник

Самые сложные, трудные загадки на логику с ответами

Загадки на логику с подвохом

В чем подвох?

Два отца, два сына нашли три апельсина и разделили их. Каждому досталось по целому апельсину. Как такое может быть? (Ответ — это были дед, отец и сын) На границу России и Китая прилетел петух. Сел точно на границу, абсолютно посредине. Снёс яйцо. Оно упало точно поперек: граница делит его посредине. Какой стране принадлежит яйцо? (Ответ — Петухи не откладывают яйца)

Видео

Короткие загадки на логику друзьям

На внимательность:

Пара лошадей пробежала 20 километров. Вопрос: сколько километров пробежала каждая лошадь в отдельности? (Ответ — 20 км) На столе лежат две монеты, в сумме они дают 3 рубля. Одна из них — не 1 рубль. Какие это монеты? (Ответ — 1 и 2 рубля) Вы вели автобус с 42 пассажирами из Бостона в Вашингтон. На каждой из шести остановок из него выходило по 3 человека, а на каждой второй — по четыре. Как звали водителя, когда водитель через 10 часов прибыл в Вашингтон? (Ответ — у водителя Ваше имя)

Читайте также:  Дальний восток река камчатка

Загадки с подвохом для детей

Начнем с малого и решим 5 загадок для самых маленьких. Взрослым ответ покажется очевидным, а вот ребятам придется подумать (но может быть и наоборот). Чур, не подсказывать!

Загадка №1 Что ты никогда не сможешь съесть на завтрак?

Ответ: Обед и/или ужин.

Загадка №2. Что может путешествовать по свету, оставаясь в одном и том же углу?

Ответ: Почтовая марка.

Загадка №3 В одноэтажном розовом доме жил розовый человек, розовый кот, розовая рыбка, был розовый компьютер, розовое кресло, розовый стол, розовый телефон, розовая душевая кабина – все было розовым! Какого цвета была лестница?

Ответ: В этом доме не было лестницы, потому что это был одноэтажный дом.

Загадка №4 Что настолько же огромное, как слон, но ничего не весит?

Ответ: Тень слона.

Загадка №5 Какое слово в словаре написано неправильно?

Ответ: Это слово «неправильно».

Мы знаем, что вам и вашим детям, как минимум, было интересно. А как максимум – вы серьезно задумались и хотите идти дальше!

Хитрые загадки с подвохом и ответами

Хитрые загадки с подвохом и ответами помогут вам улыбнуться.

Загадка №61

Висит груша – нельзя скушать. Не лампочка.

(Ответ: Чужая груша)

Представьте, что вы плывёте по морю в лодке. Вдруг лодка начинает тонуть, вы оказываетесь в воде, к вам подплывают акулы. Что сделать, чтобы спастись от акул?

(Ответ: Перестать представлять)

Вы сидите в самолете, впереди вас лошадь, сзади автомобиль. Где вы находитесь?

(Ответ: На карусели)

Ползут 3 черепахи.

Первая черепаха говорит: «За мной ползут две черепахи».

Вторая черепаха говорит: «За мной ползёт одна черепаха и передо мной ползёт одна черепаха».

А третья черепаха: «Передо мной ползут две черепахи и за мной ползёт одна черепаха».

Как такое может быть?

(Ответ: Они ползут по кругу)

Как правильно? Пять плюс семь будет «одиннадцать» или «адиннадцать»?

В комнате было 12 цыплят, 3 кролика, 5 щенят, 2 кошки, 1 петух и 2 курицы.

Сюда зашёл хозяин с собакой. Сколько в комнате стало ног?

(Ответ: 2, остальные — лапы)

Богатый купец, умирая, оставил своим сыновьям в наследство стадо из 17 коров. Всего у купца было 3 сына. В завещании указано распределить наследство следующим образом: старший сын получает половину всего стада, средний сын должен получить треть всех коров из стада, младший сын должен получить девятую часть от стада. Как же братьям поделить между собой стадо согласно условию завещания?

(Ответ: Необходимо взять еще одну корову, тогда старший сын получит девять коров, средний шесть и младший две коровы. Итак – 9 + 6 + 2 = 17. Оставшуюся корову нужно вернуть)

Какой ключ не может ни открыть, ни бить?

Могут ли на яблоне быть яйца?

(Ответ: Да, в птичьем гнезде)

На столе лежали три огурца и четыре яблока. Ребенок взял со стола одно яблоко. Сколько фруктов осталось на столе?

На руках десять пальцев. Сколько пальцев на десяти руках?

Что может в одно и то же время: стоять и ходить, висеть и стоять, ходить и лежать?

Эту загадку часто предлагают детям. Но иногда взрослые могут долго ломать голову, чтобы догадаться, как решить такую задачку, поэтому можно устроить конкурс: предложить всем желающим попытаться решить задачку. Тот, кто догадается, независимо от возраста, заслуживает приз. Вот задача:

6589 = 4; 5893 = 3; 1236 = 1; 1234 = 0; 0000 = 4; 5794 = 1; 1111 = 0; 4444 = 0; 7268 = 3; 1679 = 2; 3697 = 2 2793 = 1; 4895 = 3

(Ответ: Главное – смотреть на задачу по-детски, тогда вы поймёте, что ответ 3 (три кружочка в записи цифр)

Вы участвуете в марафоне и обогнали бегуна, бежавшего последним. Какую позицию вы теперь занимаете?

(Ответ: Это невозможно, ведь он — последний)

Шла женщина в Москву, а навстречу – три мужика. У каждого по мешку, в каждом мешке по кошке. Сколько существ направлялось в Москву?

Источник

Решение задач математики и информатики с помощью графов

Впервые основы теории графов появились в 1736 г. в работе Леонарда Эйлера, где он описывал решения головоломок и математических развлекательных задач. Широкое развитие теория графов получила с 50-х гг. ХХ в. в связи со становлением кибернетики и развитием вычислительной техники. Итак, дадим определение графа.

Графом в математике называется конечная совокупность точек, именуемых вершинами; некоторые из них соединены друг с другом линиями, называемыми ребрами графа. Существует несколько разновидностей графов: ориентированный граф(орграф), неориентированный граф и взвешенный граф.

Ориентированный граф-это граф, рёбрам которого присвоено направление.

Неориентированный граф-это граф, в котором нет направлений линий.

Взвешенный граф-это граф, рёбра которого имеют «вес», то есть длину.

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

Решение задач с помощью графов

Теперь переедем от теории к практике и рассмотрим применение графов к решению задач.

Аркадий, Борис. Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано?

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

Если подсчитать число ребер графа, изображенного на рисунке, то это число будет равно количеству совершенных рукопожатий. Как видно, их 10.

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

Определите профессию каждого из друзей

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

Будем выделять два вида рёбер: красного и чёрного цвета. Красные рёбра будут обозначать, что данный человек не может иметь выбранную профессию, а чёрные рёбра будут означать, что это профессия данного человека. Если от одной вершины уже выходить три красных ребра, то четвёртое обязательно должно быть чёрным.

Итого, из графа получается, что Андрей-шофёр, Сергей-слесарь, Николай-электрик, Вадим-токарь.

Ответ : Андрей-шофёр, Сергей-слесарь, Николай-электрик, Вадим-токарь

На пришкольном участке растут 8 деревьев: яблоня, тополь, береза, рябина, дуб, клен, лиственница и сосна. Рябина выше лиственницы, яблоня выше клена, дуб ниже березы, но выше сосны, сосна выше рябины, береза ниже тополя, а лиственница выше яблони. Расположите деревья от самого низкого к самому высокому.

В данной задаче есть два типа отношений «выше» и «ниже», поэтому для её решения будем применять ориентированный граф. Направление рёбер выберем следующим образом: стрелки будут иметь направление от более высокого дерева к более низкому..

Читайте также:  Река вазуза что водится

Ответ : Клен, яблоня, лиственница, рябина, сосна, дуб, береза и тополь.

У Наташи есть 2 конверта: обычный и авиа, и 3 марки: прямоугольная, квадратная и треугольная. Сколькими способами Наташа может выбрать конверт и марку, чтобы отправить письмо?

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

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

Ответ : 6 способов

Задача 5

На рисунке представлена схема соединений, связывающих пункты A , F , G , B , E , C , D . По каждому соединению можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из пункта A в пункт D ?

Перестроим данный ориентированный граф в виде дерева.

Итого, получаем 5 возможных путей из пункта А в пункт D .

Между населенными пунктами A , B , C , D , E построены дороги. Необходимо определить длину кратчайшего пути между пунктами А и Е. Передвигаться можно только по дорогам, протяжённость которых представлена в таблице.

Перед нами взвешенный граф, представленный в виде таблицы, перестроим его в виде схемы.

Из рисунка видно, что длина кратчайшего пути между пунктами А и Е равна 6(путь АВСЕ).

В первенстве класса по настольному теннису 6 участников: Андрей, Борис Виктор, Галина, Дмитрий и Елена. Первенство проводят по круговой системе – каждый из участников играет с каждым из остальных один раз. К настоящему моменту некоторые игры уже проведены: Андрей сыграл с Борисом, Галиной и Еленой; Борис – с Андреем, Галиной; Виктор – с Галиной, Дмитрием и Еленой; Галина – с Андреем, Виктором и Борисом. Сколько игр проведено к настоящему моменту и сколько еще осталось?

Построим граф, вершинами которого будут являться участники турнира. Красным цветом обозначим те партии, которые были сыграны, а чёрным-все оставшиеся свободные партии.

Получаем, что сыграно было 7 партий, а осталось сыграть 8.

Ответ : проведено 7 игры, осталось 8.

Задача 8

Четыре острова соединены между собой и с берегами реки 14 мостами так, как это показано на рисунке. Можно ли за одну прогулку обойти все эти мосты, побывав на каждом из них один раз?

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

Ответ : да, можно

Рукава реки Прегель, на берегу которой расположен город Кенигсберг, образовывали два острова. В эту эпоху четыре образовавшихся участка суши (правый и левый берег и два острова) соединяло семь мостов так, как это показано на рисунке. Горожане, гуляя по городу, пытались составить маршрут, чтобы он проходил по каждому мосту ровно один раз.

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

Ответ : данный маршрут невозможен

Муха забралась в банку из-под сахара. Банка имеет форму куба. Сможет ли муха последовательно обойти все 12 ребер куба, не проходя дважды по одному ребру? Подпрыгивать и перелетать с места на место не разрешается

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

Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Вене; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс и Марс – Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса ?

Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями.

Теперь сразу видно, что долететь с Земли до Марса нельзя.

Вы наверняка сталкивались с задачами, в которых требуется нарисовать какую-либо фигуру не отрывая карандаш от бумаги и проводя каждую линию только один раз. Оказывается, что такая задача не всегда разрешима, т.е. существуют фигуры, которые указанным способом нарисовать нельзя. Вопрос разрешимости таких задач также входит в теорию графов. Впервые его исследовал в 1736 году великий немецкий математик Леонард Эйлер, решая задачу о Кенигсбергских мостах. Поэтому графы, которые можно нарисовать указанным способом, называются Эйлеровыми графами.

Рассмотрим одну из таких задач

Задача 12

Можно ли нарисовать изображенный на рисунке граф не отрывая карандаш от бумаги и проводя каждое ребро ровно один раз ?

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

4 человека из нашего класса захотели поздравить друг друга с новым годом. Сделать это решили с помощью SMS-ок. Сколько всего SMS-ок было отправлено?

Клоуны Бам, Бим, Бом вышли на арену в красной, синей и зеленой рубашках. Их туфли тоже были этих трех цветов. Туфли и рубашка Бима были одного цвета. На Боме не было ничего красного. Туфли Бама были синие, а рубашка нет. Каких цветов были туфли и рубашка у Бома и Бима?

Рубашка Бама синяя, а Бома — зелёная. Туфли Бома не могут быть ни красными, ни зелёными (ибо зелёные туфли у Бама). Поскольку туфли Бама зелёные, то туфли Бома не могут быть ни красными, ни зелёными. Значит, они синие. Биму остаются красные туфли. Поэтому и рубашка у него красная. Тогда рубашка Бама синяя, а Бома — зелёная. Изобразим с помощью графа

Ответ : Бом – синяя рубашка и зеленые туфли. Бам – зеленая рубашка и синие туфли.

В школьной столовой на первое можно заказать щи, суп и борщ, на второе – котлету и рыбу, а на третье – чай и морс. Сколько различных обедов можно составить из указанных блюд?

Ответ : 12 обедов

Жила-была одна дружная семья: мама, папа и сын. Они все любили делать вместе. Но вот мультфильмы любили разные: «Ну, погоди!», «Покемоны», «Том и Джерри». Определите, какой мультфильм любит каждый из них, если мама, папа и любитель мультфильма «Покемоны» никогда не унывают, а папа и любитель мультфильма «Том и Джерри» делают зарядку по утрам?

Рассмотрим множество людей: мама, папа, сын и множество мультфильмов «Ну, погоди!», «Покемоны», «Том и Джерри». Обозначим элементы этих двух множеств точками

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

Из условия задачи следует, что нужно найти единственно возможное соответствие между элементами двух множеств.

Поэтому граф на рисунке будет выглядеть следующим образом:

Ответ: папа любит мультфильм «Ну, погоди!», сын – «Покемоны», а мама любит мультфильм «Том и Джерри».

Читайте также:  Где отдохнуть с палаткой на реке битюг

Во дворе, который окружен высоким забором, находятся три домика:

красный, желтый и синий. В заборе есть три калитки: красная, желтая и

синяя. От красного домика проведите дорожку к красной калитке, от желтого

домика – к желтой калитке, от синего – к синей так, чтобы эти дорожки не

Четыре одноклассника — Володя, Толя, Оля и Сережа выбраны классным собранием для работы в шефском, культурно-массовом, спортивном и учебном секторах школы. Определите, кого из ребят в какой из названных секторов выбрали, если известно, что:

1) Володя и культсектор живут в одном доме, и они вместе с Олей втроем ездят в школу на автобусе;

2) на классном собрании было решено в спортсектор избрать мальчика;

3) учебный сектор и Сережа вместе ходят на теннисный корт;

4) спортсектор и Володя — большие друзья;

5) Оля сидит за одной партой с учебным сектором.

Составим граф из множества ребят и множества секторов

Ответ: Володя — учебный сектор, Толя — культмассовый сектор, Оля-шефский сектор, Серёжа – спортивный сектор.

В пяти корзинах лежали яблоки пяти разных сортов. Яблоки первого сорта лежат в корзинах Г и Д; яблоки второго сорта — в корзинах А, Б, Г; в корзинах А, Б, В имеются яблоки пятого сорта, в корзине В имеются к тому же яблоки четвертого сорта, а в корзине Д — третьего. Пронумеруйте каждую корзину так, чтобы в корзине №1 были яблоки первого сорта (хотя бы одно); в корзине №2 — второго и т.д.

Ответ: №1 — Г; №2 — А или №2 — Б; №3 — Д; №4 — В; №5 — Б или №5 — А.

В стране Семёрка 15 городов, каждый из которых соединён дорогами не менее, чем с семью другими. Докажите, что из каждого города можно добраться до любого другого (возможно, проезжая через другие города).

Рассмотрим два произвольных города и предположим, что они не соединены путем, то есть такой последовательностью дорог, в которой начало очередной дороги совпадает с концом предыдущей. Каждый из этих двух городов по условию соединен не менее, чем с семью другими; при этом все упомянутые города различны – ведь если какие-то два из них совпадают, то есть путь, соединяющий исходные города. Таким образом, мы насчитали не менее 16 городов. Противоречие.

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

Общее количество «втекающих» рек должно быть равно общему количеству «вытекающих» рек. То есть возникает противоречие.

Несколько Совершенно Секретных Объектов соединены подземной железной дорогой таким образом, что каждый Объект напрямую соединён не более чем с тремя другими и от каждого Объекта можно добраться под землей до любого другого, сделав не более одной пересадки. Каково максимальное число Совершенно Секретных Объектов?

Из данного Объекта можно добраться за один «ход» до трёх Объектов, а с пересадкой – еще до 2·3 = 6 Объектов. Следовательно, Объектов не больше 10. Пример такого графа с 10 объектами изображен на рисунке.

Ответ : 10 объектов

Иван-Царевич спешит выручить Марью-Царевну из плена Кощея. В таблице указана протяжённость дорог между пунктами, через которые он может пройти. Укажите длину самого длинного участка кратчайшего пути от Ивана-Царевича до Марьи-Царевны (от точки И до точки М). Передвигаться можно только по дорогам, указанным в таблице:

Построим граф, соответствующий данной таблице

Учитель Иван Петрович живёт на станции Антоновка, а работает на станции Дружба. Чтобы успеть с утра на уроки, он должен ехать по самой короткой дороге. Проанализируйте таблицу и укажите длину кратчайшего пути от станции Антоновка до станции Дружба:

Построим граф, соответствующий данной таблице

Сельская малокомплектная школа находится в поселке Вершки. Петя Орлов живёт в деревне Дальнее. Определите, какое минимальное расстояние ему надо пройти, чтобы добраться до школы:

Построим граф, соответствующий данной таблице

На схеме нарисованы дороги между четырьмя населёнными пунктами A, B, C, D и указаны протяжённости данных дорог.

Определите, какие два пункта наиболее удалены друг от друга (при условии, что передвигаться можно только по указанным на схеме дорогам). В ответе укажите кратчайшее расстояние между этими пунктами.

Заметим, что наиболее удалены друг от друга пункты A и D. Найдём все варианты маршрутов из A в D и выберем самый короткий.

A—B—D: длина маршрута 13 км.

A—C—D: длина маршрута 15 км.

A—B—C—D: длина маршрута 23 км.

A—C—B—D: длина маршрута 17 км.

Заметим, что кратчайшее расстояние между пунктами A и D равняется 13.

На рисунке— схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, К, Л, М, Н, П. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город П, проходящих через город Л?

Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х. При этом, если путь не должен проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. А если город, наоборот, обязательно должен лежать на пути, тогда для городов, в которые из нужного города идут дороги, в суммах нужно брать только этот город. С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов:

А = 1. Б = А = 1. Г = А + Б = 2. Д = А = 1. В = Б + Г = 3. Е = Г + Д = 3.

Ж = В + Г + Е = 8. К = Ж + В = 11. Л = Ж + К= 19. Н = Д + Ж = 9.

М = Л = 19 (Ж и Н не учитываем, поскольку путь должен проходить через Л). П = Л + М = 38 (К не учитываем, поскольку путь должен проходить через Л).

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из пункта А в пункт К, не проходящих через пункт В?

Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х.

При этом, если путь не должен проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. А если город, наоборот, обязательно должен лежать на пути, тогда для городов, в которые из нужного города идут дороги, в суммах нужно брать только этот город.

С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов:

А = 1. Б = А = 1. Г = А = 1. Д = Б = 1.

Е = Д = 1 (В не учитываем, поскольку путь не должен проходить через город В).

Ж = Д = 1. И = Г + Е = 2. К = Ж + Е + И + Д = 5.

Для графов,представленных на рисунке, укажите количество вершин и количество рёбер.

Источник

Поделиться с друзьями
Байкал24