Тема 1. Графы – матрица смежности
1.03 Полное сопоставление графа и таблицы
Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела графы – матрица смежности
Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#77707

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

П1 П2 П3 П4 П5 П6 П7 П8
П1 10 12 14
П2 7 17
П3 2 9 13
П4 3 10
П5 10 2 3
П6 7 9 10
П7 12 13 15
П8 14 17 15

PIC

Определите суммарную длину маршрута A −→  G −→ H − → E −→  F −→ C  . Под суммарной длиной подразумевается общая сумма всех длин дорог, ведущих из одного пункта в другой по заданному маршруту.

В ответе запишите целое число.

Показать ответ и решение

Заметим, что пункт С – единственный, который ведет в три пункта таких, что два из них имеют две дороги. Значит, пункт С – П6. Отсюда следует, что F – П3. Пункт Е ведет в пункты с количеством дорог 2 и 3, а пункт G – с количеством дорог только 3. Поэтому, G – это П7, а E – П5.

Из пункта Е можно попасть в пункт D, который имеет две дороги и равен П4. Значит, пункт B – это П2, так как он оставшийся, имеющий два пути. Отсюда получаем, что пункт А – это П8, пункт H – П1.

П1 П2 П3 П4 П5 П6 П7 П8
H B F D E C G A

Длина маршрута A −→ G − → H −→  E −→ F − → C = 15+ 12 + 10+ 2+ 9 = 27+ 22 = 48  .

Ответ: 48

Ошибка.
Попробуйте повторить позже

Задача 2#77706

На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Звездочка означает наличие дороги между населенными пунктами.

П1 П2 П3 П4 П5 П6 П7
П1 * * *
П2 * * * *
П3 * *
П4 *
П5 *
П6 * * *
П7 * *

PIC

Выпишите последовательно без пробелов и знаков препинания указанные на графе буквенные обозначения пунктов от П1 до П7: сначала букву, соответствующую П1, затем букву, соответствующую П2, и т. д.

Показать ответ и решение

Очевидно, что пункт В – это П2, так как он единственный имеет 4 пути. Пункт Ж – это П5, так как он имеет один путь и в него можно попасть из пункта В. Пункт З – это П4, так как он тоже имеет один путь.

Пункт А – это П1, так как в него можно попасть из пункта З. Пункт Б имеет два пути и в него можно попасть из пункта А, значит, это П7. Пункт Г – это П6, а пункт Д – П3.

П1 П2 П3 П4 П5 П6 П7
А В Д З Ж Г Б
Ответ: АВДЗЖГБ

Ошибка.
Попробуйте повторить позже

Задача 3#77705

На рисунке схема дорог района изображена в виде графа, в таблице приведены длины дорог между пунктами. Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Найдите длину маршрута A − B − C − H − E − F  . В ответ укажите найденную длину.

П1 П2 П3 П4 П5 П6 П7 П8
П1 2 5 6
П2 2 5 8
П3 4 7
П4 4 6
П5 5 5
П6 6 6 7
П7 7 7 8
П8 8 8

PIC

Найдите длину маршрута A − B − C − H − E − F  .

В ответ укажите одно число – найденную длину.

Показать ответ и решение

По графу видно, что пункты B, C, H и Е имеют три пути, причём пункты H и B соединяются в пункте C. Значит, пункт C – это П1. Из пункта С можно попасть в пункт А, который имеет две дороги, значит, А – это П5. Отсюда В – П2.

Продолжая двигаться от пункта В против часовой стрелки, найдём D – П8, Е – П7, F – П3, G – П4, H – П6.

П1 П2 П3 П4 П5 П6 П7 П8
C B F G A H E D

Длина маршрута A − B − C − H − E − F = 5 +2 + 6+ 7+ 7 = 27  .

Ответ: 27

Ошибка.
Попробуйте повторить позже

Задача 4#77702

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

П1 П2 П3 П4 П5 П6 П7
П1 * * *
П2 * *
П3 * * *
П4 * *
П5 * * *
П6 * *
П7 * * *

PIC

