Номера трамвайных маршрутов обозначают двумя. Использование математических методов в коммерческой деятельности: Контрольные работы. Правила суммы и произведения

Задачи по комбинаторике

Наименование параметра	Значение
Тема статьи:	Задачи по комбинаторике
Рубрика (тематическая категория)	Математика

1. Расписание одного дня содержит 5 уроков. Определить количество таких расписаний при выборе из одиннадцати дисциплин.

Ответ˸ 55 440.

2. Комиссия состоит из председателя, ᴇᴦο заместителя и ещё пяти человек. Сколькими способами члены комиссии могут распределять между собой обязанности?

Ответ˸ 42.

3. Сколькими способами можно выбрать трех дежурных из группы в 20 человек?

Ответ˸ 1 140.

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

Ответ˸ 968.

5. В вазе стоят 10 красных и 5 розовых гвоздик. Сколькими способами можно выбрать из вазы пять гвоздик одного цвета?

Ответ˸ 253.

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

Ответ˸ 64.

7. Чемпионат, в котором участвуют 16 команд, проводится в два круга (т.е. каждая команда дважды встречается с любой другой). Определить, какое количество встреч следует провести.

Ответ˸ 240.

8. Замок открывается только в том случае, в случае если набран определенный трехзначный номер.
Размещено на реф.рф
Попытка состоит в том, что набирают наугад три цифры из заданных пяти цифр.
Размещено на реф.рф
Угадать номер удалось только на последней из всех возможных попыток. Сколько попыток предшествовало удачной?

Ответ˸ 124.

9. Из группы в 15 человек выбирают четырех участников эстафеты 800+400+200+100. Сколькими способами можно расставить спортсменов по этапам эстафеты?

Ответ˸ 32 760.

10. Команда из пяти человек выступает на соревнованиях по плаванию, в которых участвуют ещё 20 спортсменов. Сколькими способами могут распределиться места, занятые членами этой команды?

Ответ˸ 25!/20!.

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

Ответ˸ 3 126.

12. Две ладьи различного цвета расположены на шахматной доске так, что каждая может взять другую. Сколько существует таких расположений?

Ответ˸ 896.

13. Порядок выступления восьми участников конкурса определяется жребием. Сколько различных исходов жеребьевки при этом возможно?

Ответ˸ 8!.

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

Ответ˸ 30!/(10!) .

15. Сколько четырехзначных чисел, делящихся на 5, можно составить из цифр 0, 1, 3, 5, 7, в случае если каждое число не должно содержать одинаковых цифр?

Ответ˸ 42.

16. Сколько различных светящихся колец можно сделать, расположив по окружности 10 разноцветных лампочек (кольца считаются одинаковыми при одинаковом порядке следования цветов)?

Ответ˸ 9!.

17. На книжной полке помещается 30 томов. Сколькими способами их можно расставить, чтобы при этом первый и второй тома не стояли рядом?

18. Четыре стрелка должны поразить восемь мишеней (каждый по две). Сколькими способами они могут распределить мишени между собой?

Задачи по комбинаторике - понятие и виды. Классификация и особенности категории "Задачи по комбинаторике" 2015, 2017-2018.

1. Решить задачу

1. Сколькими способами можно выбрать двух дежурных из группы в 24 человека?

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

3. Из 20 спортсменов выбирается команда на соревнование по плаванию в количестве 5-ти человек. Сколько различных команд можно составить?

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

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

6. Сколькими способами можно выбрать двух студентов из группы в 15 человек?

7. Сколькими способами можно распределить три призовых места среди 20 спортсменов?

8. Из группы студентов 20 человек выбирают старосту и заместителя. Сколько вариантов такого выбора возможно?

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

10. Контрольная работа содержит 5 задач. Сколько вариантов можно составить при выборе из 20 задач?

2. Решить задачу

1. В группе 15 девушек и 11 парней. Случайным образом выбирают одного студента. Какова вероятность, что это юноша?

2. На карточках написаны буквы У, Ч, Е, Б, Н, И, К. Карточки перемешиваются и раскладываются в ряд. Какова вероятность того, что получится слово Учебник?

3. На карточках написаны буквы м, а, т, е, м, а, т, и, к, а. Берут подряд четыре карточки. Какова вероятность, что при этом получится слово тема ?

