Сколько вершин у графа изображенного слева
Под графом мы будем понимать множество точек ( вершин ), некоторые из которых соединены отрезками ( ребрами ).
Степень вершины графа — это количество выходящих из нее (или, что то же самое, входящих в нее) ребер (еще говорят: количество ребер, инцидентных данной вершине). Вершина графа называется четной , если ее степень четна, и нечетной в противном случае.
Некоторая часть вершин данного графа называется компонентой связности , если из любой ее вершины можно «дойти» до любой другой, двигаясь по ребрам.
В некоторых случаях на ребрах графа выбирается «направление движения» (например, когда на автомобильной дороге вводится одностороннее движение). При этом получается ориентированный граф . (Если направление движения по ребрам не определено, то граф называется неориентированным ). В ориентированном графе различают положительную и отрицательную степень каждой вершины (то есть количество ребер, соответственно, входящих и выходящих из нее). Две вершины могут быть соединены и несколькими ребрами, направления движения по которым противоположны («дорога с двусторонним движением»). Изменяется понятие компоненты связности: теперь каждый «маршрут» от одной вершины до другой должен учитывать направление движения по ребрам.
Задачи
1. Между девятью планетами Cолнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля — Меркурий, Плутон — Венера, Земля — Плутон, Плутон — Меркурий, Меркурий — Венера, Уран — Нептун, Нептун — Сатурн, Сатурн — Юпитер, Юпитер — Марс и Марс — Уран. По каждому маршруту ракеты летают в обе стороны. Можно ли долететь на рейсовых ракетах от Земли до Марса?
Решение.
Построим граф, вершинами которого являются планеты Солнечной системы, а ребрами — существующие маршруты рейсовых ракет. Изобразив такой граф на рисунке, нетрудно заметить, что он состоит из двух компонент связности (на нашем рисунке они выделены разными цветами). Земля и Марс оказываются в разных компонентах связности, поэтому долететь от Земли до Марса на рейсоых ракетах нельзя.
2. Доска имеет форму двойного креста, который получается, если из квадрата 4×4 убрать угловые клетки. Можно ли обойти ее ходом шахматного коня и вернуться на исходную клетку, побывав на всех клетках ровно по одному разу?
Ответ. На рисунке указано одно из возможных решений (клетки пронумерованы в том порядке, в котором их обходит конь).
3. Можно ли, сделав несколько ходов конями из исходного положения (верхний рисунок), расположить их так, как показано на нижнем рисунке? (Выходить за пределы поля 3×3 не разрешается.)
Решение. Пронумеруем клетки поля 3×3, как показано на рисунке слева. Построим граф, вершинами которого являются эти клетки. Две клетки соединим ребром графа, если из одной в другую можно попасть за один ход коня. Расположим вершины графа так, как показано на рисунке справа, и проведем все ребра. Отметим на этом рисунке начальное и конечное местоположение коней. Для того, чтобы осуществить требуемую перестановку коней, нужно по крайней мере, чтобы, например, один из черных коней «перепрыгнул» через одного из белых. Но кони ходят по очереди, и ни в какой момент времени на одной клетке не могут оказаться два коня сразу. Поэтому осуществить такое «перепрыгивание» невозможно. Стало быть, невозможно и переставить коней требуемым образом.
4. В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены авиалинией в том и только в том случае, если двузначное число, образованное названиями городов, делится на 3. Можно ли долететь по воздуху из города 1 в город 9?
Построим граф, вершинами которого являются города, а ребрами — существующие авиалинии. Вспомним признак делимости на 3: натуральное число делится нацело на 3 тогда и только тогда, когда сумма его цифр делится на 3. Заметим, что если название города делится на 3, то он соединен авиалиниями только с городами, названия которых тоже делятся на 3. Наоборот, те города, названия которых не делятся на 3, не могут быть соединены авиалиниями с городами, названия которых делятся на 3. Поэтому города 3, 6 и 9 образуют одну компненту связности графа, в которую никакие другие города не входят. Это означает, что из города 1 в город 9 добраться по воздуху нельзя.
Упражнение: А какие еще компоненты связности есть в этом графе?
5. В государстве 100 городов. Из каждого города выходит 4 дороги. Сколько всего дорог в государстве?
Решение. Обойдем по очереди все города, считая дороги, входящие из них. Всего таким способом мы насчитаем 400 дорог. Но каждая дорога выходит из двух городов, значит, каждую дорогу мы посчитали два раза. Поэтому на самом деле дорог в государстве в два раза меньше, чем мы насчитали, то есть 200.
Теорема 1. Количество ребер в любом графе равно половине суммы степеней его вершин.
Докажите эту теорему самостоятельно по аналогии с задачей 5.
6. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими?
Подсказка: попытайтесь посчитать количество телефонных проводов.
Решение. В качестве вершин графа возьмем телефоны, а в качестве ребер — телефонные провода. Применим к этому графу теорему 1. Степень каждой вершины графа равна 5, значит, сумма степеней всех вершин равна 5·15=75. Это нечетное число, поэтому его половина — число нецелое. То есть в нашем графе нецелое число ребер, и в городе нецелое число проводов, чего быть не может.
Следующую задачу в силу ее важности сформулируем в виде теоремы. 7. Теорема 2. Всякий (неориентированный) граф содержит четное число нечетных вершин.
Доказательство. По теореме 1 количество ребер графа равно половине суммы степеней всех вершин графа. Все вершины графа делятся на четные и нечетные. Сумма степеней четных вершин графа всегда четна. А вот сумма нечетного количества нечетных чисел нечетна, поэтому если нечетных вершин нечетное количество, то сумма их степеней будет нечетна. Тогда сумма степеней всех вершин графа будет нечетна. Половина этой суммы будет нецелым числом, то есть в графе нецелое число ребер, а такого быть не может. Полученное противоречие доказывает, что количество нечетных вершин графа не может быть нечетным.
При решении всех последующих задач мы будем пользоваться этой теоремой. Любое решение следует начинать с выбора вершин и ребер графа. Попробуйте решить эти задачи самостоятельно, не ссылаясь на теорему, а заново проводя ее доказательство в каждом конкретном случае.
8. В классе 30 человек. Может ли быть так, что 9 человек имеют по 3 друга, 11 — по 4 друга, а 10 — по 5 друзей?
Решение. Сделаем учеников вершинами графа, а ребрами будем соединять тех из них, которые дружат между собой. По условию в таком графе четных вершин будет 11, а нечетных 9+10=19, то есть нечетное число, что противоречит теореме 2.
9. Школьник Вася Пупкин сказал своему приятелю Вите Иванову:
— У нас в классе тридцать пять человек. И представь, каждый из них дружит ровно с одиннадцатью одноклассниками.
— Не может этого быть, — сразу же ответил Витя Иванов, победитель математической олимпиады.
Почему он так решил?
Решение. Решение этой задачи полностью аналогично решению задачи 6.
10. У короля 19 вассалов. Может ли оказаться так, что у каждого вассала 1, 5 или 9 соседей ?
Решение. Сделаем вассалов вершинами графа; ребрами соединим тех из них, которые являются соседями. По условию все вершины этого графа нечетны, а всего их 19, то есть тоже нечетное число. Но по теореме 2 такого быть не может.
11. Может ли в государстве, в котором из каждого города выходит ровно 3 дороги, быть ровно 100 дорог?
Решение. Сделаем города вершинами графа, а дороги — его ребрами. По условию в этом графе 100 ребер, а по теореме 1 число ребер равно половине суммы степеней всех вершин. Значит, сумма степеней всех вершин равна 200. Но степень каждой вершины по условию равна 3, а 200 не делится на 3. Полученное противоречие доказывает, что такого быть не может.
12. В школе 953 ученика. Одни из них знакомы, другие не знакомы друг с другом. Доказать, что хотя бы у одного из них число знакомых среди учеников этой школы чётно.
Решение. Сделаем учеников вершинами графа и будем соединять ребрами тех из них, которые знакомы друг с другом. Если бы у всех школьников число знакомых среди учеников этой же школы число знакомых было нечетно, то все 953 вершины нашего графа были бы нечетными, что противоречит теореме 2. Значит, есть по крайней мере один школьник, у которого число знакомых среди учеников этой же школы четно. Более того, можно сказать, что таких школьников обязательно должно быть нечетное число (подумайте почему).
13. Докажите, что число людей, живших когда-либо на Земле и сделавших нечетное число рукопожатий, четно.
Решение. Сделаем всех людей, когда-либо живших на Земле, вершинами графа, а рукопожатия — его ребрами. (При этом две вершины могут соединяться и несколькими ребрами; такие ребра называют кратными .) Люди, сделавшие нечетное число рукопожатий, — нечетные вершины такого графа, поэтому по теореме 2 их количество четно.
14*. Докажите, что не существует графа с пятью вершинами, степени которых равны 4, 4, 4, 4 и 2 соответственно.
Решение. У каждой из первых четырех вершин степень 4, то есть каждая из этих вершин соединена ребрами со всеми остальными (поскольку всего вершин 5). В частности, каждая из этих четырех вершин соединена и с пятой вершиной. Поэтому если в графе с пятью вершинами четыре вершины имеют степень 4, то и оставшаяся вершина должна иметь степень 4.
15*. Можно ли расположить в пространстве 9 шаров так, чтобы каждый из них касался ровно пяти других?
Решение. Сделаем вершинами графа шары и соединим ребрами те из них, которые касаются друг друга. По условию в таком графе будет нечетное число нечетных вершин, что противоречит теореме 2.
16*. а) Можно ли нарисовать на плоскости 8 отрезков так, чтобы каждый пересекался ровно с тремя другими? б) Тот же вопрос для 9 отрезков.
Ответ. а) Да, см. рисунок; б) нет.
Решение. Сделаем отрезки вершинами графа и соединим ребрами те из них, которые пересекаются между собой. По условию п. б) в таком графе нечетное число нечетных вершин, что противоречит теореме 2. Для пункта а) это рассуждение не годится, однако это еще не означает, что сделать такой рисунок возможно. Чтобы это доказать, надо его нарисовать. Для этого достаточно придумать рисунок с 4 отрезками, каждый из которых пересекается ровно с тремя другими, а потом изобразить два таких рисунка рядом. (Здесь важно, что в условии фигурируют именно отрезки, а не прямые.)
Вы видите ошибку? Выделите её и нажмите Ctrl+Enter! | | | |
Хроматическое число планарного графа
Предположим, что для планарного графа с [math]N[/math] вершинами существует раскраска в [math]6[/math] цветов. Докажем то же для графа с [math] N+1 [/math] вершиной.
По только что доказанной лемме в [math] G [/math] найдётся вершина степени не больше [math]5[/math] . Удалим её; по предположению индукции получившийся граф можно раскрасить в [math]6[/math] цветов.
Раскраска в 5 цветов
Пусть граф [math]G[/math] — планарный. Тогда [math] \chi (G) \leqslant 5.[/math]
[math]u[/math] и смежные ей вершины
Начало доказательства такое же, как в предыдущей теореме, трудность возникает в индукционном переходе. Покажем что для случая с [math]5[/math] -ю цветами всё равно можно вернуть удалённую вершину так, чтобы раскраска осталась правильной.
Обозначим за [math] u [/math] — возвращаемую вершину, [math] v^ [/math] — вершину, покрашенную в [math] k [/math] цвет.
Если среди вершин, смежных [math] u [/math] , есть две вершины одного цвета, значит остаётся по меньшей мере один свободный цвет, в который мы и покрасим [math] u [/math] .
Иначе, уложим полученный после удаления [math] u [/math] граф на плоскость, вернём вершину [math] u [/math] (пока бесцветную) и пронумеруем цвета в порядке обхода смежных вершин по часовой стрелке.
Попробуем покрасить [math] u [/math] в цвет [math]1[/math] . Чтобы раскраска осталась правильной, перекрасим смежную ей вершину [math]v_1^[/math] в цвет [math]3[/math] . Если среди смежных ей вершин есть вершины [math] v_i^ [/math] , покрасим их в цвет [math]1[/math] , и так далее. Рассмотрим две необычные ситуации, которые могут наступить во время обхода:
- мы дойдём до уже однажды перекрашенной вершины (и хотим перекрасить её обратно, что не получится сделать). Видно что такая ситуация невозможна, поскольку мы меняли цвета вершин по схеме [math]1[/math] [math]\leftrightarrow[/math] [math]3[/math] , и если по завершении обхода мы получили две смежные вершины одного цвета, значит и до перекрасок в этом месте были две вершины одинакового цвета, а по предположению граф без [math] u [/math] был раскрашен правильно.
- дойдём до вершины, смежной [math] u [/math] , исходно имевшей цвет [math]3[/math] , которую перекрасить в [math]1[/math] нельзя ( [math] u [/math] теперь имеет цвет [math]1[/math] ).
Если этот процесс был успешно завершён, то получили правильную раскраску. Если же в соответствии со вторым вариантом перекраска не удалась, это означает, что в графе есть цикл [math] u v_1^ v_2^ v_3^ \ldots v_^ v_k^ u [/math] .
Тогда попытаемся таким же образом перекрасить [math] u [/math] в цвет [math]2[/math] , а смежную ей [math]w_1^[/math] в цвет [math]4[/math] (со последующими перекрасками). Если удастся — раскраска получена.
Успешное перекрашивание | Цикл 1—3, перекрасить не удаётся |
![]() |
![]() |
![]() |
![]() |
Заметим, что не удаётся составить подобное доказательство для раскраски в четыре цвета, поскольку здесь наличие двух вершин одного цвета среди смежных [math] u [/math] не исключает того, что при их (смежных вершин) раскраске использовались все возможные цвета.
Раскраска в 4 цвета
Теорема о четырёх красках — утверждение о том, что всякую расположенную на сфере карту можно раскрасить четырьмя красками так, чтобы любые две области, имеющие общий участок границы, были раскрашены в разные цвета. При этом области могут быть как односвязными, так и многосвязными (в них могут присутствовать «дырки»), а под общим участком границы понимается часть линии, то есть стыки нескольких областей в одной точке общей границей для них не считаются.
карта России раскрашенная в [math]4[/math] цвета
Теорема о четырёх красках была доказана в [math]1976[/math] году Кеннетом Аппелем и Вольфгангом Хакеном из Иллинойского университета. Это была первая крупная математическая теорема, доказанная с помощью компьютера. Первым шагом доказательства была демонстрация того, что существует определенный набор из [math]1936[/math] карт, ни одна из которых не может содержать карту меньшего размера, которая опровергала бы теорему. Аппель и Хакен использовали специальную компьютерную программу, чтобы доказать это свойство для каждой из [math]1936[/math] карт. Доказательство этого факта заняло сотни страниц. После этого Аппель и Хакен пришли к выводу, что не существует наименьшего контрпримера к теореме, потому что иначе он должен бы содержать, хотя не содержит, какую-нибудь из этих [math]1936[/math] карт. Это противоречие говорит о том, что вообще не существует контрпримера. Изначально доказательство не было принято всеми математиками, поскольку его невозможно было проверить вручную. В дальнейшем оно получило более широкое признание, хотя у некоторых долгое время оставались сомнения.
Чтобы развеять оставшиеся сомнения, в [math]1997[/math] году Робертсон, Сандерс, Сеймур и Томас опубликовали более простое доказательство, использующее аналогичные идеи, но по-прежнему проделанное с помощью компьютера. Кроме того, в [math]2005[/math] году доказательство было проделано Джорджсом Гонтиром с использованием специализированного программного обеспечения (Coq v7.3.1)
Эквивалентные формулировки
В теории графов утверждение теоремы четырёх красок имеет следующие формулировки:
- Хроматическое число планарного графа не превосходит [math]4[/math] .
- Рёбра произвольной триангуляции сферы можно раскрасить в три краски так, что все стороны каждого треугольника были раскрашены в разные цвета.
Ложное доказательство
Ошибочным мнением считается, что решением проблемы четырех красок является — доказательство того, что невозможно начертить карту, на которой было бы всего лишь пять стран и каждая из этих стран примыкала бы к четырем остальным странам. Нетрудно доказать, что такую карту начертить нельзя. Можно предположить, что отсюда автоматически следует решение проблемы четырех красок для всех карт, но такое заключение неверно.
Карта(слева) окрашена пятью цветами, и нужно изменить как минимум [math]4[/math] из [math]10[/math] регионов, чтобы получить окраску в четыре цвета(справа)
Источники информации
- matica.org — Раскраска планарного графа
- Википедия — Проблема четырёх красок
- Wikipedia — Four color theorem
Информатика и математика))))10-11 класс)))всё внутри!
Количество ребер графа G, исходящих из вершины v1( 1 это индекс,внизу справа), называется степенью вершины v1. Вершина,степень которой равна 0, называется изолированной. Вершина,степень,которой равна 1, называется висячей. Сколько висячих вершин имеет граф,изображенный ниже?
(это задание с конкурса КИТ, по информатике. Мы сегодня писали а я не сделала это задание! Хочу всетаки понять какой тут ответ!)
Голосование за лучший ответ
Я вообще не могу понять причем тут математика и информатика какая то х*ня. 5?
Катька, смотри сколько концов свободных болтается.. . -их всего 4.
Это и есть твои «вершины со степенью 1».
Чтоб понять, двигаемся слева направо по картинке. Следи.
первая «вершина» (кружочек) сколько имеет связей? — ответ: одну (одной линией соединена с ещё одной «вершиной»-кружочком) .
Вторая (слева-направо, да? помнишь) верхняя «вершина» уже сколько имеет связей? Со сколькими кружочками связана? — ответ: с двумя. т. е. её степень =2. и т. д. (у третьей будет 4 связи, её степень — 4).
Всё на самом деле проще простого.
Похожие вопросы
Понятие и представление графа: матрица смежности, список смежности
Графы — фундаментальное понятие как в математике, так и в информатике. Проще всего объяснить его с помощью аналогии с дорожной системой. Существует определённый набор городов, некоторые из которых связаны дорогами, которые могут быть как односторонними, так и двухсторонними. Вся эта структура и называется графом.
Ну а более формально, граф — комбинация набора вершин и набора рёбер. Вершины — это города, а рёбра — дороги. Визуально граф можно представить так:
Этот граф состоит из 6 вершин, пронумерованных начиная с единицы, и 7 двухсторонних рёбер. Рёбра обычно записывают в виде пар вершин, которые они соединяют: \(1\)-\(2\), \(1\)-\(5\), \(2\)-\(3\), \(2\)-\(5\), \(3\)-\(4\), \(4\)-\(5\), \(4\)-\(6\).
Ориентированные и неориентированные графы
Мы уже упоминали, что “дороги” в графе могут быть как односторонними, так и двухсторонними. Для этого свойства существует отдельный термин: односторонние “дороги” называются ориентированными рёбрами (или дугами), а двухсторонние — неориентированными.
Граф, в котором все рёбра неориентированные, также называют неориентированным, а граф с ориентированными рёбрами, соответственно, ориентированным.
![]() |
![]() |
Слева изображён неориентированный граф, а справа — ориентированный. Как несложно догадаться, левый граф можно обходить как по часовой стрелке, так и против, а правый можно полностью обойти только по часовой, хотя одно из ребёр в нём также неориентированное (считается, что это два противоположных ориентированных ребра).
Пути и циклы
Путём в графе называется последовательность вершин, каждая из которых соединена со следующей ребром. Чаще всего под “путём” подразумевают простой путь, все вершины которого различны. Путь, который проходит через какую-либо вершину более одного раза называют сложным путём.
Если первая вершина пути совпадает с последней, то такой путь называют циклом.
Приведём примеры на этом графе:
Из множества возможных простых путей самый длинный: \(a — f — c — d — e — b — h\) (существуют и другие пути с такой же длиной).
Циклом является путь \(b — c — d — e — b\) (выделен цветом). Можно начать и с любой другой вершины, например, \(c — d — e — b — c\).
Кратные рёбра и петли
Существует множество разновидностей графов, и среди них встречаются довольно специфические. В частности, так называемые мультиграфы разрешают наличие между двумя вершинами нескольких рёбер (называемых кратными рёбрами), а также наличие петель. Петля — ребро, входящее в ту же вершину, из которой исходит. Выглядят они следующим образом:
Красным выделены кратные рёбра, а синим — петли.
Мультиграфы встречаются в задачах реже чем обычные графы (называемые простыми), но всё же встречаются, поэтому стоит иметь о них элементарное представление.
Связные графы
Граф называется связным если между любой парой вершин существует хотя бы один путь. Как пример рассмотрим следующий граф:
Одно из рёбер проведено штрихами. Если это ребро присутствует, то граф является связным. Если же его убрать, то связность теряется, граф разбивается на две части, друг с другом не связанные. Такие части называются компонентами связности.
Определение дерева
Дерево — вид графа, который можно назвать самым простым, но они обладают множеством особых свойств и встречаются в задачах чуть ли не чаще остальных графов.
Дерево — это связный граф без циклов, петель и кратных рёбер.
Все изображённые графы являются деревьями:
Среди множества свойств деревьев можно выделить два самых известных:
- Количество рёбер связано с количеством вершин формулой \(E = V — 1\).
- Между любой парой вершин существует ровно один путь.
Матрица смежности
Существует два основных способа представления графов в программировании. Один из них, матрица смежности, используется гораздо реже, но очень просто реализуется. Граф из \(N\) вершин задаётся матрицей (двумерным массивом) \(N * N\), в которой \(g[i][j]\) — логическое значение, true или false , обозначающее, существует ли ребро из вершины \(i\) в вершину \(j\).
В качестве примера решим простую задачу: для каждой вершины графа выведем количество рёбер, смежных с ней.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38using namespace std; bool graph[1000][1000]; int main() int n, m; //количество вершин и рёбер соответственно cin >> n >> m; for (int i = 0; i m; i++) int u, v; //номера вершин, соединённых очередным ребром cin >> u >> v; u--, v--; //Здесь стоит остановиться и вдуматься. //Чаще всего в задачах вершины будут нумероваться с 1 до N, //в отличие от индексации массивов в C++. //У этой проблемы есть два решения. //Первое: работать с номерами "как есть": создавать массивы размером N + 1, //использовать циклы от 1 до N, и т.д. //Второе: уменьшать номера вершин на единицу при вводе, и увеличивать обратно при выводе //Какое из них использовать - ваш личный выбор. //Для меня 1-индексация в С++ выглядит очень чужеродно, поэтому я использую второе решение. graph[u][v] = graph[v][u] = true; //Если бы граф был ориентированным, то обратное ребро мы бы не создавали. > for (int i = 0; i n; i++) int c = 0; for (int j = 0; j n; j++) if (graph[i][j]) c++; > > cout <c <" edges adjacent to vertex " <i + 1 <endl; > >Преимущества матрицы смежности:
- Сложность проверки наличия ребра между двумя вершинами: \(O(1)\)
Недостатки матрицы смежности:
- Занимает \(N^2\) памяти, что неприемлемо для достаточно больших графов.
- Сложность перебора всех вершин, смежных с данной: \(O(N)\)
Список смежности
Гораздо чаще для представления графов используется список смежности. Его идея заключается в хранении для каждой вершины расширяемого массива (вектора), содержащего всех её соседей.
Решим ту же задачу с использованием списка смежности (и С++11 для for-each):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26using namespace std; vectorint> graph[100000]; //массив из 100000 векторов. int main() int n, m; cin >> n >> m; for (int i = 0; i m; i++) int u, v; cin >> u >> v; u--, v--; graph[u].push_back(v); graph[v].push_back(u); > for (int i = 0; i n; i++) int c = 0; for (int v: graph[i]) //можно было бы просто записать "int c = graph[i].size();", c++; //но такая реализация показывает, как можно перебирать > //соседние вершины. cout <c <" edges adjacent to vertex " <i + 1 <endl; > >Если требуется также удалять рёбра, то вместо вектора нужно использовать std::set .
Преимущества списка смежности:
- Использует \(O(M)\) памяти, что оптимально.
- Позволяет быстро перебирать соседей вершины.
- Позволяет за \(O(\log N)\) проверять наличие ребра и удалять его (при использовании std::set ).
Недостатки списка смежности:
- При работе с насыщенными графами (количество рёбер близко к \(N^2\)) скорости \(O(\log N)\) может не хватать (единственный повод использовать матрицу смежности).
- Для взвешенных графов приходится хранить vector> , что усложняет код.
brestprog
Олимпиадное программирование в Бресте и Беларуси