Выпишите последовательно без пробелов и знаков препинания указанные на графе буквенные обозначения пунктов от П1 до П7: сначала букву, соответствующую П1, затем букву, соответствующую П2, и т. д.

Показать ответ и решение

Из графа можно заметить, что только пункт F ведет в две дороги, которые имеют три пути. Значит, ему соответствует пункт П6. Затем пункт F ведет в пункты B и G, но пункт B ведет в два пункта с тремя дорогами, а G – только в один. Значит, G – П5, B – П3.

Из пункта G можно попасть в пункт А, значит, А – П2, Е – П4, D – П7, С – П1.

П1 П2 П3 П4 П5 П6 П7
С А В E G F D
Ответ: CABEGFD

Ошибка.
Попробуйте повторить позже

Задача 5#64049

На рисунке схема дорог изображена в виде графа, в таблице звёздочками обозначено наличие дороги между населёнными пунктами. Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Выпишите последовательно, без пробелов и знаков препинания указанные на графе буквенные обозначения пунктов от П1 до П7: сначала букву, соответствующую П1, затем букву, соответствующую П2, и т. д.

PIC PIC

Показать ответ и решение

Единственной вершиной со степенью 5 является Б. В таблице же П4 обладает такой же степенью. Следовательно П4 = Б.

Единственной вершиной со степенью 2 является Е. В таблице же П6 обладает такой же степенью. Следовательно П6 = Е.

Единственной вершиной со степенью 1 является В. В таблице же П7 обладает такой же степенью. Следовательно П7 = В.

Единственной вершиной степени 4, соединённой с Е, является вершина Д. В таблице это П2, соединённый с П6 (вершиной Е). Следовательно П2 = Д.

Единственной вершиной степени 3, соединённой с Д, является вершина Ж. В таблице это П1, соединённый с П2 (вершиной Д). Следовательно П1 = Ж.

Единственной оставшейся вершиной степени 4, соединённой с Ж, является вершина А. В таблице это П3, соединённый с П1 (вершиной Ж). Следовательно П3 = А.

Единственная оставшаяся вершина Г = П5. Получаем ответ: ЖДАБГЕВ.

Ответ: ЖДАБГЕВ

Ошибка.
Попробуйте повторить позже

Задача 6#63908

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

PIC

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите номера населённых пунктов D и E в таблице. В ответе напишите числа в порядке возрастания без разделителей. Например, если бы ответом являлись пункты П9 и П8, в ответе нужно было бы написать 89.

Показать ответ и решение

По рисунку сразу однозначно определяются два пункта: A это П5 и H это П2.

Далее можно заметить, что рисунок симметричен относительно этих двух пунктов. Тогда, пути из A ведут в B и G, значит в таблице это П7 и П8. Из П7 и П8 есть еще по одной неизвестной дороге, в пункты П3 и П4, значит соотносим это с рисунком о определяем что это пункты C и F.

Осталось два неизвестных пункта в таблице это П1 и П6, а на рисунке не распределенными остались D и E. Следовательно ответ 16.

Ответ: 16

Ошибка.
Попробуйте повторить позже

Задача 7#63820

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

PIC

Найдите номера пунктов в таблице, соответствующие пунктам А и В на схеме, если известно, что дорога между А и В длиной 10 километров. В качестве ответа запишите без разделителей два числа – номера пунктов в таблице, соответствующие пунктам А и В на схеме, в порядке возрастания.

Показать ответ и решение

По рисунку можно однозначино определить пункт G, так как это единственный пункт, в который ведет две дороги. Тогда в таблице это П7.

Далее заметим, что остальная часть рисунка симметрична. Тогда, пунктами E и F могут являтся в таблице пункты П5 и П6.

П5 ведет в пункты П1 и П3, это либо пункты A, C либо пункты B, D. П6 ведет в пункты П2 и П4, это либо пункты A, C либо пункты B, D.

Теперь рассмотрим дороги между П1, П2, П3 и П4. Дорога длиной 10 есть между пунктами П1 и П3 и между пунктами П3 и П4. Основываясь на сказаном ранее, можно определить что пункты A и B имеют номера 3 и 4.

Ответ: 34