4. Среди 20 студентов группы, в которой 8 девушек, составляется команда для соревнований из 6 участников. Какова вероятность, что в команде окажутся 2 девушки?

5. Из 15 книг, стоящих на полке 10 по теории вероятностей. Найти вероятность того, что среди 5 взятых с полки книг три по теории вероятностей.

6. В ящике находятся 10 красных, 5 голубых и 5 белых шаров. Наудачу вынимают 4. Какова вероятность того, что среди них окажутся 2 красных, 1 голубой и 1 белый шар?

7. В бригаде 4 женщины и три мужчины. Среди членов бригады разыгрываются 4 билета в театр. Какова вероятность, что среди обладателей билетов окажутся две женщины?

8. Из партии, содержащей 10 изделий, среди которых три бракованных, наудачу извлекают три изделия. Найти вероятность того, что в полученной выборке одно изделие бракованное?

9. Из 10 билетов выигрышными являются два. Чему равна вероятность того, что среди взятых наудачу пяти билетов один выигрышный?

10. На шести одинаковых карточках написаны буквы л, м, о, о, о, к. Эти карточки наудачу разложены в ряд. Какова вероятность, что получится слово молоко ?

3. Решить задачу

1. Три стрелка независимо друг от друга стреляют по цели. Вероятность попадания для первого стрелка равна 0,75; для второго – 0,8; для третьего – 0,9. найти вероятность того, что все три стрелка одновременно попадут в цель.

2. Спортсмен стреляет по мишени. Вероятность попадания в первый сектор при этом равна 0,4, а во второй – 0,3. Какова вероятность того, что спортсмен попадет в один из секторов?

3. Каждое из четырех несовместных событий может произойти соответственно с вероятностями 0,014, 0,011, 0,009, 0,006. Найти вероятность того, что в результате опыта произойдет хотя бы одно из этих событий.

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

5. В ящике 6 белых и 8 черных шаров. Из ящика вынули два шара (без возвращения). Найти вероятность того, что оба шара белые.

6. При работе с тремя аппаратами вероятность выхода из строя первого равна 0,6, второго – 0,72, третьего 0,8. Какова вероятность того, что все три аппарата одновременно выйдут из строя?

7. В классе 10 мальчиков и 15 девочек. Нужно выбрать делегацию из двух человек. Какова вероятность, что это будут мальчик и девочка?

8. В вазе 12 красных и 9 белых роз. Наудачу составляют букет из трех цветов. Какова вероятность, что все розы красного цвета?

9. Завод изготавливает продукции первого сорта 50%, а высшего 30%. Какова вероятность, что случайно взятое изделие первого или высшего сорта?

10. Вероятности попадания каждого из трех выстрелов соответственно равны 0,9, 0,8, 0,7. Найти вероятность попадания двух выстрелов.

4. Решить задачу

1. При механической обработке станок обычно работает в двух режимах: рентабельном и нерентабельном. Рентабельный режим наблюдается в 80% из всех случаев работы, нерентабельный – в 20%. Вероятность выхода из строя за время t работы в рентабельном режиме равна 0.1, в нерентабельном – 0,7. Найти вероятность выхода станка из строя за время t

2. Две перфораторщицы набили по одинаковому комплекту перфокарт на разных перфораторах. Вероятность того, что первая перфораторщица допустит ошибку, равна 0,05; для второй эта вероятность равна 0,1. При сверке перфокарт была обнаружена ошибка. Найти вероятность того, что ошиблась первая перфораторщица

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

4. На фабрике на машинах трех видов производят соответственно 25, 35 ,40% всех изделий. В их продукции брак составляет соответственно 5,4 и 2%. Найти вероятность того, что случайно выбранное изделие фабрики будет дефектно.

5. Однотипные приборы выпускаются тремя заводами в количественном отношении , причем вероятности брака для этих заводов соответственно равны 3%, 2%, 1%. Прибор, приобретенный НИИ, оказался бракованным. Какова вероятность того, что прибор произведен первым заводом?

6. Партия деталей изготовлена тремя рабочими, причем первый изготовил 35% всех деталей, второй 40%, третий всю остальную часть продукции. Брак в их продукции составляет: у первого 2%, у второго -3%, у третьего 4%. Случайно выбранная для контроля деталь оказалась бракованной. Найти вероятность того, что она изготовлена третьим рабочим.

