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

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

Задача 1#56470

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

PIC PIC

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

Подпишем степени всех вершин:

PIC

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

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

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

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

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

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

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

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

Задача 2#56302

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

PIC

PIC

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

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

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

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

Единственной оставшейся вершиной степени 3, является вершина Б. В таблице это П2. Следовательно П2 = Б.

Единственной вершиной степени 5, соединённой с Ж, З, А, Б, является вершина Д. В таблице это П10. Следовательно П10 = Д.

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

Единственной вершиной степени 5, соединённой с А, Б, В, Ж, является вершина Й. В таблице это П7. Следовательно П7 = Й.

Единственной вершиной степени 5, соединённой с З, Й, В является вершина Г. В таблице это П8. Следовательно П8 = Г.

Единственной вершиной степени 5, соединённой с Б является вершина Е. В таблице это П6. Следовательно П6 = Е.

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

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

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

Задача 3#29436

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

PIC PIC

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

PIC

Сначала напишем степени всех вершин: А  4  , Б  5  , В  6  , Г  5  , Д  4  , Е  3  , Ж  4  ,  З        5  . Заметим, что только одна вершина имеет степень 3  — это Е  (П6  ). Ее связывают вершины со степенью 5  , и остается лишь одна вершина со степенью 5  — это Б  (П2  ). Также заметим, что только одна вершина имеет степень 6  — это       В  (П7  ). Две из трех вершин со степенью 4  связаны друг с другом, значит, оставшаяся — Д  в пункте П1  . В вершину В не приходит только Ж  , значит, Ж  П8  . Оставшаяся вершина со степенью 4  — это А  , т.е. П4  . Одна из вершин со степенью 5  приходит в Б  , а вторая — нет. Та, которая приходит, З  П5  , а Г  П3 .

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

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

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

Задача 4#29348

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

PIC PIC

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

PIC

Сначала напишем степени всех вершин: А - 2  , Б - 4  , В - 6  , Г - 6  , Д - 4  , Е - 3  , Ж - 3  , З - 2  . Вершины степени 6  (Г и В) связаны одной вершиной степени 2  - А, тогда А - П8  , и одной вершиной степени 3  - Ж, тогда Ж - П  7  . Помимо этого Ж имеет общую дорогу с населённым пунктом Б, значит, Б - П4  . У нас осталась одна вершина степени 2  - З => З - П6  , одна вершина степени 3  - Е => Е - П5  , и одна вершина степени 4  - Д => Д - П3  . Населённый пункт З имеет дороги с Д (П3  ) и Г, значит, Г - П1  , тогда оставшаяся вершина В - П2  .
Получаем ответ: ГВДБЕЗЖА

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

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

Задача 5#28797

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

PIC PIC

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

PIC

Сначала напишем степени всех вершин: А  3  , Б  3  , В  3  , Г  2  , Д  4  , Е  5  , Ж  2  ,  З        4  . Заметим, что только одна вершина имеет степень 5  — это Е  , тогда Е  П8  . Вершина А  имеет степень 3  , она одна из вершин, имеющих такую степень и не связанных с вершинами степени 2  , значит, А  П4  . Она связана с единственной вершиной степени 4  Д  , тогда Д  П6  , и единственной вершиной степени 3  В  , тогда В     П1  . У нас остался один пункт со степенью 3  Б  , ему соответствует П3  , и пункт со степенью 4  З  , ему соответствует П2 . Вершины Д  и Б  связывают З  (П2  ) и Ж  , тогда Ж  П7  . По остаточному принципу Г  П5 .

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

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

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

Задача 6#27983

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

PIC PIC

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

PIC

Подпишем все степени вершин (количество ребер, выходящих из вершины) в таблице и на графе: А  5  , Б      3  ,        В  4  , Г  4  , Д  3  , Е  4  , Ж  1  , З  2  , П1  3  , П2  1  , П3  3  , П4  4  , П5  4  , П6       4  , П7 2  , П8  5  . У нас три вершины с уникальными степенями, можем их сопоставить: П8  А  , П7  З  ,    П2  Ж . Вершина Ж  связана только с Б  , можем найти Б  : П1  Б  . З  связана с двумя вершинами, одна из которых известна, значит, П5  Г  . Осталась одна неизвестная вершина степени 3  , можем найти её в таблице: П3  Д  . Из двух оставшихся вершин одна связана с Г  , другая нет, можем найти обе: П4  Е  , П6  В .

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

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