Ошибка.
Попробуйте повторить позже

Задача 8#63517

На рисунке снизу изображена схема дорог Н-ского района, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.

1 2 3 4 5 6 7
1 * * *
2 * * *
3 * *
4 * * *
5 * * *
6 * *
7 * *

PIC

Каждому населённому пункту на схеме соответствует его номер в таблице, но неизвестно, какой именно номер. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам A и G на схеме. В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.

Показать ответ и решение

По две дороги у населенных пунктов: B, D, F. По три дороги у населенных пунктов: A, C, E, G.

Проверим, в населенные пункты с каким числом дорог ведут дороги из пунктов A, C, E, G.

A -> 2, 3, 3

C -> 2, 3, 2

E -> 2, 3, 2

G -> 3, 3, 2

Заметим, что пункты A и G ведут имеют аналогичные (по количеству) пути, при этом отличные от C и E. Тогда найдем в таблице номера НП, которые имеют 3 дороги и при этом ведут в НП с числом дорог 2, 3, 3. Это будут НП 4 и 5.

Ответ: 45

Ошибка.
Попробуйте повторить позже

Задача 9#63231

На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице приведены длины дорог между пунктами. Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Найдите номера пунктов Б и В.

В качестве ответа укажите номера пунктов без буквы "П"в порядке возрастания. Пробел и другие знаки ставить не нужно.

PIC

Показать ответ и решение

Пункт К имеет два маршрута - ему соответствует номер 3. Из пункта К можно попасть в пункты Д и Е, которые имеют 4 и 3 маршрута соответственно. Значит, подходящие для них номера - 2 и 5. Из пункта Д можно попасть в пункты Г и Б, имеющие 4 и 3 маршрута соответственно, их номера - 4 и 1. Пункт А следует из пункта Б и для него остается номер 6. Тогда, пункт В равен номеру 7.

Ответ: 17

Ошибка.
Попробуйте повторить позже

Задача 10#63230

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

PIC

Показать ответ и решение

Заметим, что пункты Г и Д единственные, имеющие 4 пути и соединяющиеся в пункте В. Значит, пунктам Г и Д могут соответствовать номера 2 и 3, пункту В - номер 4.

Так как помимо пунктов Г и Д пункт В ведет в А, то пункт А - номер 7.

В свою очередь пункт А ведет в пункты Б и Е, которые равны номерам 5 и 6. У нас осталось всего 2 номера для К и И - 1 и 8. Значит, ответ 18.

Ответ: 18

Ошибка.
Попробуйте повторить позже

Задача 11#61617

На рисунке схема дорог изображена в виде графа, в таблице звёздочками обозначено наличие дороги между населёнными пунктами. Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Выпишите последовательно, без пробелов и знаков препинания указанные на графе буквенные обозначения пунктов от П1 до П7: сначала букву, соответствующую П1, затем букву, соответствующую П2, и т. д.

PIC PIC

Показать ответ и решение

Из таблицы мы можем заметить, что только из одного пункта П7 ведет 2 дороги, поэтому очевидно, что пункту П7 соответсвует буква Е.

Из пункта Е мы можем попасть в пункты Ж и А, из которых выходит по 5 дорог. Им могут соответствовать пункты П2 и П4.

На схеме существует два пункта с тремя дорогами - Б и В, но пункт В - общий для Ж и А. Значит, пункт В имеет номер П3. Получаем, что пункт Б имеет номер П1.

Так как из пункта Б можно попасть только в пункт А, а в пункт Ж прямой дороги нет, то пункту А соответсвует номер П2, пункту Ж - П4.

Для пунктов Г и Д остаются варианты П5 и П6. Из пункта Ж можно попасть в пункт Г, а из пункта А нет. Значит, пункту Г соответсвует номер П5, а пункту Д - П6.

Получаем ответ: БАВЖГДЕ.

Ответ: БАВЖГДЕ

Ошибка.
Попробуйте повторить позже

Задача 12#57438

На рисунке изображена схема дорог, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам Е и В на схеме.

В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания

П1 П2 П3 П4 П5 П6 П7
П1 * * *
П2 * * *
П3 * *
П4 * * *
П5 * * * * * *
П6 * *
П7 * * *

