Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/circles/oim/materials/spring06/zhest/z08-kar.ps Дата изменения: Sat Apr 8 14:03:00 2006 Дата индексирования: Sun Dec 23 01:25:39 2007 Кодировка: Windows-1251 Поисковые слова: m 2

Ориентированные графы
Группа Жести, Карина Куюмжиян, 08.04.06
Пусть G ориентированный граф , которому разрешается иметь противоположно
направленные ребра, петли и кратные ребра. Путь в графе G последовательность
ориентированных ребер v 0 v 1 ; v 1 v 2 ; : : : ; v k 1 v k , в котором все вершины v 0 ; v 1 ; : : : ; v k
различны.
Определение. Вершины a и b ориентированного графа G назовем связанными,
если в графе G существуют пути из a в b и из b в a. Ориентированный граф
G назовем сильно связным, если любые две его вершины связаны.
Определение. Говорят, что на множестве M задано отношение эквивалентности,
если в множестве f(m 1 ; m 2 )jm 1 ; m 2 2 Mg выделено такое подмножество E,
что :
1. 8m 2 M (m; m) 2 E (рефлексивность)
2. 8m 1 ; m 2 2 M (m 1 ; m 2 ) 2 E ! (m 2 ; m 1 ) 2 E (симметричность)
3. 8m 1 ; m 2 ; m 3 2 M ((m 1 ; m 2 ) 2 E & (m 2 ; m 3 ) 2 E ! (m 1 ; m 3 ) 2 E
(транзитивность)
Если (m 1 ; m 2 ) 2 E, то это часто обозначается m 1  m 2
Определение. Турниром называется полный граф, в котором все ребра
ориентированы. Турнир называется сильным, если множество его вершин
нельзя разбить на 2 части так, чтобы все ребра между частями шли в одном
направлении.
Задача 1. В стране некоторые города соединены дорогами. Доказать,
что король может установить на дорогах одностороннее движение так, что,
выехав из любого города, уже нельзя будет в него вернуться.
Задача 2. Докажите, что в любом турнире есть остовный путь (то есть
путь, проходящий по всем вершинам).
Задача 3. Докажите, что если дан сильный турнир с n вершинами, то
для любого p, 3  p  n, в этом турнире есть ориентированный цикл с p
вершинами.
Задача 4. Дан турнир. Будем говоорить, что А хуже Б, если всем,
кому проиграл Б, проиграл и А. Докажите, что не может быть ровно два
человека, которые не хуже никого.
Задача 5. Доказать, что в любом ориентированном графе связанность
является отношением эквивалентности: все вершины разбиваются на группы
V 1 ; V 2 ; : : : ; V k так, что внутри каждой группы любые две вершины связаны,
а любые две вершины из разных групп - нет. V i называются компонентами
сильной связности графа G.
Для данного ориентированного графа G можно построить граф C(G),
вершинами которого будут компоненты сильной связности исходного графа.
В C(G) две вершины соединены ребром тогда и только тогда, когда между
соответствующими группами вершин в исходном графе было хотя бы одно
ребро. (все ребра между двумя фиксированными группами ориентированы
одинаково)
Задача 6. Для любого ориентированного графа
а. В графе C(G) нет циклов
б. Для любой компоненты сильной связности V i граф G(V i ) на вершинах
множества V i с ребрами графа G между этими вершинами сильно связен.
Задача 7. В ориентированном графе 200 вершин, из каждой вершины
выходит хотя бы одно ребро и в каждую вершину входит хотя бы одно
ребро. Докажите, что можно добавить не более 100 новых ориентированных
ребер так, чтобы этот граф стал сильно связным. (Между двумя вершинами
может быть проведено несколько ребер.)
1

Задача 8. В Тридевятом царстве 2005 городов. Некоторые города соединены
дорогами с односторонним движением.Известно, что для любых двух городов
из одного из них можно добраться до другого, не нарушая правил дорожного
движения (т.е. для городов А и В можно проехать из А в В или из В в
А). Король хочет направить в несколько городов своих наместников так,
чтобы в любой город, где нет наместника, можно было напрямую попасть
из города, где есть наместник. Докажите, что для этого ему хватит 1003
наместников.
Определение. В неориентированном связном графе мост - это такое
ребро, после удаления которого граф перестает быть связным (концы ребра
не удаляются).
Задача 9. Пусть дан неориентированный связный граф G без мостов.
Докажите, что его ребра можно ориентировать так, чтобы получившийся
граф был сильно связен.
Задача 10. В стране n городов, любые два соединены дорогой. Король
хочет ввести на всех дорогах одностороннее движение так, чтобы из любого
города в любой другой можно было добраться, проехав по не более, чем
двум дорогам. Докажите, что ему это удастся при
a) n=99,
b) n=100.
Задача 11. По кругу расставлено несколько коробочек. В каждой из них
может лежать один или несколько шариков (или она может быть пустой).
За один ход разрешается взять все шарики из любой коробочки и разложить
их, двигаясь по часовой стрелке, начиная со следующей коробочки, кладя
в каждую коробочку по одному шарику.
a) Докажите, что если на каждом следующем ходе шарики берут из той
коробочки, в которую попал последний шарик на предыдущем ходе, то в
какой-то момент повторится начальное размещение шариков.
b) Докажите, что за несколько ходов из любого начального размещения
шариков по коробочкам можно получить любое другое.
Задача 12. В королевстве N городов и r дорог, каждая дорога соединяет
два города, и из любого города можно добраться до любого по дорогам. В
городах живут гонцы. В начале каждого года один из городов отправляет
во все соседние (т. е. соединенные с ним дорогами) города по гонцу (в
таком городе должно быть достаточное для этого количество гонцов). Если
в каждом городе гонцов недостаточно, то движения гонцов прекращаются.
Пусть через несколько лет движение гонцов прекратилось. Докажите, что
если города, отправляющие гонцов, выбирать по-другому, то движение гонцов
все равно прекратится; при этом конечное количество гонцов в каждом
городе не зависит от выбора последовательности отправляющих городов.
Задача 13.Дан граф без мостов. Двое играют в игру: по очереди ориентируют
ребра графа. Проигрывает тот, после чьего хода граф перестает быть сильно
связным. Если все ребра уже ориентированы, то ничья. Кто выигрывает при
правильной игре?
Задача 14. На прямой в произвольном порядке расставлены числа от 1
до 101. Доказать, что можно выбрать либо 11 чисел, образующих возрастающую
последовательность, либо 11 чисел, образующих убывающую последовательность.
2