Задача 7#27444

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

PIC PIC

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

PIC

Сначала напишем степени всех вершин: А  4  , Б  4  , В  4  , Г  4  , Д  3  , Е  3  , Ж  5  ,  З        3  . Заметим, что только одна вершина имеет степень 5  — это Ж  , тогда Ж  — П6  . Пункты Д  и Б  не связаны с   Ж  , тогда Д  П1  (степень вершины 3  ), а Б  П8  (степень вершины 4  ). Б  и Д  связаны с З  и Г  , значит, З       П2  , Г П4  . Вершины Д  и Г  связывает А  , тогда А  П3  . Остались вершины Е  и В  , они имеют разное количество дорог, поэтому можем найти соответствующие пункты в таблице. Таким образом, Е  П7  , В  П5 .

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

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

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

Задача 8#26936

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

PIC PIC

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

PIC

Распишем степени вершин. Видим, что единственная вершина степени 4  это В  П1  . Вершина В  не связана только с одной вершиной — Е  , соответственно Е  П2  . Вершина Е  связана с Б  и А  , соответственно П3  и П6  . По оставшимся степеням вершин Г  П4  , Д  П5  .

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

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

Задача 9#26668

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

PIC PIC

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

PIC

Подпишем степени вершин. Е — единственная вершина со степенью 2  , ей соответствует П5. Она связана с вершиной Г со степенью 6  и с вершиной В со степенью 5  . Им соответствуют П1 и П3 соответственно. Оставшаяся вершина Д со степенью 5  соответствует П2. Вершина Г не связана с вершиной Б. Значит, вершине Б соответствует П4. Вершина Б связана с вершиной З. Ей соответствует П7. Оставшимся вершинам А и Ж соответствуют П6 и П8 соответственно.

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

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

Задача 10#26080

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

PIC PIC

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

PIC

Сначала напишем степени всех вершин: А - 3  , Б - 3  , В - 3  , Г - 3  , Д - 2  , Е - 3  , Ж - 3  , З - 4  . Заметим, что только одна вершина имеет степень 2  - это Д, тогда Д - П3  . Также лишь одна вершина имееь степень 4  - это З, тогда З - П8  . Вершина Д связана с З (П8  ) и Б, значит, Б - это П7  . Пункты Б и З связавает Е, тогда Е - П6  . Е (П6  ) связана с З (П8  ), Б (П7  ) и В, по таблице смежности определяем, что В - это П1  . Вершина В (П1  ) связана с Е (П6  ), З (П8  ) и Ж, методом исключения, используя таблицу, определяем, что Ж - это П5  . Пункты Ж (П5  ) и З (П8  ) связывают В (П1  ) и А, так как В нам исвестна, то по остаточному принципу А - это П2  . У нас осталось одна вершина - Г, которая соответствует П4  .
Получаем ответ: ВАДГЖЕБЗ

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

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

Задача 11#26053

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

PIC PIC

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

PIC

Сначала напишем степени всех вершин: А  5  , Б  5  , В  4  , Г  6  , Д  7  , Е  3  , Ж  5  , З  6  , И  3  , Й  4  . Можем заметить, что только одна вершина имеет степень 7  — это Д  , тогда Д  П9  . Вершина Д  связана со всеми вершинами, кроме Б  и Е  , значит, П1  — это Е  (так как Е имеет степень 3  , как и П1  ), а П6  — это Б  (так как Б  имеет степень 5  , как и П6  ). Вершина Е (П1  ) связана с З  , А  и Б  , так как Б  мы уже знаем, то не составит труда определить А  и З  , ведь у них разные степени, получаем, что А  — это П5  , а З  П4  . Вершина А  связана с В  , имеющей степень 4  , значит В  — это П7  , тогда вершина Й  (которая также имеет степень 4  , но не связана с А  ) — это П8  . Й  связана с Ж, Д, В  и Б  , из них мы не знаем, какому пункту соответствует Ж  , но знаем другие, тогда свободный пункт, связанный с Й  П2  , значит, вершине Ж  соответствует П2  . Заметим, что теперь у нас остались два пункта, и оба с разными степенями, значит, можем определить вершины! П3 имеет степень 6  , как и свободная вершина Г  , а П10  имеет степень 3  , как и свободная вершина И .

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

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

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