PIC

Показать ответ и решение

Пункт Д имеет 6 дорог, ему соответствует значение П5. Пункты Г и Ж имеют по две дороги, значит их значения либо П6, либо П3. Пункты Е и В связаны с пунктами Г и Ж и имеют по 3 дороги, значит, им соответствуют значения либо П4, либо П2.

Ответ: 24

Ошибка.
Попробуйте повторить позже

Задача 13#57437

На рисунке схема дорог изображена в виде графа, в таблице звёздочками обозначено наличие дорог. Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Выпишите последовательно указанные на графе буквенные обозначения пунктов от П7 до П1. Пробелов и других знаков препинания ставить не нужно.

П1 П2 П3 П4 П5 П6 П7
П1 * *
П2 * * *
П3 * * *
П4 * * * *
П5 * * *
П6 * * * *
П7 * * * * *

PIC

Показать ответ и решение

Пункт Д имеет 5 дорог, ему соответствует значение П7. Пункт Ж имеет 2 дороги, он является значением П1. Так как Ж связан с Д и Е, то пункт Е имеет значение П3. Пункт Б имеет 4 дороги и связан с пунктом Е, ему соответствует пункт П6. Пункт Г также имеет 4 дороги, значит это пункт П4. Пункт В имеет 3 дороги и связан с пунктом Д, он является пунктом П2. Остается пункт А, это пункт П5.

П1 П2 П3 П4 П5 П6 П7
Ж В Е Г А Б Д

 

Ответ: ДБАГЕВЖ

Ошибка.
Попробуйте повторить позже

Задача 14#57436

На рисунке слева изображена схема дорог. В таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет. Каждому пункту на схеме соответствует его номер в таблице, однако неизвестно, какой именно.

Определите номер пункта, соответствующего пункту В.

В ответе запишите только число, букву П писать не нужно.

П1 П2 П3 П4 П5 П6 П7
П1 * * * * *
П2 * * *
П3 * * *
П4 * *
П5 * * *
П6 * * *
П7 * * *

PIC

Показать ответ и решение

Пункт D имеет 5 дорог, ему соответствует значение П1. Пунт G единственный имеет две дороги, его номер П4. Так как пункт G связан с пунктами Е и F, значит их значения П2 и П3. По аналогии, пунктам А и С соответствуют значения П5 и П6, так как они связаны с пунктами Е и F. Получается, что пункт В имеет номер П7.

Ответ: 7

Ошибка.
Попробуйте повторить позже

Задача 15#57435

На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе.

Определите длину дороги между пунктами Е и Ж. Передвигаться можно только по указанным дорогам.

П1 П2 П3 П4 П5 П6 П7
П1 2 4
П2 2 7
П3 1 3
П4 9
П5 7 12
П6 4 1 9 12 13
П7 3 13

PIC

Показать ответ и решение

Пункт Г имеет 5 дорог, ему соответствует значение П6. Пункт Д - одну дорогу, он является пунктом П4 в таблице. Пункты А, Б и В связаны между собой и имеют длину 2, значит им в таблице соответствуют значения П1, П2, П5. Наконец, остались только пункты Е и Ж. Это пункты П3 и П7. Длина дороги между ними равна 3.

Ответ: 3

Ошибка.
Попробуйте повторить позже

Задача 16#57434

На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе.

Определите, какова длина дороги из пункта Д в пункт Г.

П1 П2 П3 П4 П5 П6 П7
П1 30 35 47
П2 30 12 27 28
П3 12 14
П4 35 27 31 45
П5 28 14 6
П6 47 31 1
П7 45 6 1

PIC

Показать ответ и решение

Оба пункта Г и Д имеют 4 дороги. Поэтому им соответствуют пункты П2 и П4. Длина дороги между ними равна 27.

Ответ: 27

Ошибка.
Попробуйте повторить позже

Задача 17#57267

На рисунке слева изображена схема дорог Н-ского района, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Выпишите последовательно без пробелов и знаков препинания указанные на графе буквенные обозначения пунктов от П1 до П8: сначала букву, соответствующую П1, затем букву, соответствующую П2, и т. д.