7. В продажу поступила партия запасных деталей, произведенных на двух станках. Причем, 70% продукции произведено на первом станке. Среди деталей, произведенных первым станком 4% бракованных, вторым -1%. Найти вероятность того, что купленная покупателем деталь оказалась бракованной.

8. Безаварийная работа объекта обеспечивается тремя сигнализаторами. Вероятности того, что первым отказом будет отказ 1, 2, 3 сигнализатора равны . В каждом из этих случаев может произойти авария с вероятностями 0,04; 0,03; 0,012. Найти вероятность аварии при первом отказе какого либо сигнализатора.

9. В некотором вузе 75% юношей и 25 % девушек. Среди юношей курящих 20%, среди девушек 10%. Наудачу выбранное лицо оказалось курящим. Какова вероятность, что это юноша?

10. В торговую фирму поступили телевизоры от трех поставщиков: 10% от первого, 40% от второго и 50% от третьего. Практика показала, что телевизоры, поступающие от первого, второго и третьего поставщиков не потребуют ремонта в течении гарантийного срока соответственно в 98%, 88%, 92% случаев. Найти вероятность того, что поступивший в торговую фирму телевизор не потребует ремонта в течении гарантийного срока.

5. Решить задачу

1. Вероятность попадания в мишень при одном выстреле для данного стрелка 0,7 и не зависит от номера выстрела. Найти вероятность того, что при 5 выстрелах произойдет ровно 2 попадания в мишень.

2. Подбрасывается 5 симметричных монет. Найти вероятность того, что выпало ровно 2 герба.

3. Вероятность попадания в мишень при одном выстреле для данного стрелка 0,7 и не зависит от номера выстрела. Найти вероятность того, что при 7 выстрелах произойдет ровно 3 попадания в мишень.

4. Подбрасывается 5 симметричных монет. Найти вероятность того, что выпало более 2 гербов.

5. Всхожесть семян растения равна 90%. Найти вероятность того, что из четырех семян взойдут три.

6. . Монету подбрасывают 10 раз. Какова вероятность того, что герб выпадет 4 раза.

7. В семье трое детей. Какова вероятность того, что все они мальчики. Вероятность рождения мальчика 0,51

8. Всхожесть семян растения равна 90%. Найти вероятность того, что из пяти посеянных семян взойдут меньше трех.

9. В семье 6 детей. Какова вероятность того, что среди них не более 2-х девочек. Вероятность рождения мальчика 0,51.

10. Всхожесть семян растения равна 90%. Найти вероятность того, что из пяти посеянных семян взойдут не менее трех.

6. Решить задачу

1. Вероятность появления события равна 0,7 в каждом из 2100 независимых испытаний. Найти вероятность появления события не менее 1470 и не более 1500 раз.

2. Найти вероятность того, что среди 500 новорожденных окажется от100 до 200 мальчиков. Вероятность рождения мальчика принять 0,51.

3. Вероятность рождения девочки 0,49. Найти вероятность того, что среди 100 новорожденных будет 50 девочек.

4. Вероятность появления события в каждом из 300 независимых испытаний постоянна и равна 0,7. Найти вероятность появления события не менее 150 раз.

5. . Завод отправил в торговую сеть 500 изделий. Вероятность повреждения изделия в пути равна 0,002. Найти вероятность того, что при транспортировке будет повреждено более 3-х изделий

6. Обувной магазин продал 200 пар обуви. Вероятность того, что в магазин будет возвращена бракованная пара, равна 0,01. Найти вероятность того, что из проданных пар обуви будет возвращено более трех.

7. Учебник издан тиражом 100000 экземпляров. Вероятность того, что учебник сброшюрован неправильно, равна 0,0001. Найти вероятность того, что тираж содержит ровно 5 бракованных книг.

8. Обувной магазин продал 200 пар обуви. Вероятность того, что в магазин будет возвращена бракованная пара, равна 0,01. Найти вероятность того, что из проданных пар обуви будет возвращено не более трех.

9. Найти вероятность того, что событие А наступит в 2000 испытаниях 1000 раз. Вероятность появления события А в каждом испытании равна 0,6.