Задача 12#25974

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

PIC PIC

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

PIC

Подпишем степень (количество ребер, выходящих из нее) вершин на графе и в таблице. Получаем на графе: А - 5, Б - 5, В - 4, Г - 5, Д - 5, Е - 5, Ж - 5, 3 - 8, И - 5, Й - 5. В таблице: П1 - 5, П2 - 5, П3 - 5, П4 - 5, П5 - 4, П6 - 5, П7 - 8, П9 - 5, П10 - 5. У нас есть 2 две вершины с уникальными степенями, З и В, подпишем их в таблице: П5 - В, П7 - З. Только одна вершина не связана с З - это Д - найдём её в таблице: П6 - Д. Вершина В связана с тремя вершинами степени 5, и только одна из них связана с Д, найдём её в таблице: П9 - А. Из связей вершины В вершина А связана с И, но не связана с Б. Можем найти Б и И: П2 - И, П3 - Б. Вершина Б из оставшихся неизвестных связана со всеми, кроме Ж, можем найти Ж: П1 - Ж. Вершина Ж из оставшихся неизвестных не связана только с Й, находим: П4 - Й. Вершина Г связана с Й, а Е не связана, ищем в таблице: П8 - Г, П10 - Е.

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

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

Задача 13#25947

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

PIC PIC

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

PIC

Подпишем у каждой вершины ее степень (количество ребер, выходящих из нее): А - 6, Б - 8, В - 5, Г - 5, Д - 6, Е - 5, Ж - 7, З - 5, И - 6, Й - 3. У нас есть сразу 3 вершины с уникальными степенями, Б, Й, Ж, найдем их в таблице и получаем: П1 - Б, П2 - Й, П10 - Ж. Г - единственная вершина, не связанная с Б, в таблице это П3, Г - П3. А - единственная вершина степени 6, не связанная с Й, находим в таблице: А - П9. В - единственная вершина степени 5, не связанная с Ж, найдем в таблице: В - П5. Осталось две неизвестных вершины степени 6, одна из которых связана с Г, можем найти обе. Связанная с Г - это П8 - И, не связанная - П6 - Д. Из двух оставшихся вершин одна связана с Д, другая нет. Связанная с Д - это П7 - З, не связанная - П4 - Е.

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

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

Задача 14#25920

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

PIC PIC

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

PIC

Подпишем около каждой вершины ее степень (количество ребер, выходящих из нее). Получается: А  1  , Б      4  , В 2  , Г  3  , Д  1  , Е  4  , Ж  4  , З  3  . У нас есть вершина с уникальной степень — В  — найдём в таблице вершину степени 2  П5  , получаем: В  П5  . Из В  выходит два ребра, оба степени 4  , у нас всего 3  вершины степени 4  , две из которых связаны с В  , значит, мы можем определить не связанную — вершина Е  . Ищем в таблице вершину степени 4  , не связанную с В  , — П8  , значит, Е  П8  . Е  связана с вершиной степени 1  А  , значит, находим в таблице вершину степени 1  , связанную с Е  , — П6  , значит, П6  А  . У нас осталась еще одна вершина степени 1  Д  , находим в таблице неизвестную вершину степени 1  П2  , значит П2  Д  . Д  связана только с Ж  , значит, единственная связь Д  в таблице — П3  — это Ж  . Единственная неизвестная вершина степени 4  — это Б  , находим в таблице неизвестную вершину степени 4  П1  , значит Б  П1  . У нас осталась две вершины степени 3  , одна из которых связана с Е  , другая с Ж  . Получается, З  , связанная с Ж  , — это П7  , и остается, что Г  - П4 .

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

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

Задача 15#25893

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

PIC PIC

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

PIC

