velikol.ru
1

7 «М» класс Школа №25 2011-2012 учебный год



15 Графы -2

20 декабря

Деревья

Деревом называется связный граф без циклов. Вершина степени 1 называется висячей. Вершина степени 0 называется изолированной.

  • Докажите, что если в графе существует единственный маршрут из любой вершины в любую другую, то этот граф — дерево.

  • Докажите, что в любом дереве есть висячая вершина.

  • Докажите, что таких вершин по крайней мере две.

  • Докажите, что в дереве вершин на одну больше, чем ребер.

  1. Система станций метро устроена таким образом, что с каждой станции на каждую можно проехать единственным образом. Доказать, что одну из станций можно закрыть (без права проезда через нее) так, что это свойство сохранится.

  2. Нарисуйте всевозможные деревья с пятью вершинами.

  3. Докажите, что если в графе с n вершинами меньше, чем n – 1 ребро, то он не связен, а если в нем больше, чем n – 1 ребро, то в нём есть циклы.

  4. Все города Трапезундии (в том числе столица) соединены кольцевой железной дорогой. Кроме того, столица соединена отдельными линиями с каждым из городов, кроме соседей по кольцу. Правительство решило разделить железнодорожную сеть между двумя компаниями так, чтобы, пользуясь дорогами любой из компаний, можно было доехать от любого города до любого другого. Можно ли выполнить это решение?

  5. В некоторой стране 19 городов и всего 18 дорог, притом из каждого города можно проехать в любой другой. На всех дорогах ввели одностороннее движение. Докажите, что теперь, выехав из какого-нибудь города невозможно вернуться в него обратно.

  6. В дереве есть 10 вершин степени 3, 15 вершин степени 4, а все остальные вершины — висячие. Сколько их?

  7. На каждую общую сторону двух клеток шахматной доски положена спичка. Какое минимальное количество спичек придется убрать, чтобы из каждой клетки можно было дойти до каждой, не перепрыгивая через спички?

  8. Ребра графа, степени всех вершин которого равны 5, раскрасили в три цвета так, что по ребрам каждого цвета можно от любой вершины дойти до любой другой. Каким могло быть число вершин этого графа?

  9. В дереве степени всех вершин нечётные. Докажите, что более половины его вершин – висячие.

  10. Пиранья считается сытой, если съест трех других пираний. В пруд выпустили несколько пираний. Через день осталась только одна сытая рыбка, причем ровно 100 пираний погибли сытыми. Какое наименьшее число рыб могло быть выпущено в пруд вначале?

^ Скелеты

Скелетом (или остовом) графа называется подграф (часть графа), содержащий все его вершины и являющийся деревом.

Процесс построения скелета: вершины — резервуары, ребра — трубы, пошагово исследуем протекание воды по трубам, закрывая те трубы, которые нам оказались не нужны (подали воду в уже заполненные резервуары).

  • Докажите, что если в связном графе есть цикл, то при удалении любого ребра, входящего в этот цикл, граф останется связным.

  • Докажите, что если граф имеет единственный скелет, то он — дерево.

  1. В связном графе 5 вершин и 10 ребер. Сколько ребер можно удалить так. чтобы граф остался связным?

  2. В связном графе В вершин и Р ребер. Сколько ребер надо удалить, чтобы получить скелет этого графа?

  3. Можно ли раскрасить ребра куба в два цвета так, чтобы по ребрам каждого цвета можно было добраться из любой вершины в любую?

  4. Волейбольная сетка имеет вид прямоугольника размером 50×200 клеток. Какое наибольшее число веревочек можно перерезать так, чтобы сетка не распалась на куски?

  5. Могут ли два различных скелета одного графа не иметь общих ребер?

  6. Система станций метро устроена таким образом, что из каждой станции в каждую можно проехать. Доказать, что одну из станций можно закрыть так, что это свойство сохранится.

  7. Каждая грань кубика разбита на 4 квадрата. Некоторые стороны этих квадратов покрасили в красный цвет — всего 26 сторон. Докажите, что на поверхности кубика найдется замкнутая ломаная из красных отрезков.

  8. В стране 15 городов, некоторые из них соединены авиалиниями, принадлежащими трем авиакомпаниям. Известно, что даже если любая из авиакомпаний прекратит полеты, можно будет добраться из любого города в любой другой (возможно, с пересадками), пользуясь рейсами оставшихся двух компаний. Какое наименьшее количество авиалиний может быть в стране?