10. Вероятность поражения мишени при одном выстреле равна 0,85. Найти вероятность того, что при 90 выстрелах мишень будет поражена 50 раз.

7. Дискретная с.в. X задана законом распределения

Требуется:

1) построить функцию распределения,

2) найти математическое ожидание,

4) дисперсию,

5) среднее квадратическое отклонение,

6) коэффициент вариации,

7) коэффициент асимметрии

Х	-4	-2
Р	0,3	?	0,1	0,1	0,1

Х
Р	0,5	0,1	0,1	?

Х
Р	0,3	?	0,1	0,1	0,2

Х	-1
Р	0,1	?	0,3	0,1	0,1

Х
Р	0,1	0,1	?	0,2	0,2

Х	-10
Р	0,2	0,1	?	0,2	0,3

Х
Р	0,1	0,2	0,3	?	0,1

Х	-3	-1
Р	0,3	0,2	?	0,1	0,1

Х
Р	0,3	0,1	0,1	?	0,2

Х
Р	0,1	0,2	0,1	0,2	?

8. Непрерывная с.в.Х задана плотностью распределения вероятностей. Требуется.

Омнибус N 9-10 2007 год.

Морская душа маршрутных огней.

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

Ещё совсем в недавнее время существовала традиция давать трамвайным маршрутам не только цифровое, но и цветовое обозначение - маршрутные огни зажигались по обе стороны от номера маршрута, спереди и сзади вагона. Улицы с трамвайным движением отличались особой, праздничной нарядностью, по маршрутным огням ориентировались в трамвайном потоке водители, пассажиры, путевые рабочие, диспетчеры и стрелочники, многие не представляли себе трамвая без цветных огней. Московская система маршрутных огней был построена на однозначном соответствии цифры и цвета. "1" - всегда красный цвет, "2" - зелёный, "5" - оливковый, "7" - голубой и так далее. А вот в Ленинграде огни "говорили" на другом языке, и их чтение "по-московски" чаще всего приводило к бессмыслице, так как огней было не 10, как в Москве, а только пять. Они хорошо различались, а их сочетания выглядели всегда очень красиво. Однако из пяти огней возможны 25 разных сочетаний по два, в то время как маршрутов в Петербурге-Ленинграде со временем стало около 70, поэтому знаки маршрутов могли повторяться. Например, два белых - 9, 43; красный и жёлтый - 1, 51, 64; синий и красный - 33, 52, 54; два красных - 5, 36, 39, 45, 47. И только маршрут N 20 обозначался по московской и питерской системе одинаково: зелёный и белый.
Бывало, что маршрутные огни в Петербурге менялись. Если случалось так, что после изменения одного из маршрутов он работал на достаточно протяжённом участке с другим маршрутом, имеющим такие же цвета, то у одного из этих маршрутов приходилось изменять состав огней.
Маршрут N 4 раньше ходил от острова Декабристов до Волкова кладбища и обозначался двумя жёлтыми (оранжевыми) огнями. Потом маршрут закрыли и под тем же номером открыли в другом месте с другими огнями: синий + синий, поскольку он имел общий участок с 35-м трамваем (два жёлтых).
Маршрут N 43 изначально имел огни: красный + белый. При продлении в порт в 1985 году огни изменились: белый + белый, так как маршрут стал иметь общий участок с трамваем N 28 (красный + белый). 3-й маршрут обозначался зелёным и белым цветами. При восстановлении огней в 2007 году сочетание заменено на жёлтый + зеленый. Тогда же изменились сочетания и на ряде других маршрутов: 48 (было: белый + белый, стало: синий + синий); 61 (было: белый + белый, стало: белый + желтый) и т.п.
Петербургская система маршрутных огней, такая простая внешне и такая запутанная, связана с традицией прежде всего европейских трамвайных городов. Так, уже в 1907 году в письме в газету "Новое время" содержится просьба от "обывателей Васильевского острова" ввести на трамваях цветные фонари, "как за границей, в частности во Франкфурте-на-Майне". В настоящее время сохранились остатки былых систем в виде цветной подсветки по диагонали на маршрутных указателях трамваев в Амстердаме. Эта традиция, в свою очередь, вероятно, восходит к огням морской навигации. Почему именно к морским, а не, скажем, к железнодорожным? Да потому, что маршрутные огни, как и морские, никому ничего не запрещают, не заставляют, а просто помогают сориентироваться в тёмное время суток.
Огни морской навигации расшифровываются в специальных морских книгах - лоциях морей. Так же и маршрутные огни описываются в городских путеводителях. Первым из них был "Передвижной путеводитель санкт-петербургских трамваев", выпущенный издательством Э.И. Маркуса (1910).
Состав цветов, применяемых в петербургских маршрутных огнях (белый, красный, оранжевый или жёлтый, зеленый, синий), мало отличается от цветов морских огней (белый, красный, оранжевый, зеленый, синий, фиолетовый).
Присмотревшись, можно найти и другие черты сходства, но гораздо важнее понять, почему в расчётливом Петербурге прижилась такая нестрогая система маршрутных огней, требующая постоянной корректировки. Ответ прост: ведь Петербург - приморский город, и ему в равной степени свойственны и строгость архитектурных форм и легкомыслие карнавала, а значит, и весёлое разноцветье маршрутных огней.
В 2007 году традиция вышла на новый виток. Теперь на вагонах устанавливают светодиодные лампы для маршрутных огней. Они будут светить не только в вечерних сумерках, но и при свете дня.

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

