Графы. 7-8 класс

A

B

C

D

0

1

1

0

B

0

0

1

1

C

0

0

1

1

D

0

0

0

0

A

B

C

D

A

0

1

1

0

B

0

0

1

1

C

0

0

1

1

D

0

0

0

0

A

B

C

D

A

10

7

0

B

10

5

6

C

7

5

3

D

0

6

3

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

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

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

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

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

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

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

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

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

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

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

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

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

Решение

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

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

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

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

Ответ: 5 путей

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

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

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

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

.

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

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

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

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

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

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

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

Решение Ответ: 12

Задача 10

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

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

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

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

Решение Ответ: 12 обедов

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

Ответ: 3

Задача 12 Решение

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

Задача 13

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

Решение

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

Задача 14 Сельская малокомплектная школа находится в поселке Вершки. Петя Орлов живёт в деревне Дальнее.

Определите, какое минимальное расстояние ему надо пройти, чтобы добраться до школы: Решение

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

Задача 14

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

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

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

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

Задача 15

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

Задача 16

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

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

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

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

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

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

Ж = Д = 1. И = Г + Е = 2. К = Ж + Е + И + Д = 5. Ответ: 5

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

Задача 18 На соревнованияхпо спортивному ориентированию участник должен пробежать от старта до финиша, набрав максимально возможное количество баллов (их число за преодоление того или иного участка указано на рисунке). Определите это количество.

Решение Рассмотрим все возможные пути:

С-А-В-Ф=3+2+6=11

С-Б-Г-Ф=8+2+4=14

С-А-Б-Г-Ф=3+6+2+4=15

С-А-Б-В-Ф=3+6+3+6=18

С-А-Б-В-Г-Ф=3+6+3+6+4=22

С-Б-А-В-Г-Ф=8+6+2+6+4=26

С-Б-В-Г-Ф=8+3+6+4=21 Ответ: 26