Таблицы Брадиса

Теория графов 2

Теория графов 2

Элементы математики в задачах - Г. А. Мерзон

в) Решение этого пункта аналогично предыдущему. Точкой А бу­дет произвольная вершина п-угольника, точками В и В — ее соседи.

Теория групп

Симметрия в данном случае будет относительно прямой, соединя­ющей А с центром п-угольника, которая не обязательно является диагональю. Разница будет еще лишь в том, что повороты будут кратными не 90°, а 360°/п.

Группа симметрий имеет 2п элементов и две образующие — а и Ь, соответствующие, опять же, повороту и симметрии. Порядок элемента а равен п, порядок элемента Ь равен 2, а умножение в группе удовлетворяет соотношению аЬ = Ьап—1.

Теория графов 2

листок зд / март 2005

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

Среди отдельных задач стоит отметить теорему Кэли о числе де­ревьев и теорему Холла о совершенном паросочетании.

Конец листка посвящен планарным графам, т. е., по существу, началам комбинаторной топологии. Основные результаты здесь — знаменитая формула Эйлера и критерий планарности Понтрягина — Куратовского.

Задача 1. В турнире по олимпийской системе участвовали п команд. Сколько всего было сыграно матчей?

Решение. Раз соревнования проводились по олимпийской системе, из п команд ровно одна стала победителем, а все остальные отсеялись в турнире. При этом после каждого сыграного матча уходила ровно одна команда — проигравшая. Значит, всего партий было сыграно п — 1.