Ответы:

формула будет такая: 8²=64 64 различных маршрутов.

Похожие вопросы

Вспомните архитектурные постройки и скульптуры Возрождения, имеющие нечто сходное с собором Возрождения, и статуей Вероккио. Запишите их названия.
Вставьте вместо пропусков порядковые номера соответствующих слов из предложенного списка. Слова даны в списвке в единственном числе, в именительном падеже. ОБРАТИТЕ ВНИМАНИЕ: в списке слов больще, чем пропусков в тексте! Большое распространение в _____ получила классификация, выделяющая в зависимости от оснований и условий приобретения ____ членства кадровые в ____ партии. Первые отличаются тем, что они формируются вокруг группы политических ___, а основой их стровения является комитет активистов. Кадровые партии формируются обычно "сверху" на базе различных ___ фракций, объединений партийной бюрократии. Такие партии обычно активизируют свою деятельность только на время ___. Другие партии представляют собой централизованные, хорошо дисциплинированные организации. Большое значение в них придается ___ единству членов партии. Такие партии чаще всего формируются "снизу", на основе профсоюзных и иных ___ движений, отражающих интересны различный соц. групп 1)Социология 10) выборы 2)общественный 11) норма 3фактор 12) партийный 4)избирательный 13) парламентский 5)национальный 14)консенсус 6) социум 15) идиологический 7) массовый 16) система 8) импичмент 17) лидер 9) политология
№1 Решить: 28/5*4 №2 На координатной прямой отмечено число а _______o____|___|___|___________> a -1 0 1 1) a; a -1;\frac{1}{a} 2) a;\frac{1}{a};a-1 3) a-1;\frac{1}{a};a 4)a-1;a;\frac{1}{a}
является ли число 2008*2011*2012*2014+1 точным квадратом
В новопостроенном доме 300квартир.В первый день заселили 120 квартир,во второй - третью часть остатка.Сколько квартир осталось заселить?
Толик умножил пятизначное число на сумму его цифр. Потом Толик умножил результат на сумму его (результата) цифр. Удивительно, но получилось опять пятизначное число. Какое число Толик умножил в первый раз? (Найдите все возможные варианты ответа.)

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

3. Сколькими способами можно выбрать трех дежурных из группы в 20 человек.

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

5. В вазе стоят 10 красных и 5 розовых гвоздик. Сколькими способами можно выбрать из вазы пять гвоздик одного цвета.

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

7. Из группы в 15 человек выбирают четырех участников эстафеты 800+400+200+100. Сколькими способами можно расставить спортсменов по этапам эстафеты.

8. Команда из пяти человек выступает на соревнованиях по плаванию, в которых участвуют еще 20 спортсменов. Сколькими способами могут распределиться места, занятые членами этой команды.

9. Из группы в 12 человек ежедневно в течение 6 дней выбирают двух дежурных. Определить количество различных списков дежурных, если каждый человек дежурит один раз.

Вопросы для обсуждения на форуме

1. Решение задач комбинаторики.

Список дополнительной литературы:

1. Горбатов В.А. Фундаментальные основы дискретной математики. М.: Высшая школа, 2000. – 544с.