PIC

Показать ответ и решение

Для начала можно определить номера пунктов Ж и Г, они различаются между собой. Дороги из Ж ведут в пункты, из которых ведут 3 дороги(Е,Д,И) или же 4(Г). Из Г ведут дороги в пункты, из которых ведут 2 дороги(А) ,3 дороги(Б,Е) или же 4(Ж).

На основе этого, можно легко найти номера Ж и Г, им соответствуют П5 и П8. Зная номер пункта Г, нам не составит труда найти номера пунктов А,Е,Б. Их номера: П7,П3,П1.

Теперь мы можем узнать номера пунктов В и Д, им соответствуют номера П4 и П6. Остался один пункт: И. его номер П2.

Для правильно ответа нужно указать пункты от П1 до П8 и в итоге мы получаем ответ: БИЕВЖДАГ.

Ответ: БИЕВЖДАГ

Ошибка.
Попробуйте повторить позже

Задача 18#56428

На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).

П1 П2 П3 П4 П5 П6 П7
П1 12 13
П2 12 6 1
П3 4
П4 13 6 9 8
П5 4 3 7
П6 9 3
П7 1 8 7
PIC

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите протяженность маршрута ЗЕКАСДА. В ответе запишите целое число.

Показать ответ и решение

В самом начале мы можем с легкостью определить номера пунктов А и З, так как они имеют отличное от других пунктов количество рёбер. Их номера: П4 и П3 соответственно. Зная номер З, без трудностей находим номер Е, затем номера Д и К. Этим пунктам соответствуют номера: П5, П7, П6.

Осталось два пункта: С и В. Найти их номера не составит труда, поскольку они отличаются между собой количеством рёбер. П2 и П1 – это номера пунктов С и В соответственно. Остаётся найти протяженность маршрута ЗЕКАСДА: 4+3+9+6+1+8 = 31. Ответ: 31

Ответ: 31

Ошибка.
Попробуйте повторить позже

Задача 19#55048

На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о их протяженности.

1 2 3 4 5 6 7
1 6
2 16 14
3 12 2
4 16 10 8
5 10 4
6 14 12
7 6 2 8 4

PIC

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите сумму протяженностей дорог из пункта D в пункт E и из пункта G в пункт C.

Показать ответ и решение

Заметим, что вершина E единственная, имеющая степень 4. Значит, вершина Е соответствует значению 7 в таблице. Вершина D имеет степень 1, вершина С – 3 , остальные вершины имеют степень 2. Из этого следует, что вершине D соответствует значение 1 в таблице, вершине С – значение 4. Протяженность дороги между пунктами 1 и 7 – 6. Вершиной G могут быть значения 2 либо 5 в таблице. Так как существует путь из пункта Е в пункт G, то вершина G – это 5. Протяженность дороги между пунктами 5 и 4 равна 10. Сумма протяженностей равна 6 + 10 = 16.

Ответ: 16

Ошибка.
Попробуйте повторить позже

Задача 20#53421

На рисунке слева изображена схема дорог Неизвестного района, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет

1 2 3 4 5 6 7
1 * * *
2 * *
3 * * * *
4 * * *
5 * * *
6 * *
7 * * *

PIC

Каждому населённому пункту на схеме соответствует его номер в таблице, но неизвестно, какой именно номер. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам E и F на схеме. В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.

Показать ответ и решение

Проанализировав схему, становится очевидно, что только из пункта А выходят 4 дороги. Значит, населенному пункту А соответсвует 3 номер в таблице. Из пунктов B и C выходит по две дороги, значит, им соответствуют номера 2 и 6.

Кроме пункта А дороги из пунктов В и С ведут в пункты D и G соответственное. Посмотрев в таблицу, можно заметить, что пунктам D и G могут соответствовать только номера 1 и 4.

Для населённых пунктов E и F остаётся только два номера - 5 и 7. Так как в ответе необходимо указать номера в возрастающем порядке, то ответ 57.

Ответ: 57
Рулетка
Вы можете получить скидку в рулетке!