Расставим все степени (количество ребер, выходящих из нее) вершин: А - 3, Б - 4, В - 6, Г - 5, Д - 4, Е - 6, Ж - 4, З - 6, И - 6, Й - 4. У нас есть две вершины с уникальными степениями: А и Г, можем найти их по таблице: это вершины П5 и П3 соответственно. А связана с двумя вершинами степени 6 и одной вершиной степени 4, вершиной Б, эту вершину мы и можем найти по таблице через связи П5, это вершина П1. Б связана с тремя вершинами степени 6 из четырех, можем найти вершину, которая не связана с Б, степени 6, это вершина З, она же в таблице - П7. У нас осталось 3 вершины степени 4, две из которых связаны друг с другом, значит, можно найти вершину степени 4, не связанную ни с одной другой неизвестной вершиной степени 4, это вершина Д, она же в таблице П9. То же самое можно сделать с вершиной В и понять, что это П10. Осталось найти две вершины степени 6, одна из которых связана с З, другая нет, значит, по таблице через связи З ищем неизвестную вершину - это П6, она же вершина И. Значит, оставшаяся неизвестная вершина степени 6 - П2 - это Е. Две оставшиеся неизвестные можно найти по их связям: Й связана с Е, Г, В, а Ж связана с И, В, Г. Можно определить, что Й - это П4, а Ж - это П8.

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

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

Задача 16#25761

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

PIC PIC

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

PIC

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

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

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

Задача 17#25599

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

PIC

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

PIC

Для начала у каждой вершины подпишем ее степень (количество ребер, выходящих из этой вершины). Получаем: A - 3, B - 3, C - 2, E - 3, G - 5, H - 3, F - 3, D - 4. У нас есть сразу 3 вершины с уникальными степенями, подпишем их в таблице, получаем: C - П2, D - П4, G - П5. Теперь смотрим на связи этих вершины. По картинке видно, что C связана с двумя вершинами, одна из которых связана с G, другая - нет. Значит, П1 - B, П8 - Е. Осталось три вершины степени 3, две из которых связаны с D, выходит, что ищем неизвестную вершину, не связанную с D, это будет H. Получается, H - П7. Остается две вершины, одна из которыз связана с H. Ищем неизвестную вершину, связанную с H, это будет F. Получается, A - П3, F - П6 (по остаточному принципу).

Ответ: BCADGFHE

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

Задача 18#25572

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

PIC PIC

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

PIC

Первым делом напишем около каждой вершины ее степени. Получается: А - 2, Б - 3, В - 2, Г - 2, Д - 5, Е - 2, Ж - 3, З - 3. Видим, что единственная вершина степени 5 - это Д, значит, П1 - это Д, так как в таблице она единственная имеет 5 связей. Замечаем, что только З имеет степень 3 и не связана с Д. Ищем в таблице вершину, которая имеет степень 3 и не связана с Д, это П4. З связана с двумя вершинами степени 2 и одной степени 3, эту одну вершину степени мы можем определить. По картинке видно, что это Ж, находим ее по таблице (вершина, связанная с З, степени 3), это П8. Две вершины, с которыми связана Ж мы знаем, значит, можем найти и третью. По картинке это Е, значит, находим по таблице ее номер, это П6. Все вершины степени 3, кроме одной, мы уже опредили, поэтому можно найти последнюю. По картинке это Б, находим в таблице неизвестную вершину степени 3 - это П2. Осталось найти 3 вершины степени 2. Идём по таблице, нужна П3, она связана с Д и Б, видимо по картинке, что П3 - это В. Далее П5, она связана с Д И З, по картинке видим, что П5 - это А. Остается только, что Г - это П7. Получаем ответ: ДБВЗАЕГЖ.

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

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

Задача 19#25545

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

PIC

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, каким номерам соответствуют пункты F и C, ответ запишите последовательностью цифр.

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

PIC

У нас есть лишь одна вершина степени 1 - это H, значит, вершина H соответствует 8 номеру в таблице. Вершина H связана с вершиной F, понимаем из таблицы, что F - это 5 вершина. Нам нужно найти только F и C, F мы уже нашли, ещё одна вершина степени 3 это С, а это номер 1. Значит, ответ - 51.

Ответ: 51

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

Задача 20#25131

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

PIC

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

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

PIC

Подпишем степени вершин. A  — единственная вершина со степенью 4  , ей соответствует П2. E  — единственная вершина со степенью 2  , не связанная с вершиной A  , ей соответствует П5. Вершина E  связана с вершиной C  со степенью 3  и с вершиной D  со степенью 2  , им соответствуют П4 п П3 соответственно. Вершина C  связана с вершиной B  , которой соответствует П6. Оставшаяся вершина F  соответствует П1.

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