Алгебра
Английский
Биология
География
Геометрия
История
Русский
Обществознание
Физика
Химия
Информатика
Литература
МатематикаВопрос:
В городе 5 районов: R1, R2, R3, R4, R5. Дороги построены между R1-R2, R2-R3, R3-R4, R4-R5, R5-R1 (кольцевая линия), а также мост R2-R5. Является ли граф связным? Какой мост нужно закрыть на ремонт, чтобы город распался на две части? Существует ли путь из R3 в R5, не проходящий через R2?
Ответ:
- Является ли граф связным: Да, граф связный, так как из любого района можно добраться до любого другого.
- Мост для разделения города: Если закрыть мост R2-R5, город не распадется на две части, но если убрать ребро R2-R3 или R3-R4, то город разделится.
- Путь из R3 в R5, не проходящий через R2: Да, существует. Можно проехать из R3 в R4, затем в R5.
Похожие
- В каком турнире участвовали команды «Спартак», «Динамо», «Торпедо», «Локомотив»? Каковы были результаты матчей?
- Нарисуйте ориентированный граф (стрелка от победителя к проигравшему) и определите, какая команда имеет самую высокую «исходящую степень» (количество побед).
- В саду посадили 7 деревьев. Между некоторыми проложили дорожки так, что получилось дерево (связный граф без циклов). Известно, что в этом дереве 4 вершины имеют степень 1 (листья), 2 вершины — степень 2, одна вершина — степень 3. Сколько в этом дереве ребер?
- На карте области 5 стран. Нужно раскрасить их так, чтобы соседние страны (имеющие общую границу) были разного цвета. Постройте граф соседства (вершина — страна, ребро — соседство) по описанию: Страна 1 граничит с 2, 3, 5. Страна 2 граничит с 1, 3, 4. Страна 3 граничит с 1, 2, 4, 5. Страна 4 граничит с 2, 3. Страна 5 граничит с 1, 3. Какое минимальное количество цветов потребуется? (Подсказка: попробуйте раскрасить последовательно).