2. Кофман В. А. Введение в прикладную комбинаторику. М.: Радио и связь, 1982. 431с.

Семинар №7.Теория графов

Цель семинара:

Рассмотреть вопросы, связанные с практическим применением теории графов в принятии решений.

План занятия:

Семина посвящен теории графов. Первой рассматривается тема основные понятия и операции на графах, затем тема посвященная маршрутам и деревьям. На семинар отводится 2 часа.

Задача 1. На рис.7.1 изображены графы - с четырьмя вершинами в каждом. Сравнить графы.

Рис. 7.1. Графы -

Решение .

Результаты сравнения графов таковы:

Неориентированные;

Ориентированные;

Полные, причем = ;

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

Все вершины этого графа являются изолированными (граф с пустым множеством ребер, т.е. 0);

И являются дополнением друг к другу: = и = ;

Мультиграф, так как содержит кратные ребра a и b , а также e и f ;

Ориентированный, канонически соответствующий неориентированному графу ;

И не является равными, так как имеют отличающиеся ребра (4,1) - и (1,4) в ;

Ориентированный мультиграф: ребра a и b – кратные, тогда как мультиграфом не является, поскольку в нем ребра a и b различно ориентированы.

Задача 2. Чему равны степени вершин графов , на рис.7.2.

Рис. 7.2. Графы и

Решение .

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

Где m =7 – число ребер графа.

Степени вершин ориентированного графа :

Суммы степеней вершин первого и второго типа графа совпадают и равны числу m ребер графа: .

Задача 3. На рис. 7.3 изображен сетевой граф (сетевая модель) выполнения комплекса операций (работ) некоторой программы. В нем стрелки обозначают операции, вершины – события, характеризующие окончание одних работ и начало других. Направленность стрелок отражает последовательность наступления этих событий. Задать сетевой граф различными способами.

Рис. 7.3. Сетевой граф

Решение .

Изображенная сетевая модель представляет собой ориентированный граф, который может быть полностью задан различными способами:

1) графически(см.рис. выше);

2) с помощью задания двух множеств: и ;

3) матрицей инцидентности (табл. 7.1). Особенностью сетевой модели является то, что из начального события 1 стрелки выходят, а в конечное 6 – только входят. Поэтому в первой строке матрицы инцидентности имеются единицы только со знаком «минус», а в последней – только со знаком «плюс»;

Таблица 7.1. Матрица инцидентности

4) матрицей смежности (табл. 7.2). По причине, указанной в п.3, в последней строке матрицы смежности поставлены только нули;

Таблица 7.2. Матрица смежности

5) списком ребер сетевой граф задается очевидным образом, поскольку ребра графа обозначены через свои концевые вершины. В таком случае в столбце «вершины» списка будут повторяться номера вершин, указанных в столбце «ребра», причем в той последовательности, в какой в данном случае стрелки – ребра обозначены.

Задача 4. Имеют ли графы на рис. 7.4 ниже гамильтоновы циклы, цепи.

Рис. 7.4. Графы и

Решение .

Гамильтонов цикл как простой цикл, проходящий через все вершины графа, существует на графе - он проходит по ребрам (a, b, c, d, e, f, g, q, n, m, l, h, a ). В существует и гамильтонова цепь, для чего в гамильтоновом цикле достаточно удалить любое ребро.

В графе гамильтонова цикла нет: чтобы пройти через вершины a, b, c внешнего треугольника графа должен содержать все лежащие на этих сторонах ребра, но тогда он не проходит через расположенную в центре треугольника вершину d .Однако гамильтонова цепь в графе существует, например с началом в вершине a , концом d и последовательностью ребер, соединяющих вершины a, f, b, g, c, e, d .

Задача 5. Задача о кратчайшем пути. Как кратчайшим путем попасть из одной вершины графа в другую. В терминах производственного менеджмента: как кратчайшим путем (и, следовательно, с наименьшим расходом топлива и времени, наиболее дешево) попасть из пункта А в пункт Б. Для решения этой задачи каждой дуге ориентированного графа должно быть сопоставлено число - время движения по этой дуге от начальной вершины до конечной. Рассмотрим граф приведенный на рис. 7.5.

Рис. 7.5. Граф

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

