Меню
Главная
Авторизация/Регистрация
 
Главная arrow Математика, химия, физика arrow ГЕОМЕТРИЧЕСКАЯ ТЕОРИЯ ГРАФОВ
Посмотреть оригинал

Задачи и упражнения

  • 1. Докажите, что связный граф остается связным после удаления ребра тогда и только тогда, когда это ребро содержится в некотором цикле.
  • 2. Докажите, что связный граф с п вершинами содержит не менее п-1 ребра.
  • 3. Докажите, что если граф содержит п вершин и п-к ребер при к>1, то он является несвязным и состоит не менее чем из к компонент связности.
  • 4. Известно, что граф является fc-связным и имеет п вершин. Какое минимальное количество ребер имеет этот граф?
  • 5. Военная база противника расположена на 6 островах, соединенных мостами (см. рис. 27). Какое минимальное число мостов (или островов) достаточно взорвать, чтобы разобщить противника?
  • 6. Докажите, что

множество всех ребер конечного связного графа образует простой цикл р ^7

тогда и только тогда, когда

степень каждой вершины равна двум.

  • 7. В конечном графе G вершины А и В имеют нечетную степень, а степени остальных вершин четны. Докажите, что вершины А и В соединяются цепью.
  • 8. В локальную сеть объединены несколько компьютеров. Известно, что один из них может передавать информацию только одному компьютеру, другой связан с 11 компьютерами, все остальные могут передавать информацию 10 другим. Докажите возможность передачи информации от первого компьютера ко второму (может быть через компьютеры-посредники).
  • 9. В некоторой стране из каждого города выходит 100 дорог, по которым из любого города можно добраться до любого другого. Одну дорогу закрыли на ремонт.

Докажите, что и теперь из любого города можно добраться до любого другого.

  • 10. В стране «Цифра» есть 9 городов с названиями 1, 2, ..., 9. Путешественник обнаружил, что два города соединяются авиалинией в том и только том случае, если двузначное число, полученное из цифр-названий, делится на 3. Можно ли добраться из города 1 в город 9?
  • 11. В городе 15 банков, каждый из которых осуществляет взаиморасчеты не менее чем с 7 другими. Докажите, что любой банк может перевести деньги в любой другой (быть может, при помощи банков- посредников).
  • 12. Докажите, что элементарный граф с п

п -1

вершинами, степень каждой из которых не меньше ——, является связным.

13. В связном графе степени четырех вершин равны 3, а степени остальных вершин равны 4. Докажите, что нельзя удалить ребро так, чтобы граф распался на две изоморфные компоненты связности.

 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Популярные страницы