Статья "Графы" (А. Савин)
Статья "Элементы теории графов" (В. Фосс)
Материалы по этой теме:
-
Книги, журналы, Генкин С.А., Итенберг И.В., Фомин Д.В., Ленинградские математические кружки, глава 6. Графы-1
Книги, журналы, Генкин С.А., Итенберг И.В., Фомин Д.В., Ленинградские математические кружки, глава 13. Графы-2
Книги, журналы, Иванов С.В., Математический кружок, глава 5. Графы
Подтемы:
-
Степень вершины
(123 задачи)
Связность и разложение на связные компоненты
(67 задач)
Деревья
(36 задач)
Планарные графы. Формула Эйлера
(21 задача)
Обход графов
(79 задач)
Ориентированные графы
(48 задач)
Теория графов (прочее)
(80 задач)
Фильтр
Выбрана 1 задача Убрать все задачи
В некой стране 100 городов (города считайте точками на плоскости). В справочнике для каждой пары городов имеется запись, каково расстояние между ними (всего 4950 записей).
а) Одна запись стёрлась. Всегда ли можно однозначно восстановить её по остальным?
б) Пусть стёрлись k записей, и известно, что в этой стране никакие три города не лежат на одной прямой. При каком наибольшем k всегда можно однозначно восстановить стёршиеся записи?
Решение
Задачи
Задача 98278 |
|
|
В компанию из n человек пришёл журналист. Ему известно, что в этой компании есть человек Z, который знает всех остальных членов компании, но его не знает никто. Журналист может к каждому члену компании обратиться с вопросом: "Знаете ли вы такого-то?"
а) Может ли журналист установить, кто из компании есть Z, задав
менее n вопросов?
б) Найдите наименьшее количество вопросов, достаточное для того,
чтобы наверняка найти Z, и докажите, что меньшим числом вопросов обойтись нельзя.
(Все отвечают на вопросы правдиво. Одному человеку можно задавать несколько
вопросов.)
|
|
Решение |
Задача 98544 |
|
|
В каждой клетке таблицы (n–2)×n (n > 2) записано целое число от 1 до n, причём в каждой строке все числа различны и в каждом столбце все числа различны. Докажите, что эту таблицу можно дополнить до квадрата n×n, записав в каждую новую клетку какое-нибудь целое число от 1 до n так, чтобы по-прежнему в каждой строке и в каждом столбце числа были различны.
|
|
|
Решение |
Задача 109490 |
|
|
Можно ли покрасить 15 отрезков, изображённых на рисунке, в три цвета так, чтобы никакие два отрезка одного цвета не имели общего конца?
|
|
|
Решение |
Задача 116047 |
|
|
В некой стране 100 городов (города считайте точками на плоскости). В справочнике для каждой пары городов имеется запись, каково расстояние между ними (всего 4950 записей).
а) Одна запись стёрлась. Всегда ли можно однозначно восстановить её по остальным?
б) Пусть стёрлись k записей, и известно, что в этой стране никакие три города не лежат на одной прямой. При каком наибольшем k всегда можно однозначно восстановить стёршиеся записи?
|
|
|
Решение |
Задача 30823 |
|
|
В связном графе степени всех вершин чётны. Докажите, что на рёбрах этого графа можно расставить стрелки так, чтобы выполнялись следующие условия:
а) двигаясь по стрелкам, можно добраться от каждой вершины до любой другой;
б) для каждой вершины числа входящих и выходящих рёбер равны.
|
|
|
Решение |
Страница: << 63 64 65 66 67 68 69 >> [Всего задач: 383]