Таблица 7.3. Исходные данные к задаче о кратчайшем пути.

Спрашивается в задаче: как кратчайшим путем попасть из вершины 1 в вершину 4.

Решение. Введем обозначение: С (Т ) - длина кратчайшего пути из вершины 1 в вершину Т . (Поскольку любой путь, который надо рассмотреть, состоит из дуг, а дуг конечное число, и каждая входит не более одного раза, то претендентов на кратчайший путь конечное число, и минимум из конечного числа элементов всегда достигается.) Рассматриваемая задача состоит в вычислении С (4) и указании пути, на котором этот минимум достигается.

Для исходных данных, представленных на рис. выше и в табл. выше, в вершину 3 входит только одна стрелка, как раз из вершины 1, и около этой стрелки стоит ее длина, равная 1, поэтому С (3) = 1. Кроме того, очевидно, что С (1) = 0.

В вершину 4 можно попасть либо из вершины 2, пройдя путь, равный 4, либо из вершины 5, пройдя путь, равный 5. Поэтому справедливо соотношение

С (4) = min {С(2) + 4; С (5) + 5}.

Таким образом, проведена реструктуризация (упрощение) задачи - нахождение С(4) сведено к нахождению С(2) и С (5).

В вершину 5 можно попасть либо из вершины 3, пройдя путь, равный 2, либо из вершины 6, пройдя путь, равный 3. Поэтому справедливо соотношение

С (5) = min {С (3) + 2; С (6) + 3}.

Мы знаем, что С (3) = 1. Поэтому

С (5) = min {3; С (6) + 3}.

Поскольку очевидно, что С (6) - положительное число, то из последнего соотношения вытекает, что С (5) = 3.

В вершину 2 можно попасть либо из вершины 1, пройдя путь, равный 7, либо из вершины 3, пройдя путь, равный 5, либо из вершины 5, пройдя путь, равный 2. Поэтому справедливо соотношение

С (2) = min {С(1) + 7; С(3) + 5; С (5) + 2}.

Нам известно, что С (1) = 0, С (3) = 1, С (5) = 3. Поэтому

С (2) = min {0 + 7; 1 + 5; 3 + 2} = 5.

Теперь мы можем найти С (4):

С (4) = min {С (2) + 4; С (5) + 5} = min {5 + 4; 3 + 5} = 8.

Таким образом, длина кратчайшего пути равна 8. Из последнего соотношения ясно, что в вершину 4 надо идти через вершину 5. Возвращаясь к вычислению С (5), видим, что в вершину 5 надо идти через вершину 3. А в вершину 3 можно попасть только из вершины 1. Итак, кратчайший путь таков:

1 → 3 → 5 → 4 .

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

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

Рис. 7.6. Граф

Исходные данные о транспортной системе, например, внутризаводской, приведенные на рис. 7.6., можно также задать таблицей табл.7.4.

Таблица 7.4. Исходные данные к задаче о кратчайшем пути.

Решение.

Решение задачи о максимальном потоке может быть получено из следующих соображений.

Очевидно, максимальная пропускная способность транспортной системы не превышает 6, поскольку не более 6 единиц грузов можно направить из начального пункта 0, а именно, 2 единицы в пункт 1, 3 единицы в пункт 2 и 1 единицу в пункт 3.

Далее надо добиться, чтобы все 6 вышедших из пункта 0 единиц груза достигли конечного пункта 4. Очевидно, 2 единицы груза, пришедшие в пункт 1, можно непосредственно направить в пункт 4. Пришедшие в пункт 2 грузы придется разделить: 2 единицы сразу направить в пункт 4, а 1 единицу - в промежуточный пункт 3 (из-за ограниченной пропускной способности участка между пунктами 2 и 4). В пункт 3 доставлены такие грузы: 1 единица из пункта 0 и 1 единица из пункта 2. Их направляем в пункт 4.

Итак, максимальная пропускная способность рассматриваемой транспортной системы - 6 единиц груза. При этом не используются внутренние участки (ветки) между пунктами 1 и 2, а также между пунктами 1 и 3. Не догружена ветка между пунктами 1 и 4 - по ней направлены 2 единицы груза при пропускной способности в 3 единицы.

Решение можно представить в виде табл. 7.5.

Таблица 7.5. Решение задачи о максимальном потоке